Katkat
Back

Rotate Couriers Daily at Minimum Total Cost

OpenAISoftware Engineer · Technical Screen
HardSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

Choose one courier company per day so that no company works two days in a row and the total price is minimal, then return the schedule. Tests DP over a small state, path reconstruction, and the best/second-best trick for k options.

A small bakery outsources its morning deliveries. Each day it hires exactly one courier company from a fixed roster, and each company quotes a different price for each day. To keep any single company from getting complacent, the bakery has one rule: the same company may never be hired on two consecutive days.

Given the price quotes, find a hiring schedule with the lowest possible total cost and return that cost and the schedule itself.

Part 1: Three companies

def plan_couriers(costs: list[list[int]]) -> tuple[int, list[int]]:
  • costs[d][c] is the price of company c on day d, with c in {0, 1, 2}.
  • Return (total, schedule), where schedule[d] is the company hired on day d.
  • Adjacent entries of schedule must differ, and total must be the minimum over all valid schedules. If several schedules tie, any of them is accepted.

Example 1

costs = [[4, 2, 7],
         [3, 1, 5],
         [6, 8, 2],
         [5, 4, 9]]
Output: (11, [1, 0, 2, 1])

Company 1 is cheapest on days 0 and 1, but it cannot be hired twice in a row. Hiring 1, 0, 2, 1 costs 2 + 3 + 2 + 4 = 11, and no valid schedule is cheaper.

Part 2: Any number of companies

The roster grows to k companies (2 <= k <= 100). Same signature, same rule. Your solution should run in O(n * k) time, not O(n * k^2).

Example 2

costs = [[10, 3, 8, 6],
         [ 2, 9, 4, 7],
         [ 5, 1, 6, 3]]
Output: (6, [1, 0, 1])

Using company 1 on days 0 and 2 is fine because the days are not consecutive.

Constraints

  • 1 <= n <= 10^5 days
  • 1 <= costs[d][c] <= 10^4
  • For Part 1, k = 3. For Part 2, 2 <= k <= 100.

Hints

Hint 1

What is the only information about the past that matters when you choose day d's company?

Hint 2

Define best[d][c] as the minimum cost for days 0..d when company c is hired on day d.

Hint 3

Store which previous company produced each minimum so you can rebuild the schedule at the end.

Hint 4

For k companies, each day you only need the smallest and second-smallest values of the previous row.

Follow-up questions

  • How would you reduce memory if n is 10^7 but you still need the schedule? (Hint: checkpointing or Hirschberg-style recomputation.)
  • What if a company may not be hired within 2 days of its last booking instead of 1?
  • Some companies are unavailable on some days. How do you represent that, and how do you detect that no schedule exists?
  • How would you return the lexicographically smallest optimal schedule?