Solve Shipping and Bundle-Cost Problems
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
Quick Answer: This question evaluates algorithmic reasoning for scheduling and capacity planning (minimum daily shipping capacity) and combinatorial optimization with constrained purchases (bundle-cost minimization).
Minimum Daily Shipping Capacity
Constraints
- weights are positive
Examples
Input: ([1, 2, 3, 1, 1], 4)
Expected Output: 3
Explanation: Capacity 3 ships in four days.
Input: ([3, 2, 2, 4, 1, 4], 3)
Expected Output: 6
Explanation: Capacity 6.
Input: ([10], 1)
Expected Output: 10
Explanation: Single package.
Hints
- Binary-search capacity with a greedy day counter.
Minimum Cost with Bundle Offers
Constraints
- Oversupply is not allowed
Examples
Input: ([2, 5], [[3, 0, 5], [1, 2, 10]], [3, 2])
Expected Output: 14
Explanation: Classic shopping offers.
Input: ([2, 3, 4], [[1, 1, 0, 4], [2, 2, 1, 9]], [1, 2, 1])
Expected Output: 11
Explanation: Use a mix of offers and units.
Input: ([5], [], [3])
Expected Output: 15
Explanation: No offers.
Hints
- Memoize by remaining needs; unit purchases are the fallback.