Average Waiting Time

Average Waiting Time

What is this problem about?

The Average Waiting Time interview question is a simulation of a single-chef restaurant. You are given a list of customers, each with an arrival time and the time required to prepare their dish. The chef cooks for one customer at a time in the order they arrive. A customer's waiting time is (finish_time - arrival_time). Your goal is to find the average waiting time for all customers. This Average Waiting Time coding problem focuses on sequential processing.

Why is this asked in interviews?

Apple, Meta, and Google ask this to evaluate your ability to manage state over time. It tests whether you can correctly track the chef's "current available time" and understand how idle time (when no customers are present) affects the timeline.

Algorithmic pattern used

This follows the Array, Simulation interview pattern. You maintain a variable currentTime representing when the chef will finish the current task. For each customer, the chef starts cooking at max(arrival_time, currentTime).

Example explanation

Customer 1: Arrives at 1, takes 2 mins. Customer 2: Arrives at 2, takes 5 mins.

1. Cust 1: Chef starts at 1, finishes at 3. Wait = 3 - 1 = 2. currentTime = 3.
2. Cust 2: Chef starts at 3 (since arrival was at 2 but chef was busy), finishes at 8. Wait = 8 - 2 = 6. currentTime = 8.

• Total Wait: 2 + 6 = 8. Average: 8 / 2 = 4.

Common mistakes candidates make

• Ignoring Idle Time: Assuming the chef starts the next order exactly when the previous one ends, even if the next customer hasn't arrived yet.
• Wrong Wait Formula: Calculating wait as just the prep time, forgetting that the time spent waiting for the chef to become free counts too.
• Integer Overflow: If the number of customers and times are large, the total sum of waiting times can exceed a 32-bit integer.

Interview preparation tip

In simulation problems, always track the "global clock." Before processing an event, advance the clock to the event's start time if the clock is currently behind.