Greedy Algorithms And Priority Queues
Asked of: Software Engineer
Last updated

What's being tested
These problems test greedy choice validation, priority queue design, and stateful data-structure updates under ordering constraints. You need to show why the local choice is safe, choose the right heap/tree/map representation, and handle ties, partial updates, and edge cases deterministically.
Patterns & templates
-
Max-heap selection with unlock constraints — sort by requirement, push feasible profits into
heapq; each step picks best available inO(n log n). -
Min-heap tree construction —
Huffman-style merge by frequency; include deterministic tie-breakers like(freq, symbol_id, node_id)to avoid ambiguous encodings. -
Price-time priority matching — maintain buy/sell books using heaps plus FIFO queues; best price wins, then earliest timestamp, with partial fills preserved.
-
Greedy proof template — state invariant, prove exchange argument, then show each chosen item cannot make a better future solution impossible.
-
Heap deletion gotcha —
heapqlacks efficient arbitrary removal; use lazy deletion, indexed heaps, or balanced maps depending on update/cancel requirements. -
Grid escape with time constraints — model as shortest path/BFS/Dijkstra over
(row, col, time); avoid greedy moves unless monotonicity is proven. -
Complexity discipline — aim for
O(n log n)for selection/tree/order-book operations; explain whenO(n^2)scans will fail.
Common pitfalls
Pitfall: Picking the highest-profit project before checking capital feasibility breaks the greedy invariant; only choose among currently unlocked candidates.
Pitfall: Building a frequency tree without stable tie-breaking can produce correct-looking but non-reproducible encode/decode behavior.
Pitfall: Treating an order book as “sort all orders after every event” is usually too slow; maintain incremental priority structures instead.
Practice these
The practice cards below cover the canonical variants — solve all of them and time yourself.
Featured in interview prep guides
Practice questions
Related concepts
- Greedy, Heaps, And Scheduling OptimizationCoding & Algorithms
- Heaps, Top-K, And Streaming SelectionCoding & Algorithms
- Heaps, Priority Queues, and Top-K SelectionCoding & Algorithms
- Top-K Selection, Heaps, And RankingCoding & Algorithms
- Heaps And Selection AlgorithmsCoding & Algorithms
- Dynamic Programming, Scheduling, And Set CoverCoding & Algorithms