Software Engineer

To solve the question using a max heap, make a max heap of all the elements of the list. Run a loop for k-1 times and remove the top element of the heap. After running the loop, the element at top will be the kth largest element, return that. Time Complexity : O(n + klogn)

The question can also be solved using a min heap. 
 

Approach :
 

1. Create a min heap class with a capacity of k
 

2. When the heap reaches capacity eject the minimum number. 
 

3. Loop over the array and add each number to the heap. 
 

4. At the end, the largest k number of elements will be left in the heap, the smallest of them being at the top of the heap, which is the kth largest number
 

The time complexity for this solution is O(N logK).

BFS can be used here. 
Algorithm : 

1. Create an empty queue Q. 
 

2. Find all rotten oranges and enqueue them to Q. Also, enqueue a delimiter to indicate the beginning of the next time frame.
 

3. Run a loop While Q is not empty
 

4. Do following while delimiter in Q is not reached
4.1. Dequeue an orange from the queue, rot all adjacent oranges. While rotting the adjacent, make sure that the time frame is incremented only once. And the time frame is not incremented if there are no adjacent oranges.
 

4.2. Dequeue the old delimiter and enqueue a new delimiter. The oranges rotten in the previous time frame lie between the two delimiters.
 

Time Complexity: O(N*M)
Space Complexity: O(N*M)

Tip 1 : Firstly, remember that the system design round is extremely open-ended and there’s no such thing as a standard answer. Even for the same question, you’ll have a totally different discussion with different interviewers.

Tip 2 : Before you jump into the solution always clarify all the assumptions you’re making at the beginning of the interview. Ask questions to identify the scope of the system. This will clear the initial doubt, and you will get to know what are the specific detail interviewer wants to consider in this service.