We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Average Waiting Time

Number: 1803

Difficulty: Medium

Paid? No

Companies: Amazon, Google, DE Shaw, Meta, Salesforce

Problem Description

There is a restaurant with a single chef. Customers arrive with an arrival time and a required preparation time. The chef processes orders one at a time in the order they are given. For each customer, the waiting time is the difference between the time when their order is completed and their arrival time. The task is to compute the average waiting time for all customers.

Key Insights

  • The customers are processed in the exact order they appear in the input.
  • Simulate the order processing by tracking the current time (i.e., when the chef is available).
  • If the chef is idle when a customer arrives, the current time is updated to the customer's arrival time.
  • Waiting time for each customer is computed as (current time after processing - arrival time).

Space and Time Complexity

Time Complexity: O(n), where n is the number of customers. Space Complexity: O(1) additional space (ignoring the input data).

Solution

We iterate through each customer, and for each, update the chef's current time. If the chef is busy, the customer must wait; if the chef is idle, we move forward to the customer's arrival time. For every customer, we add the wait time, which is the difference between the time the order is completed and the arrival time. Finally, we compute the average waiting time by dividing the total waiting time by the number of customers.

Code Solutions

# Function to compute the average waiting time.
def average_waiting_time(customers):
    current_time = 0  # Current time when the chef is free
    total_wait_time = 0  # Sum of all customers' waiting times
    
    # Process each customer in sequential order
    for arrival, prep_time in customers:
        # If the chef is idle, update current time to the customer's arrival time.
        if current_time < arrival:
            current_time = arrival
        # Process the customer's order.
        current_time += prep_time
        # The waiting time is the time from the arrival until the order is completed.
        total_wait_time += (current_time - arrival)
    
    # Return the average waiting time.
    return total_wait_time / len(customers)

# Example usage:
customers = [[1, 2], [2, 5], [4, 3]]
print(average_waiting_time(customers))  # Expected output: 5.0
← Back to All Questions