Kth largest element in a stream of running integers
AppleThe problem
Implement a class **KthLargest **to find the k****th **largest **number in a stream. It should have the following methods:
- KthLargest(int k, int [] nums) Initializes the object with the integer k and the initial stream of numbers in nums
- int add(int val) Appends the integer **val **to the stream and returns the k****th largest element in the stream. Note that it is the k****th largest element in the sorted order, not the k****th distinct element.
Input: [KthLargest(3, [1, 2, 3, 4]), add(5), add(2), add(7)] Output: [null, 3, 3, 4] Explanation: initial stream = [1, 2, 3, 4], k = 3. add(5): stream = [1, 2, 3, 4, 5] -> returns 3 add(2): stream = [1, 2, 2, 3, 4, 5] -> returns 3 add(7): stream = [1, 2, 2, 3, 4, 5, 7] -> returns 4
Input: [KthLargest(2, [5, 5, 5, 5], add(2), add(6), add(60)] Output: [null, 5, 5, 6] Explanation: initial stream = [5, 5, 5, 5], k = 2. add(2): stream = [5, 5, 5, 5, 2] -> returns 5 add(6): stream = [5, 5, 5, 5, 2, 6] -> returns 5 add(60): stream = [5, 5, 5, 5, 2, 6, 60] -> returns 6
Input: [KthLargest(4, [5, 1, 2, 7], add(8), add(2), add(6)]
- 1 <= Number of instructions <= 1000
- -104 <= val & all initial values <= 104
- 1 <= k <= 104
- k - 1 <= nums.length <= 103
- The stream will have at least k elements after any add call.
cpp
class KthLargest {
public:
KthLargest(int k, vector<int>& nums) {
}
int add(int val) {
}
};java
class KthLargest {
public KthLargest(int k, int[] nums) {
}
public int add(int val) {
}
}python
class KthLargest:
def __init__(self, k, nums):
def add(self, val):javascript
class KthLargest {
constructor(k, nums) {
}
add(val) {
}
}csharp
class KthLargest
{
public KthLargest(int k, int[] nums)
{
}
public int Add(int val)
{
return 0;
}
}go
type KthLargest struct {
}
func Constructor(k int, nums []int) *KthLargest {
}
func (kl *KthLargest) Add(val int) int {
}Stuck? Show a way to structure it+
- 01Clarify whether output is needed after every insertion
- 02Create a min-heap of capacity k
- 03Push each value and pop when size exceeds k
- 04Read the root when size is k
Reference answer
Then expect these follow-ups
How would you maintain the kth smallest instead?
Tests: follow-up reasoning
What is the time per update?
Tests: complexity analysis
Hiring now
Get the Apple interview, not just the prep
landed applies to roles like these for you, on each company’s own site, with answers written for the role.
Next question