Learning Outcome
Top K, two heaps, scheduling, merge streams, and event selection.
Pattern Recognition
| Item | Detail |
|---|---|
| Core signal | A known interview family appears and the constraints reward the standard pattern. |
| Use when | Use a heap when the next item to process is always the smallest, largest, earliest, or most urgent candidate. |
| Avoid when | The required invariant is not monotonic or the input constraints point to a simpler direct scan. |
Intuition
Use a heap when the next item to process is always the smallest, largest, earliest, or most urgent candidate.
Exact Practice Question Names
- Top K Frequent Elements
- K Closest Points to Origin
- Find Median from Data Stream
- Meeting Rooms III
- Merge K Sorted Lists
- Single-Threaded CPU
Interview Approach
- Name the exact family.
- Write the invariant or state.
- Pick the standard container or recurrence.
- Dry-run the smallest example.
- State complexity and one follow-up.
Pseudocode
identify pattern
initialize state/container
for each input unit:
update state safely
update answer when invariant is valid
return answerSample Dry Run
Take the smallest Heap / Priority Queue example, track the state after every operation, and verify the final answer before coding.
Edge Cases
- Empty or single-item input
- Duplicate values
- Boundary constraints
- Large values requiring long/int64
Common Mistakes
- Memorizing code without naming the invariant
- Skipping the brute-force baseline
- Not explaining why the optimized approach is correct
Complexity
| Item | Detail |
|---|---|
| Expected time | Usually O(n log n), O(V + E), or states times transitions depending on the family. |
| Expected space | Usually O(n), O(V + E), or number of DP states. |
Java, C++ and Python Notes
- Java: prefer explicit classes and clear helper methods over clever one-liners.
- C++: use vector, unordered_map, set, priority_queue, and long long when sums can grow.
- Python: keep state readable with dict, set, deque, heapq, and lru_cache where appropriate.
Quick Revision Checklist
- Name the pattern before coding.
- State the invariant or DP state in one sentence.
- Dry-run the smallest non-trivial example.
- Close with time and space complexity.