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.

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.

Hints

  1. 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.
  2. 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.
  3. 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.

Loading coding console...