Grokking the Coding Interview: Patterns for Coding Questions

0% completed

​

Kth Largest Number in a Stream (medium)

Problem Statement

Design a class to efficiently find the Kth largest element in a stream of numbers.

The class should have the following two things:

  1. The constructor of the class should accept an integer array containing initial numbers from the stream and an integer ‘K’.
  2. The class should expose a function add(int num) which will store the given number and return the Kth largest number.

Example 1:

Input: [3, 1, 5, 12, 2, 11], K = 4
1. Calling add(6) should return '5'.
2. Calling add(13) should return '6'.
2. Calling add(4) should still return '6'.

Constraints:

.....

.....

.....

Like the course? Get enrolled and start learning!
F

First

· 4 years ago

// if heap has more than 'k' numbers, remove one number if (this.minHeap.length > this.k) { this.minHeap.pop(); } How does this loop enough times to pop the minHeap if this is an if statement?

Show 2 replies
U

Utkarsh Gupta

· 3 years ago

Time Complexity of alternative approach would be O(N log(N)). Insertion takes O(logN) time. In the alternate approach we are first inserting all the numbers into the heap which would result in O(Nlog(n)).

B

Baraa Attabbaa

· 3 years ago

Initializing the min-heap with all numbers will take O(N)

Show 1 reply