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 average customer waiting time | Instacart Coding Question

Quick Overview

Compute average customer waiting time evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.

Compute average customer waiting time

Company: Instacart

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Onsite

You are given n customer orders; each order i = [a_i, p_i] where a_i is the arrival time and p_i is the preparation time. A single chef processes orders non-preemptively. If the chef is idle and multiple orders are available, they pick the earliest-arrived order among those waiting. Compute the average waiting time across all customers, where waiting_i = finish_i − a_i. Return a floating-point value. Constraints: 1 ≤ n ≤ 100000; 0 ≤ a_i < 1e9; 1 ≤ p_i ≤ 1e4. Follow-ups: ( 1) If you can choose any waiting order, how would you minimize the average waiting time? ( 2) Generalize to k chefs and describe your algorithm and complexity.

Quick Answer: Compute average customer waiting time evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.

You are given `n` customer orders. Each order `i = [a_i, p_i]`, where `a_i` is the arrival time and `p_i` is the preparation time. A single chef processes orders non-preemptively (once started, an order runs to completion). When the chef is idle and one or more orders have already arrived, the chef picks the earliest-arrived order among those waiting (ties broken by smaller preparation time, then by input order). If no order has arrived yet, the chef waits until the next arrival. The waiting time of a customer is `waiting_i = finish_i - a_i`, where `finish_i` is the time the chef completes that order. Return the **average** waiting time across all customers as a floating-point value. **Example** `orders = [[1,2],[2,5],[4,3]]` - Order 0 arrives at 1, chef idle, starts at 1, finishes at 3 → wait 2. - Order 1 arrived at 2 (waiting since the chef was busy), starts at 3, finishes at 8 → wait 6. - Order 2 arrived at 4, starts at 8, finishes at 11 → wait 7. - Average = (2 + 6 + 7) / 3 = 5.0.

Constraints

1 <= n <= 100000
0 <= a_i < 1e9 (arrival time)
1 <= p_i <= 1e4 (preparation time)
The chef processes orders non-preemptively.
When idle, the chef picks the earliest-arrived order among those that have already arrived.

Examples

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

Expected Output: 5.0

Explanation: Order 0: start 1, finish 3, wait 2. Order 1: start 3, finish 8, wait 6. Order 2: start 8, finish 11, wait 7. Average = 15/3 = 5.0.

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

Expected Output: 3.25

Explanation: At time 5 both [5,2] and [5,4] are waiting; the shorter-prep one is chosen first (tie on arrival). Waits sum to 13 over 4 orders = 3.25 (LeetCode 1701 sample).

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

Expected Output: 3.0

Explanation: Single order arrives at 0, finishes at 3, wait 3 → average 3.0.

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

Expected Output: 2.0

Explanation: Chef is idle until the only order arrives at 10; it finishes at 12, wait 2 → average 2.0. Exercises the idle fast-forward branch.

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

Expected Output: 2.0

Explanation: Three identical orders all arrive at 0. They finish at 1, 2, 3 → waits 1+2+3 = 6, average 2.0. Tests duplicate handling.

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

Expected Output: 3.5

Explanation: Both arrive at 0; tie broken by smaller prep, so [0,2] runs first (finish 2, wait 2), then [0,3] (finish 5, wait 5). Average = 7/2 = 3.5.

Hints

Sort orders by arrival time. Sweep a clock forward, and whenever the chef is free, only orders that have already arrived are eligible.
Use a min-heap of waiting orders keyed by arrival time so you can quickly grab the earliest-arrived one. When the heap is empty, fast-forward the clock to the next arrival.
Waiting time for an order is finish_time - arrival_time, where finish_time is the clock value right after the chef completes it. Sum these and divide by n.

Quick Overview