Quick Overview

This question evaluates competence in event-driven simulation, scheduling and queueing concepts, and algorithmic analysis by requiring computation of average customer waiting time for single and multiple shoppers.

Compute delivery wait times

Company: Instacart

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

You're building a last‑mile delivery simulator. Given n orders, each with arrival_time (non-decreasing integers) and service_time (positive integers), a single shopper processes one order at a time and is idle until the next order arrives. Compute the average customer waiting time, where waiting_time = finish_time − arrival_time. Return a floating‑point average with 5 decimal places. Follow up: Now there are k shoppers (k ≥ 1). Process orders strictly in arrival order and always assign the next order to the earliest available shopper (break ties by smallest shopper id). Compute the resulting average waiting time and analyze time and space complexity.

Overview: This question evaluates competence in event-driven simulation, scheduling and queueing concepts, and algorithmic analysis by requiring computation of average customer waiting time for single and multiple shoppers.

Read the full Instacart Software Engineer interview experience this question came from

Delivery Wait Times — Single Shopper

You're building a last-mile delivery simulator. Given n orders, each with an arrival_time (non-decreasing integers) and a service_time (positive integers), a single shopper processes one order at a time in arrival order. The shopper is idle until the next order arrives, then starts it at max(current_available_time, arrival_time). For each order, waiting_time = finish_time - arrival_time, where finish_time = start_time + service_time. Compute the average customer waiting time across all orders, rounded to 5 decimal places. If there are no orders, return 0.0.

Constraints

  • 0 <= n <= 10^5
  • arrival_time is non-decreasing
  • service_time[i] >= 1
  • Round the average to 5 decimal places
  • Return 0.0 when there are no orders

Examples

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

Expected Output: 5.0

Explanation: Order0: 0->3 (wait 3). Order1 starts at 3: 3->6 (wait 5). Order2 starts at 6: 6->9 (wait 7). Total 15, avg 5.0.

Input: ([0, 5, 10], [2, 2, 2])

Expected Output: 2.0

Explanation: Shopper is idle between orders, so each order starts at its own arrival and waits exactly its service time (2).

Hints

  1. Track the time at which the shopper becomes free; the next order can only start at max(free_time, its_arrival).
  2. waiting_time already includes the queueing delay because it is measured from arrival_time, not from start_time.
  3. Accumulate finish_time - arrival_time per order, then divide by n and round to 5 decimals.

Delivery Wait Times — k Shoppers

Follow-up to the single-shopper simulator. Now there are k shoppers (k >= 1). Process orders strictly in arrival order and always assign the next order to the earliest-available shopper, breaking ties by the smallest shopper id. A shopper that picks up an order at time start = max(shopper_available_time, arrival_time) finishes (and becomes available again) at start + service_time. For each order, waiting_time = finish_time - arrival_time. Compute the average waiting time across all orders, rounded to 5 decimal places. If there are no orders, return 0.0.

Constraints

  • 1 <= k <= 10^5
  • 0 <= n <= 10^5
  • arrival_time is non-decreasing
  • service_time[i] >= 1
  • Assign each order to the earliest-available shopper; break ties by smallest shopper id
  • Round the average to 5 decimal places
  • Return 0.0 when there are no orders

Examples

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

Expected Output: 5.0

Explanation: With one shopper this matches Part 1: waits 3, 5, 7 -> avg 5.0.

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

Expected Output: 3.0

Explanation: Three shoppers, each takes one order with no queueing: every order waits exactly its 3-unit service time -> avg 3.0.

Hints

  1. Keep a min-heap of (available_time, shopper_id). Popping gives the earliest-available shopper, with the id as a natural tie-breaker.
  2. The order's start time is max(that shopper's available_time, the order's arrival_time); push back (start + service_time, shopper_id).
  3. Because orders are processed in arrival order, you never need to sort — just iterate and let the heap pick the shopper.
  4. k = 1 reduces exactly to the single-shopper version.

Loading coding console...