Google | Phone | Calculate Total Wait Time
Anonymous User
7871
GoogleInterview
  1. Question:

Calculate the total wait time for a customer C to speak to an agent given N agents, M customers, and T[] time for an agent to serve a customer. T[i] represents the amount of time it takes for an agent i to serve one customer. One agent can serve one customer at a time. All N agents can serve concurrently. The customer chooses the agent with the lowest wait time.

Examples:

N = 2
M = 2
T = [4, 5]
First customer chooses agent 1. Second customer chooses agent 2.
Customer C will wait 4 minutes.
N = 2
M = 4
T = [4, 5]
First customer chooses agent 1. Second customer chooses agent 2.
Third customer chooses agent 1. Forth customer chooses agent 2.
Customer C will wait 8 minutes.

Initial questions:

Bounds on N and M - No bounds
Can N or M be zero - Both can be zero
Are the T values constant - Yes
Are the T values integers - Yes

Python solution:

N = 2
M = 4
T = [4, 5]

W = [0] * len(T)

for i in range(M):
    min = 12345
    agent = -1
    for j in range(N):
        if (W[j] < min):
            min = W[j]
            agent = j
    W[agent] += T[agent]

C_time = 12345
C_agent = -1
for j in range(N):
    if (W[j] < C_time):
        C_time = W[j]
        C_agent = j
        
print(f"C_time: {C_time}, C_agent: {C_agent}")
  1. Efficiency

I gave O(M*N). If M and N are equally large O(N^2).

  1. Test cases

I gave
N and M at max
N and M at zero

  1. Follow up question

What agent will customer C speak to?

No coding required - answer was already in initial solution.

Edit:

from queue import PriorityQueue

N = 2
M = 4
T = [5, 4]

queue = PriorityQueue()

for agent in range(N):
    queue.put((T[agent], (T[agent], agent)))
    
for cust in range(M):
    totalTime, (helpTime, agent) = queue.get()
    queue.put((totalTime + helpTime, (helpTime, agent)))
    
totalTime, (helpTime, agent) = queue.get()
print(f"C_time: {totalTime - helpTime}, C_agent: {agent}")
Comments (19)