Maximize credits with limited skips
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Take-home Project
You are given n warehouses with inventories inventory[0..n-1], and two dispatch amounts: you dispatch dispatch1 units first each turn, then your co-worker dispatches dispatch2 units. Your co-worker may skip their turn a total of at most skips times across all warehouses; when they skip, you immediately take the next dispatch instead. For a warehouse i, a credit is earned only if the warehouse becomes empty (inventory[i] <=
0) immediately after your dispatch on that warehouse. Determine the maximum total number of credits achievable over all warehouses by optimally choosing when the co-worker skips. Return an integer. Constraints: 1 <= n <= 1e5; 1 <= inventory[i], dispatch1, dispatch2, skips <= 1e9. Describe the algorithm and its time and space complexity, and implement getMaximumCredits(inventory, dispatch1, dispatch2, skips).
Quick Answer: This question evaluates algorithm design and optimization skills in resource allocation under constraints, focusing on decision-making to maximize credits when turn-taking and limited skips affect processing.
For each warehouse, compute skips needed so your dispatch empties it, then maximize credits under the skip budget.
Constraints
- Inputs are Python literals matching the function signature.
- Return a deterministic exact-match value.
Examples
Input: ([10,20,30], 5, 5, 1)
Expected Output: 1
Explanation: One skip can save one otherwise-lost warehouse.
Input: ([4,8,12], 5, 3, 0)
Expected Output: 2
Explanation: Some credits require no skips.
Input: ([100], 10, 10, 100)
Expected Output: 1
Explanation: Enough skips for one warehouse.
Hints
- Model object-style prompts as arrays or operation streams when needed.
- Handle empty and boundary cases before the main logic.