How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Take-home Project rounds at Amazon.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Amazon during technical interviews.

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.

Input: ([], 3, 2, 5)

Expected Output: 0

Explanation: No warehouses means no points regardless of the skip budget.

Input: ([5], 2, 3, 0)

Expected Output: 0

Explanation: You 5->3, coworker 3->0 empties it (their move), so you score nothing and have no skips to steal it.

Input: ([5], 2, 3, 1)

Expected Output: 0

Explanation: Even with a skip, the warehouse cannot be won within budget along a winning path here, so 0 points.

Input: ([1], 5, 5, 0)

Expected Output: 1

Explanation: Your very first move removes 5 >= 1 item, emptying the warehouse, so you earn the point with no skips.

Input: ([0, 0, 3], 3, 1, 0)

Expected Output: 1

Explanation: Empty warehouses yield no points; the warehouse with 3 items is emptied by your first move (3->0), so 1 point.

Input: ([10, 10, 10], 3, 4, 2)

Expected Output: 3

Explanation: Each 10-item warehouse can be won with 0 skips (3 your-moves of 3 plus coworker moves land the finishing blow on you), so all 3 points come for free and the budget is unused.

Input: ([7], 1, 1, 10)

Expected Output: 1

Explanation: With m=n=1 the parity works out so a your-move can be made to land last (using skips if needed within the generous budget), earning the point.

Input: ([100], 7, 9, 0)

Expected Output: 1

Explanation: A single large warehouse can be finished by one of your moves with no skips needed, so 1 point.

Input: ([8, 8, 7], 6, 1, 1)

Expected Output: 3

Explanation: Large your-removal (m=6) lets you finish all three warehouses cheaply; with one skip available you secure all 3 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.

Quick Overview

This question evaluates algorithmic problem-solving and optimization under sequential-turn constraints, testing competency in dynamic programming, combinatorial reasoning, and time/space complexity analysis.