Compute minimum delivery days
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Take-home Project
##### Question
Given N distribution centers numbered 1..N and an orderCityList of length M where orderCityList[i] denotes the city that the i-th order must be delivered to, you may schedule deliveries over multiple days under the following rules:
Each day, every center can work on at most one destination city.
If a center’s own number equals the destination city’s number, the center can deliver all remaining orders for that city in that single day.
If a center’s number differs from the destination city’s number, that center needs two consecutive days to finish delivering all remaining orders for that city (the center is occupied on both days).
Return the minimum number of calendar days required to deliver all orders in orderCityList.
Quick Answer: This question evaluates algorithmic problem-solving skills focused on scheduling, resource allocation, and simulation of constrained delivery processes, testing the ability to model workload distribution and temporal constraints.
There are N distribution centers numbered 1..N and an order list orderCityList of length M, where orderCityList[i] is the city number that the i-th order must be delivered to. You schedule deliveries over consecutive calendar days under these rules:
- Each day, every center can work on at most one destination city.
- If a center's own number equals the destination city's number, that center can deliver all remaining orders for that city in that single day (a 1-day job on its dedicated center).
- If a center's number differs from the destination city's number, that center needs two consecutive days to finish all remaining orders for that city, and the center is occupied on both days (a 2-day job that can run on any center).
A city is fully served once any single center has run the appropriate job (1-day matched job, or 2-day foreign job) for it; the number of duplicate orders for the same city does not change the cost. Return the minimum number of calendar days required to deliver all orders in orderCityList.
Implement: minDeliveryDays(N, orderCityList) -> int.
Example: N=2, orderCityList=[1,2,3,4]. Cities 1 and 2 each have a dedicated center (1-day jobs); cities 3 and 4 have no center and need 2-day jobs that must share the 2 centers. The optimal schedule finishes in 3 days.
Constraints
- 1 <= N (number of distribution centers)
- 0 <= M (length of orderCityList)
- Each orderCityList[i] is a positive integer city number; it may or may not fall within 1..N.
- Multiple orders for the same city collapse to a single delivery job.
- Foreign (non-matching) deliveries occupy a center for two consecutive days.
Examples
Input: (3, [1, 2, 3])
Expected Output: 1
Explanation: Cities 1, 2, 3 each have a matching center, so all three are delivered in parallel on day 1.
Input: (2, [1, 2])
Expected Output: 1
Explanation: Both cities use their own centers (1-day jobs) simultaneously on day 1.
Hints
- Only the SET of distinct cities matters. Duplicate orders for the same city are finished by one job, so the count of orders per city does not affect the answer.
- Split distinct cities into two groups: 'own' cities whose number is in 1..N (finishable in 1 day on their dedicated center) and 'foreign' cities (each needs 2 consecutive days on any center).
- All 'own' cities can be served in parallel on distinct dedicated centers, so they alone never need more than 1 day. The bottleneck is fitting the 2-day foreign jobs onto N centers.
- Binary-search or linearly scan the number of days T: in T days a free center can complete T//2 foreign jobs, while a center that must also serve its own matched city can complete (T-1)//2 foreign jobs. Pick the smallest T whose total capacity covers all foreign jobs.