Maximize points with limited coworker skips
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Take-home Project
You and a coworker must unload a sequence of warehouses. For warehouse i there are c[i] items (non‑negative integers). Turns alternate starting with you: on your turn you remove exactly m items; on the coworker’s turn they remove exactly n items (m,n are positive integers). If your move empties a warehouse (i.e., the last removal that makes its remaining items ≤ 0 is yours), you earn 1 point for that warehouse; otherwise you earn 0. You must alternate turns, except you may spend up to k total skip tokens across all warehouses: spending one token on the coworker’s upcoming turn causes them to skip that turn and you immediately take the next turn instead; skips may be used multiple times on the same warehouse or spread across warehouses, but the total number of skips used across all warehouses must be ≤ k. Determine the maximum total points you can earn, and design an algorithm to compute it efficiently. State the time and space complexity.
Quick Answer: This question evaluates algorithmic problem-solving and optimization under sequential-turn constraints, testing competency in dynamic programming, combinatorial reasoning, and time/space complexity analysis.
You and a coworker unload a sequence of warehouses. Warehouse i starts with `c[i]` items (a non-negative integer). Turns alternate, starting with you: on your turn you remove exactly `m` items; on the coworker's turn they remove exactly `n` items (`m, n` are positive integers). If the move that brings a warehouse's remaining items to `<= 0` is YOURS, you earn 1 point for that warehouse; otherwise you earn 0.
You must alternate turns, except that you may spend skip tokens. Spending one token on the coworker's upcoming turn makes them skip that turn, and you immediately take the turn instead (after which the coworker is again scheduled next, and you may skip again). Skips may be used multiple times on the same warehouse or spread across warehouses, but the total number of skips used across ALL warehouses must be `<= k`.
Return the maximum total number of points you can earn.
Implement `solution(c, m, n, k)` where `c` is the list of warehouse item counts, `m` is your removal amount, `n` is the coworker's removal amount, and `k` is the global skip budget.
Example: `c = [2, 4, 6, 2, 4, 7]`, `m = 2`, `n = 3`, `k = 0` -> `4` (you finish warehouses 2, 6, 2, and 7 with no skips). With `k = 3` -> `6` (one skip each lets you also steal the two warehouses with 4 items).
Constraints
- 0 <= len(c)
- 0 <= c[i] (non-negative item counts; an already-empty warehouse yields no point)
- m >= 1 and n >= 1 (positive removal amounts)
- 0 <= k (total skip tokens shared across all warehouses)
Examples
Input: ([2, 4, 6, 2, 4, 7], 2, 3, 0)
Expected Output: 4
Explanation: With no skips you finish warehouses with 2, 6, 2, and 7 items yourself (e.g. 6: you 6->4, coworker ->1, you ->win), so 4 points.
Input: ([2, 4, 6, 2, 4, 7], 2, 3, 3)
Expected Output: 6
Explanation: The two warehouses with 4 items each need exactly 1 skip to steal; with k=3 you can afford both (1+1=2 <= 3) on top of the four free wins, for all 6 points.
Hints
- Each warehouse is independent except that all warehouses draw skip tokens from the same global budget k, and winning any warehouse is worth exactly +1 point. So first compute, per warehouse, the MINIMUM skips needed to win it, then greedily buy the cheapest wins until k runs out.
- For one warehouse, search over the turn sequence: on your turn you remove m; on the coworker's scheduled turn you either let them remove n (free) or spend one skip to remove m yourself. You only ever need to skip when letting the coworker play would let THEM empty the warehouse, but a Dijkstra/BFS over (remaining, whose-turn) minimizing skips captures every case cleanly.
- Be careful not to greedily return the first finishing move you find: a path that lets the coworker play once more can sometimes reach a win with FEWER skips. Only declare a win when you pop a remaining<=0 state from a min-skips priority queue, never inside the relaxation step.