Understand what the interviewer is asking for by using test cases and questions about the problem.
- Established a set (2-3) of test cases to verify their own solution later.
- Established a set (1-2) of edge cases to verify their solution handles complexities.
- Have fully understood the problem and have no clarifying questions.
- Have you verified any Time/Space Constraints for this problem?
HAPPY CASE
Input
["KthLargest", "add", "add", "add", "add", "add"]
[[3, [4, 5, 8, 2]], [3], [5], [10], [9], [4]]
Output
[null, 4, 5, 5, 8, 8]
Explanation
KthLargest kthLargest = new KthLargest(3, [4, 5, 8, 2]);
kthLargest.add(3); // return 4
kthLargest.add(5); // return 5
kthLargest.add(10); // return 5
kthLargest.add(9); // return 8
kthLargest.add(4); // return 8
Input
["KthLargest", "add", "add", "add", "add", "add"]
[[3,[4,5,8,2]],[10],[15],[10],[30],[4]]
Output
[null,5,8,10,10,10]
Explanation
KthLargest kthLargest = new KthLargest(3, [4, 5, 8, 2]);
kthLargest.add(10); // return 5
kthLargest.add(15); // return 8
kthLargest.add(10); // return 10
kthLargest.add(10); // return 10
kthLargest.add(10); // return 10
EDGE CASE (Multiple Spaces)
Input
KthLargest kthLargest = new KthLargest(1, [4, 5, 8, 2]);
Output
[null,10,15,15,15,15]
kthLargest.add(10); // return 10
kthLargest.add(15); // return 15
kthLargest.add(10); // return 15
kthLargest.add(10); // return 15
kthLargest.add(10); // return 15
Match what this problem looks like to known categories of problems, e.g. Linked List or Dynamic Programming, and strategies or patterns in those categories.
For Array/Strings, common solution patterns include:
Plan the solution with appropriate visualizations and pseudocode.
General Idea: Create a min-heap and limit it's size to k. The first element will be the kth largest element
1) Create heap
2) Limit heap to size k
3) Upon add(val), add new val to heap
4) Remove k + 1 largest val from heap
5) Return kth largest val in heap
⚠️ Common Mistakes
Implement the code to solve the algorithm.
class KthLargest:
def __init__(self, k: int, nums: List[int]):
# Create heap
self.heap = nums
heapq.heapify(self.heap)
# Limit heap to size k
while len(self.heap) > k:
heapq.heappop(self.heap)
def add(self, val: int) -> int:
# Upon add(val), add new val to heap
heapq.heappush(self.heap, val)
# Remove k + 1 largest val from heap
heapq.heappop(self.heap)
# Return kth largest val in heap
return self.heap[0]
class KthLargest {
// Create heap
private PriorityQueue<Integer> minHeap = new PriorityQueue<>();
private int k;
public KthLargest(int k, int[] nums) {
this.k = k;
for (int i: nums) {
minHeap.add(i);
// Limit heap to size k
if (minHeap.size() > k) {
minHeap.poll();
}
}
}
public int add(int val) {
// Upon add(val), add new val to heap
minHeap.add(val);
// Remove k + 1 largest val from heap
if (minHeap.size() > k) {
minHeap.poll();
}
// Return kth largest val in heap
return minHeap.peek();
}
}
/**
* Your KthLargest object will be instantiated and called as such:
* KthLargest obj = new KthLargest(k, nums);
* int param_1 = obj.add(val);
*/
Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.
Evaluate the performance of your algorithm and state any strong/weak or future potential work.
Assume N
represents the number of items in array and K
represents the number of items in the heap.
K
items in the heap