Heap

Problem There are n workers. You are given two integer arrays quality and wage where quality[i] is the quality of the ith worker and wage[i] is the minimum wage expectation for the ith worker. We want to hire exactly k workers to form a paid group. To hire a group of k workers, we must pay them according to the following rules: Every worker in the paid group must be paid at least their minimum wage expectation. In the group, each worker’s pay must be directly proportional to their quality. This means if a worker’s quality is double that of another worker in the group, then they must be paid twice as much as the other worker. Given the integer k, return the least amount of money needed to form a paid group satisfying the above conditions. Answers within $10^{-5}$ of the actual answer will be accepted. ...

Problem You are given an array happiness of length n, and a positive integer k. There are n children standing in a queue, where the ith child has happiness value happiness[i]. You want to select k children from these n children in k turns. In each turn, when you select a child, the happiness value of all the children that have not been selected till now decreases by 1. Note that the happiness value cannot become negative and gets decremented only if it is positive. ...

Problem You are given an integer array score of size n, where score[i] is the score of the ith athlete in a competition. All the scores are guaranteed to be unique. The athletes are placed based on their scores, where the 1st place athlete has the highest score, the 2nd place athlete has the 2nd highest score, and so on. The placement of each athlete determines their rank: ...

Problem Given that integers are read from a data stream. Find median of elements read so for in efficient way. OR Numbers are randomly generated and passed to a method. Write a program to find and maintain the median value as new values are generated. OR You are given a stream of numbers which can be positive or negative. You are required to provide an operation FIND MEDIAN..which when invoked should be able return the median of the numbers in stream(in say O(1) time) ...

Problem You are given an array of k linked-lists lists, each linked-list is sorted in ascending order. Merge all the linked-lists into one sorted linked-list and return it. Examples 1 -> 10 -> 20 4 -> 11 -> 13 3 -> 8 -> 9 will result in 1 -> 3 -> 4 -> 8 -> 9 -> 10 -> 11 -> 13 -> 20 ...

Problem Alice has some number of cards and she wants to rearrange the cards into groups so that each group is of size groupSize, and consists of groupSize consecutive cards. Given an integer array hand where hand[i] is the value written on the ith card and an integer groupSize, return true if she can rearrange the cards, or false otherwise. This question is the same as Leetcode 1296: https://leetcode.com/problems/divide-array-in-sets-of-k-consecutive-numbers/, which states: ...

Problem Given an integer array nums and an integer k, return the kth largest element in the array. Note that it is the kth largest element in the sorted order, not the kth distinct element. Example 1: Input: nums = [3,2,1,5,6,4], k = 2 Output: 5 Example 2: Input: nums = [3,2,3,1,2,4,5,5,6], k = 4 Output: 4 ...

Problem You are given an array of integers nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position. Return the max sliding window. Sometimes k is also denoted as w. Example Example ...

Problem You are given an array of integers stones where stones[i] is the weight of the ith stone. We are playing a game with the stones. On each turn, we choose the heaviest two stones and smash them together. Suppose the heaviest two stones have weights x and y with x <= y. The result of this smash is: If x == y, both stones are destroyed, and If x != y, the stone of weight x is destroyed, and the stone of weight y has new weight y - x. At the end of the game, there is at most one stone left. ...

Problem Given an integer n, return the nth ugly number. Ugly Number Definition Examples Example 1: Input: n = 10 Output: 12 Explanation: [1, 2, 3, 4, 5, 6, 8, 9, 10, 12] is the sequence of the first 10 ugly numbers. Example 2: Input: n = 1 Output: 1 Explanation: 1 has no prime factors, therefore all of its prime factors are limited to 2, 3, and 5. ...