Grokking the Coding Interview Patterns in C++/

...

Solution: Kth Largest Element in a Stream

Let's solve the Kth Largest Element in a Stream problem using the Top K Elements pattern.

We'll cover the following...

Statement
Solution
- Naive approach
- Optimized approach using Top K Elements

Statement

You are part of a university admissions office that needs to dynamically track the k^th highest test score among applicants in real time. This functionality is critical for determining cutoff marks for interviews and admissions as new applicants continue to submit their scores.

You need to implement a class that, given an integer, k, manages a continuous stream of test scores. Each time a new score is added, the class should return the k^th highest score among all scores received so far, i.e., the score that would appear in the $k^{th}$ position if the scores were sorted in descending order.

Implement the KthLargest class:

Constructor: Initializes the object with the integer k and the initial stream of test scores nums.
int add(int val): This function adds a new test score val to the stream and returns the k^th highest score among all scores seen so far.