PPractick

The problem

A game server keeps a live high-score board and must report the k-th highest score after every new score arrives: it's the cutoff for the top-k badge. Re-sorting after each score is wasteful. Keep a min-heap of the k largest scores seen so far. Its root is the k-th largest. A new score enters only if it beats the root (or the heap has fewer than k scores), and then the root is evicted. Each update costs O(log k).

Example: KthLargest(3, [4, 5, 8, 2]): add(3) → 4, add(5) → 5, add(10) → 5, add(9) → 8, add(4) → 8.

Function signature

class KthLargest {
public:
    KthLargest(int k, const vector<int>& nums);
    int add(int val);   // returns the k-th largest after adding val
};

Test cases

Operations	Output	Explanation
KthLargest(3, [4,5,8,2]), add 3, 5, 10, 9, 4	4 5 5 8 8	LeetCode's example
KthLargest(1, []), add −3, −2, −4, 0, 4	-3 -2 -2 0 4	k = 1 is the running maximum
KthLargest(2, [0]), add −1, 1, −2, −4, 3	-1 0 0 0 1	Starts with fewer than k elements

(Confirm: after every add there are at least k elements in total; duplicates count separately.)

How interviewers phrase it

• "Design a class to find the kth largest element in a stream" (LeetCode 703).

Clarifying questions to ask

1. The k-th largest counting duplicates? (Yes.)
2. Can the initial array have fewer than k elements? (Yes, but every add returns once k are available.)
3. How many adds? (Up to 10⁴: O(log k) each.)

Follow-ups to expect

1. "Why a min-heap of size k?"
2. "What does add do?"
3. "What about the initial array?"
4. "What if k changes or deletions happen?"
5. "Complexity?"

Related questions

• Find Median from Data Stream Hard
• Design Twitter Medium
• Minimize Max Distance to Gas Station Hard
• Implement Min Stack Hard
• LFU Cache Hard
• Merge K sorted Lists Hard

All 474 dsa interview questions

DSA mock interviews · System design interview questions · Free mock interview practice · Browse interviewers · Sign in