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.

Find minimum days to deliver all orders

Company: Amazon

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Take-home Project

You manage N delivery centers labeled 1..N and an array orderCityList where each element is the destination city of one order (city IDs are in 1..N). Each calendar day, every center can work on at most one order. If a center’s ID equals the order’s city, that order takes 1 day of that center’s capacity; otherwise it takes 2 days of that center’s capacity (treat it as occupying two days on the assigned center). Orders cannot be split across centers. Compute the minimum number of days required to finish all orders. Example: N=3, orderCityList=[1,1,3,1,1] → 3 days, one optimal assignment by indices is Center1: {1,2,4}, Center2: {5}, Center3: {3}. Design an efficient algorithm (avoid brute force) and analyze its time and space complexity. Implement a function minDays(N, orderCityList) that returns the minimal days.

Quick Answer: This question evaluates algorithm design and combinatorial optimization skills, focusing on scheduling and load-balancing under per-center capacity constraints and frequency-based counting.

You manage N delivery centers labeled 1..N and an array `orderCityList` where each element is the destination city of one order (city IDs are in 1..N). Each calendar day, every center can work on at most one order. If a center's ID equals the order's city, that order takes 1 day of that center's capacity; otherwise it takes 2 days of that center's capacity (treat it as occupying two days on the assigned center). Orders cannot be split across centers. Compute the minimum number of days required to finish all orders. Example: N=3, orderCityList=[1,1,3,1,1] -> 3 days. One optimal assignment by indices is Center1: {1,2,4}, Center2: {5}, Center3: {3}. Implement `minDays(N, orderCityList)` returning the minimal number of days. Avoid brute force.

Constraints

1 <= N (number of delivery centers)
0 <= len(orderCityList)
1 <= orderCityList[i] <= N for every order
A center may serve at most one order per day; a non-matching (foreign) order occupies two of that center's days.
Orders cannot be split across centers.

Examples

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

Expected Output: 3

Explanation: City counts: city1=4, city3=1. With D=3, Center1 takes 3 home orders (3 days), Center3 takes its 1 home order (1 day), and the remaining 1 order for city1 goes to Center2 as a foreign order (2 days). Max load = 3. D=2 fails, so 3 is minimal.

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

Expected Output: 3

Explanation: Only one center exists, and all 3 orders are home orders for it, costing 1 day each = 3 days total. There is no other center to offload to.

Input: (2, [])

Expected Output: 0

Explanation: No orders means no work, so 0 days are needed.

Input: (3, [2])

Expected Output: 1

Explanation: The single order to city 2 is served by Center2 as a home order, costing 1 day.

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

Expected Output: 4

Explanation: Six orders all for city 1. With D=4: Center1 takes 4 home orders (4 days), and the remaining 2 orders go to Center2 and Center3 as foreign orders (2 days each). Max load = 4, and D=3 is infeasible.

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

Expected Output: 2

Explanation: City1=2, city2=2. With D=2: Center1 serves both city1 orders home (2 days) and Center2 serves both city2 orders home (2 days). Max load = 2.

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

Expected Output: 2

Explanation: Five orders all for city 1. With D=2: Center1 takes 2 home orders (2 days); the remaining 3 orders each go to one of Centers 2, 3, 4 as a foreign order (2 days each). Max load = 2.

Hints

Binary search on the answer D (the number of days). The feasible region is monotone: if D days suffice, so does any D' > D, so the smallest feasible D is the answer.
Give every center a budget of D occupied-days. A home order (center id == city) costs 1 day and is always cheaper than the 2 days a foreign order costs, so for each city greedily place up to min(count[c], D) orders on their home center first.
After placing home orders, any leftover order for any city is 'foreign' and needs a 2-day slot somewhere. A center with h home orders has D - h days left, giving floor((D - h) / 2) foreign slots. D is feasible iff total foreign slots >= total leftover (foreign) orders.

Quick Overview

This question evaluates algorithm design and combinatorial optimization skills, focusing on scheduling and load-balancing under per-center capacity constraints and frequency-based counting.