| Problem Names | Solution Writeups | Code |
|---|---|---|
| k-th Largest Element In a Stream |
Create a priority queue and maintain it at size k so that top element is the kth largest element. To do this, first push all numbers into the priority queue and keep popping until pq.size() <= k. |
|
| Last Stone Weight |
Create min heap and keep popping two largest stones until remaining stone is 1 or 0. |
|
| K Closet Points To Origin |
Create min heap, calculate distance then insert into min heap using pair data structure, then keep popping until k elements are popped. |
|
| Task Scheduler |
Task with largest count has highest priority, create max heap for it. Create another queue that will add back remaining task with its next available time, using data structure like pair(task_count_remaining, next_available_time). While max heap or the queue is not empty, should +1 to count. Even if not any task can be added back to max heap, we should +1, indicates idle. |
|
| Design Twitter |
Create a hash table that maps a user to a set of his/her followees. Create another array that stores all posts by all users, and then the latest posts are guaranteed to be at the last index. When getPost is called, filter only followees' posts and the user's own post, keep at 10 posts only. |
|
| Find Median from Data Stream |
The goal is to get O(1) findMedian. To do this, we can have two heaps, one is min heap and one is max heap. All values in max heap must smaller than min heap, and abs(max_heap.size() - min_heap.size()) <= 1. By default, insert to max heap, and then check if any condition is violated, move max from max heap to min heap, or move min from min heap to max heap. To find median, if max_heap.size == min_heap.size, median = (max_heap.top() + min_heap.top()) / 2, else median = top of the larger size heap. |