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 and optimize average wait time | Instacart Coding Question

Compute and optimize average wait time

Company: Instacart

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Onsite

You are given n pickup orders for a grocery delivery counter. Each order i is described by orders[i] = [arrival_i, service_i] in minutes, where arrival_i is when the shopper arrives and service_i is how long a single clerk needs to hand off the order. The counter opens at time 0 and the clerk processes one order at a time; when the clerk is idle and the next shopper has not yet arrived, the clerk waits. Compute the average waiting time across all shoppers (waiting includes service time). Assume arrival_i are non-decreasing; if they are not, sort them by arrival time first. Follow-ups: (a) Extend the solution when there are k >= 1 identical clerks; each arriving order is assigned to the clerk that becomes available the earliest. Return the average waiting time and justify your data structures and time complexity. (b) Discuss how your approach scales for very large n (e.g., n up to 2e 5) and what the big-O time and space complexities are.

Quick Answer: This question evaluates skills in scheduling and queueing algorithms, simulation of service systems, and reasoning about time and space complexity when computing average waiting times.

Average Wait Time at a Single-Clerk Delivery Counter

You are given `n` pickup orders for a grocery delivery counter. Each order `i` is `orders[i] = [arrival_i, service_i]` in minutes, where `arrival_i` is when the shopper arrives and `service_i` is how long a single clerk needs to hand off that order. The counter opens at time 0 and the single clerk processes one order at a time. When the clerk finishes an order, they immediately start the next shopper who has already arrived; if the next shopper has not yet arrived, the clerk waits idle until they do. A shopper's waiting time is measured from their arrival until their hand-off completes (so it includes the service time itself). Return the **average waiting time** across all shoppers as a float. Arrivals are typically non-decreasing, but you must not rely on that — if they are not sorted, sort the orders by arrival time first. Return `0.0` for an empty list. The key recurrence: process orders in arrival order, tracking the time `current` at which the clerk becomes free. For each order the service starts at `start = max(current, arrival)`, finishes at `start + service`, and the shopper's wait is `finish - arrival`. Then `current = finish`.

Constraints

0 <= n <= 2 * 10^5
0 <= arrival_i, service_i (minutes), each fits in a 32-bit int; the running total can exceed 32 bits, so accumulate in a 64-bit / arbitrary-precision integer
Arrivals may be unsorted; sort by arrival time first
Return 0.0 when there are no orders

Examples

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

Expected Output: 10.0

Explanation: Shopper0 waits 3 (0->3). Shopper1 arrives at 1 but clerk free at 3: 3->12, wait 11. Shopper2 arrives at 2, clerk free at 12: 12->18, wait 16. (3+11+16)/3 = 10.0.

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

Expected Output: 2.0

Explanation: Single shopper served on arrival; wait equals the 2 minutes of service. Average = 2.0.

Input: ([],)

Expected Output: 0.0

Explanation: No shoppers — defined as 0.0.

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

Expected Output: 2.0

Explanation: All arrive at 0. Waits are 1, 2, 3 as they queue. (1+2+3)/3 = 2.0.

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

Expected Output: 4.0

Explanation: Unsorted input; sort to [[0,3],[2,4]]. First waits 3 (0->3). Second arrives at 2, clerk free at 3: 3->7, wait 5. (3+5)/2 = 4.0.

Input: ([[10, 2], [11, 3], [20, 1]],)

Expected Output: 2.3333333333333335

Explanation: First: 10->12, wait 2. Second arrives 11, clerk free 12: 12->15, wait 4. Third arrives 20 after clerk idle: 20->21, wait 1. (2+4+1)/3 = 2.333...

Hints

The clerk is never idle while there is already a waiting shopper, so you only need one running 'clerk-free' timestamp, not a full event simulation.
For each order, service begins at max(current_free_time, arrival) and the wait is (begin + service) - arrival. Notice this equals service plus any idle-queue delay the shopper absorbed.
Sort by arrival first; if two shoppers arrive at the same time, either order gives the same total wait, so a stable sort is fine.

Average Wait Time with k Identical Clerks

Follow-up to the single-clerk counter. Now the counter staffs `k >= 1` identical clerks who each process one order at a time. Orders are still given as `orders[i] = [arrival_i, service_i]` and are handled in non-decreasing arrival order (sort first if needed). Each arriving order is assigned to the clerk that becomes **available the earliest** (ties broken arbitrarily — any earliest-free clerk gives the same total). Service for that order begins at `max(clerk_free_time, arrival)`. Return the **average waiting time** across all shoppers as a float, where a shopper's wait is again `finish - arrival` (service inclusive). Return `0.0` for an empty list. Data structure: keep a min-heap of the `k` clerks' next-free timestamps (all initialized to 0, the open time). For each order in arrival order, pop the smallest free time, compute the wait, then push back the new finish time. When `k = 1` this is exactly the single-clerk problem; when `k >= n` every shopper is served immediately on arrival.

Constraints

1 <= k
0 <= n <= 2 * 10^5
0 <= arrival_i, service_i (minutes); accumulate the total in 64-bit to avoid overflow
Assign each order to an earliest-available clerk; ties among equally-free clerks do not change the result
k = 1 reduces to the single-clerk problem; k >= n means every shopper is served on arrival
Return 0.0 when there are no orders

Examples

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

Expected Output: 10.0

Explanation: k=1 reduces to the single-clerk case: waits 3, 11, 16 -> average 10.0.

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

Expected Output: 6.333333333333333

Explanation: ClerkA: 0->3 (wait 3). ClerkB free at 0 takes shopper1: 1->10 (wait 9). ClerkA free at 3 takes shopper2: 3->9 (wait 7). (3+9+7)/3 = 6.333...

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

Expected Output: 6.0

Explanation: Three clerks, each shopper served on arrival: 0->3 (3), 1->10 (9), 2->8 (6). (3+9+6)/3 = 6.0.

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

Expected Output: 2.0

Explanation: More clerks than orders; the single shopper is served immediately, wait 2.0.

Input: ([], 3)

Expected Output: 0.0

Explanation: No shoppers — 0.0 regardless of k.

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

Expected Output: 1.3333333333333333

Explanation: Two clerks: first two shoppers served 0->1 (wait 1 each); third queues behind a clerk free at 1: 1->2 (wait 2). (1+1+2)/3 = 1.333...

Input: ([[10, 2], [11, 3], [20, 1]], 2)

Expected Output: 2.0

Explanation: ClerkA: 10->12 (2). ClerkB: 11->14 (3). Shopper3 arrives at 20 when both clerks are idle: 20->21 (1). (2+3+1)/3 = 2.0.

Hints

Track only when each clerk next becomes free. A min-heap of k free-times lets you pull the earliest-available clerk in O(log k) per order.
Initialize all k clerk free-times to 0 (the counter's open time). Popping the min and pushing the new finish keeps the heap describing the future state correctly.
Because orders are processed in arrival order, the earliest-free clerk at the moment of assignment is exactly the clerk who would start this order soonest — greedy by free-time is optimal here.
For very large n (up to 2e5) the sort is the bottleneck at O(n log n); the heap of size k is tiny, so memory is O(n + k) and the algorithm stays well within limits.

Quick Overview

This question evaluates skills in scheduling and queueing algorithms, simulation of service systems, and reasoning about time and space complexity when computing average waiting times.