Kth Largest Element in a Stream

EasyHeapheap

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

Scores arrive one at a time and after each arrival you must report the k-th largest score seen so far. The ranking counts duplicates separately: in [5, 5, 3] the 1st and 2nd largest are both 5. Implement: - KthLargest(k, nums) stores k and the initial scores nums (which may be empty). - add(val) inserts val into the stream and returns the k-th largest value among everything inserted so far (including nums). It is guaranteed that at least k values exist whenever add returns. Each add should run in O(log k).

Examples

Input: ["KthLargest","add","add","add","add"] [[2,[5,1,8]],[3],[10],[9],[7]]
Output: [null,5,8,9,9]
With k = 2: after adding 3 the values are {5,1,8,3}, second largest 5. Adding 10 makes it 8, adding 9 makes it 9, and adding 7 leaves it at 9.
Input: ["KthLargest","add","add","add"] [[1,[]],[-4],[-7],[2]]
Output: [null,-4,-4,2]
With k = 1 the answer is simply the maximum so far: -4, still -4, then 2.

Constraints

  • 1 <= k <= 10^4
  • 0 <= nums.length <= 10^4
  • -10^4 <= nums[i], val <= 10^4
  • At most 10^4 calls to `add`.
  • At least `k` values exist after every `add`.

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.

More heap problems