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 Onsite rounds at Instacart.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Instacart during technical interviews.

Compute delivery wait times | Instacart Coding Question

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.

Quick Answer: 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.

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).

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

Expected Output: 3.33333

Explanation: All arrive at 0. Finishes at 1, 3, 6. Waits 1, 3, 6 -> total 10, avg 3.33333.

Input: ([5], [4])

Expected Output: 4.0

Explanation: Single order: 5->9, wait 4.

Input: ([], [])

Expected Output: 0.0

Explanation: No orders -> average is 0.0.

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

Expected Output: 5.0

Explanation: Order0 0->5 (5). Order1 starts at 5: 5->10 (9). Order2 arrives at 10, starts at 10: 10->11 (1). Total 15, avg 5.0.

Hints

Track the time at which the shopper becomes free; the next order can only start at max(free_time, its_arrival).
waiting_time already includes the queueing delay because it is measured from arrival_time, not from start_time.
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.

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

Expected Output: 2.33333

Explanation: Shopper0 takes order0 (0->1), shopper1 takes order1 (0->2), shopper0 (free at 1) takes order2 (1->4, wait 4). Waits 1,2,4 -> total 7, avg 2.33333.

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

Expected Output: 4.0

Explanation: Shopper0 takes the long order0 (0->10). Shopper1 handles order1 (0->1), order2 (1->2), order3 (2->3). Waits 10,1,2,3 -> total 16, avg 4.0.

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

Expected Output: 4.0

Explanation: Single order on the earliest-available (and lowest-id) shopper: 5->9, wait 4.

Input: ([], [], 4)

Expected Output: 0.0

Explanation: No orders -> average is 0.0.

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

Expected Output: 3.66667

Explanation: Shopper0 order0 (0->5, wait5), shopper1 order1 (1->6, wait5), shopper0 free at 5 takes order2 which arrives at 10 (10->11, wait1). Total 11, avg 3.66667.

Hints

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

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.