Kth Largest Element in a Stream
Explore how to implement a KthLargest class in Go that dynamically manages a stream of scores and returns the kth highest score after each addition. Learn to solve real-time top-k element challenges with efficient data handling and maintain performance within given constraints.
We'll cover the following...
Statement
You are part of a university admissions office that needs to dynamically track the kth 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 kth highest score among all scores received so far, i.e., the score that would appear in the
Implement the KthLargest class:
Constructor: Initializes the object with the integer
kand the initial stream of test scoresnums.int add(int val): This function adds a new test score
valto the stream and returns thekthhighest score among all scores seen so far.
Constraints:
-
nums.length -
nums[i] -
value - At most, calls will be made to add.
- It is guaranteed that there will be at least elements in the array when you search for the element.
Examples
Understand the problem
Let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:
Kth Largest Element in a Stream
KthLargest (2, [10, 7, 11, 5])
What does the call add(12) return?
Figure it out!
We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.
Try it yourself
Implement your solution in main.go in the following coding playground. We have provided some useful code templates in the other file that you may build on to solve this problem.
package maintype KthLargest struct {// Write your code here}// KthLargestInit is a constructor to initialize heap and store values in itfunc (this *KthLargest) KthLargestInit(k int, nums []int) {// Write your code here}// Add function adds element in the heapfunc (this *KthLargest) add(value int) int {// Write your code herereturn -1}