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.

Compute minimum delivery days | Amazon Coding Question

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.

Input: (1, [2])

Expected Output: 2

Explanation: City 2 has no center (only center 1 exists), so center 1 needs two consecutive days to finish it.

Input: (2, [3, 4])

Expected Output: 2

Explanation: Two foreign cities and two centers: both 2-day jobs start on day 1 and finish on day 2.

Input: (1, [2, 3])

Expected Output: 4

Explanation: One center, two foreign cities. Each foreign job takes 2 days and they run sequentially: 2 + 2 = 4 days.

Input: (3, [4, 5, 6, 7])

Expected Output: 4

Explanation: Four foreign cities, three centers. Three jobs finish in days 1-2, the fourth in days 3-4: 2*ceil(4/3) = 4.

Input: (2, [2, 3])

Expected Output: 2

Explanation: City 2 is served by its own center (day 1); city 3 is foreign and runs on the other center across days 1-2, giving 2 days total.

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

Expected Output: 3

Explanation: Cities 1 and 2 are matched (1-day each); cities 3 and 4 are foreign 2-day jobs that must share two centers also needed for matches, so the optimal schedule completes in 3 days.

Input: (4, [4, 4, 4, 1, 1])

Expected Output: 1

Explanation: Distinct cities are {4, 1}, both within 1..4, so both are matched 1-day jobs done in parallel on day 1; duplicate orders do not add time.

Input: (3, [10])

Expected Output: 2

Explanation: City 10 is far outside 1..3, so it is a single foreign job taking two consecutive days.

Input: (5, [1, 2, 3, 4, 5, 6, 7, 8, 9, 10])

Expected Output: 3

Explanation: Cities 1-5 are matched; cities 6-10 are five foreign 2-day jobs that must pack onto five centers (which also serve matches), completing in 3 days.

Input: (1, [])

Expected Output: 0

Explanation: No orders means no delivery days are required.

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.

Quick Overview

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.