Greedy, Heaps, And Scheduling Optimization
Asked of: Software Engineer
Last updated

What's being tested
These problems test greedy choice, priority-queue invariants, and efficient array reasoning under ordering constraints. Interviewers are probing whether you can replace brute-force scans or pairings with O(n log n) or O(n) structures, justify correctness, and handle duplicates, empty inputs, and boundary cases cleanly.
Patterns & templates
-
Monotonic stack for nearest-smaller relationships —
O(n)time,O(n)space; decide strict<versus<=before coding duplicates. -
Fenwick tree or segment tree for rightmost-smaller queries — coordinate-compress values, store max index, query values
< a[i]inO(log n). -
Two heaps for streaming median — max-heap lower half, min-heap upper half; rebalance after every
addNum()to keep sizes within one. -
Greedy resource allocation — sort counts/capacities, consume smallest feasible requirement first; prove exchange argument, not just “seems optimal.”
-
Heap scheduling template — sort events by start time, push active candidates into
heapq, pop expired or highest-priority item; usuallyO(n log n). -
Pairing optimization — sort both sides or sort by constraint then use a heap; watch whether objective is max sum, min operations, or feasibility.
-
Range-update minimization — reason on adjacent differences, not full arrays; difference arrays often turn repeated interval operations into linear accounting.
Common pitfalls
Pitfall: Treating “nearest smaller” and “rightmost smaller” as the same problem; the former is usually stack-based, the latter often needs indexed value queries.
Pitfall: Using Python
heapqas a max-heap without negating priorities, or forgetting tie-breaking when equal priorities affect deterministic output.
Pitfall: Giving a greedy algorithm without a correctness argument; state the invariant or exchange proof before moving to implementation details.
Practice these
The practice cards below cover the canonical variants — solve all of them and time yourself.
Featured in interview prep guides
Practice questions
- Minimize Branch Merge ConflictsAmazon · Software Engineer · Take-home Project · hard
- Compute minimal operations and optimal server pairingAmazon · Software Engineer · Take-home Project · easy
- Minimize operations to reduce price differenceAmazon · Software Engineer · Take-home Project · hard
- Maximize memory capacity with primary-backup serversAmazon · Software Engineer · Take-home Project · hard
- Maximize total bandwidth of data channel pairsAmazon · Software Engineer · Take-home Project · hard
- Find minimum days to deliver all ordersAmazon · Software Engineer · Take-home Project · Medium
- Maximize optional tasks under daily limitAmazon · Software Engineer · Take-home Project · Medium
- Compute rightmost-smaller delay timesAmazon · Software Engineer · Take-home Project · Medium
- Design faster delay-time computationAmazon · Software Engineer · Take-home Project · Medium
- Place items into earliest fitting binsAmazon · Software Engineer · Technical Screen · Medium
- Select maximum tasks before deadlinesAmazon · Software Engineer · Technical Screen · Medium
- Design a streaming median structureAmazon · Software Engineer · Onsite · Medium
Related concepts
- Greedy Algorithms And Priority QueuesCoding & Algorithms
- Dynamic Programming, Scheduling, And Set CoverCoding & Algorithms
- Heaps, Top-K, And Streaming SelectionCoding & Algorithms
- Pricing, Demand, And Capacity OptimizationAnalytics & Experimentation
- Heaps And Selection AlgorithmsCoding & Algorithms
- Dynamic Programming, Backtracking, And Combinatorial SearchCoding & Algorithms