Design a call center
Route calls through operators, supervisors and directors.
On this page
Constraints and assumptions#
- What levels of employees are in the call center?
- Operator, supervisor, director
- Can we assume operators always get the initial calls?
- Yes
- If there is no available operators or the operator can't handle the call, does the call go to the supervisors?
- Yes
- If there is no available supervisors or the supervisor can't handle the call, does the call go to the directors?
- Yes
- Can we assume the directors can handle all calls?
- Yes
- What happens if nobody can answer the call?
- It gets queued
- Do we need to handle 'VIP' calls where we put someone to the front of the line?
- No
- Can we assume inputs are valid or do we have to validate them?
- Assume they're valid
Solution#
from abc import ABCMeta, abstractmethod
from collections import deque
from enum import Enum
class Rank(Enum):
OPERATOR = 0
SUPERVISOR = 1
DIRECTOR = 2
class Employee(metaclass=ABCMeta):
def __init__(self, employee_id, name, rank, call_center):
self.employee_id = employee_id
self.name = name
self.rank = rank
self.call = None
self.call_center = call_center
def take_call(self, call):
"""Assume the employee will always successfully take the call."""
self.call = call
self.call.employee = self
self.call.state = CallState.IN_PROGRESS
def complete_call(self):
self.call.state = CallState.COMPLETE
self.call_center.notify_call_completed(self.call)
@abstractmethod
def escalate_call(self):
pass
def _escalate_call(self):
self.call.state = CallState.READY
call = self.call
self.call = None
self.call_center.notify_call_escalated(call)
class Operator(Employee):
def __init__(self, employee_id, name):
super(Operator, self).__init__(employee_id, name, Rank.OPERATOR)
def escalate_call(self):
self.call.level = Rank.SUPERVISOR
self._escalate_call()
class Supervisor(Employee):
def __init__(self, employee_id, name):
super(Operator, self).__init__(employee_id, name, Rank.SUPERVISOR)
def escalate_call(self):
self.call.level = Rank.DIRECTOR
self._escalate_call()
class Director(Employee):
def __init__(self, employee_id, name):
super(Operator, self).__init__(employee_id, name, Rank.DIRECTOR)
def escalate_call(self):
raise NotImplemented('Directors must be able to handle any call')
class CallState(Enum):
READY = 0
IN_PROGRESS = 1
COMPLETE = 2
class Call(object):
def __init__(self, rank):
self.state = CallState.READY
self.rank = rank
self.employee = None
class CallCenter(object):
def __init__(self, operators, supervisors, directors):
self.operators = operators
self.supervisors = supervisors
self.directors = directors
self.queued_calls = deque()
def dispatch_call(self, call):
if call.rank not in (Rank.OPERATOR, Rank.SUPERVISOR, Rank.DIRECTOR):
raise ValueError('Invalid call rank: {}'.format(call.rank))
employee = None
if call.rank == Rank.OPERATOR:
employee = self._dispatch_call(call, self.operators)
if call.rank == Rank.SUPERVISOR or employee is None:
employee = self._dispatch_call(call, self.supervisors)
if call.rank == Rank.DIRECTOR or employee is None:
employee = self._dispatch_call(call, self.directors)
if employee is None:
self.queued_calls.append(call)
def _dispatch_call(self, call, employees):
for employee in employees:
if employee.call is None:
employee.take_call(call)
return employee
return None
def notify_call_escalated(self, call): # ...
def notify_call_completed(self, call): # ...
def dispatch_queued_call_to_newly_freed_employee(self, call, employee): # ...Added on this site
The one idea#
A call has to reach someone who can handle it, in a fixed order: operators first, then supervisors, then directors. If nobody suitable is free, the call waits. If the person who picked it up cannot handle it, it escalates upward. That is a small routing and queueing problem, and the interesting design question is where each decision lives.
How to get there in an interview#
- Read the constraints as a spec. Three ranks. Operators always get the first try. A call that no operator can take goes to a supervisor, then a director. Directors can handle anything. If nobody is free, the call is queued. No VIP calls. Each answer removes a branch from your design.
- List the nouns. Employee (with three ranks), Call, CallCenter. A call's state matters too: waiting, in progress, complete.
- Decide where behaviour lives.
- An
Employeeknows its rank and whether it is on a call. - A
Callknows the lowest rank allowed to handle it, which rises each time it is escalated, and who has it. - The
CallCenterowns the routing: which employees exist, who is free, and the waiting queue. Employees should not search for each other.
- An
- Pick the data structures. Employees grouped by rank, so the dispatcher can walk the ranks in order. A FIFO queue for waiting calls, so the longest wait is served first.
- Handle the two events that free someone up. A call completes, or it escalates. In both cases the employee becomes free and should immediately be offered the longest-waiting call they are allowed to take.
A working version#
A small version that models the whole flow. It uses one Employee class with a rank, rather than three subclasses with the same body, because only the rank differs. Say that choice out loud: do not create subclasses unless behaviour differs.
from collections import deque
from enum import IntEnum
class Rank(IntEnum):
OPERATOR = 0
SUPERVISOR = 1
DIRECTOR = 2
class Employee:
def __init__(self, name, rank):
self.name = name
self.rank = rank
self.call = None
@property
def is_free(self):
return self.call is None
class Call:
def __init__(self, caller):
self.caller = caller
self.min_rank = Rank.OPERATOR # lowest rank allowed to handle it; rises on escalation
self.employee = None
class CallCenter:
def __init__(self, employees):
self.by_rank = {rank: [e for e in employees if e.rank == rank] for rank in Rank}
self.waiting = deque()
def dispatch(self, call):
"""Give the call to a free employee, lowest rank first. Queue it if nobody can take it."""
for rank in Rank:
if rank < call.min_rank:
continue
for employee in self.by_rank[rank]:
if employee.is_free:
employee.call, call.employee = call, employee
return employee
self.waiting.append(call)
return None
def finish(self, call):
"""The call is over. Free the employee and give them the longest-waiting call they may take."""
return self._free_and_reassign(call.employee)
def escalate(self, call):
"""The employee cannot handle it. Move it up a rank and find someone else."""
employee = call.employee
call.min_rank = Rank(min(employee.rank + 1, Rank.DIRECTOR))
self._free_and_reassign(employee)
return self.dispatch(call)
def _free_and_reassign(self, employee):
employee.call.employee = None
employee.call = None
for waiting in list(self.waiting):
if waiting.min_rank <= employee.rank:
self.waiting.remove(waiting)
employee.call, waiting.employee = waiting, employee
return waiting
return NoneTry it with one employee of each rank:
ann, bob, cy = Employee('Ann', Rank.OPERATOR), Employee('Bob', Rank.SUPERVISOR), Employee('Cy', Rank.DIRECTOR)
center = CallCenter([ann, bob, cy])
first, second, third, fourth = Call('c1'), Call('c2'), Call('c3'), Call('c4')
assert center.dispatch(first) is ann # operators are tried first
assert center.dispatch(second) is bob # the only operator is busy, so a supervisor takes it
assert center.dispatch(third) is cy # then the director
assert center.dispatch(fourth) is None # nobody is free: it waits
assert list(center.waiting) == [fourth]
assert center.finish(first) is fourth # Ann is free again and takes the waiting call
assert fourth.employee is ann
center.escalate(fourth) # Ann cannot handle it; it needs a supervisor or above
assert fourth.min_rank == Rank.SUPERVISOR
assert list(center.waiting) == [fourth] # Bob and Cy are both busy, so it waits for one of them
assert center.finish(second) is fourth # Bob finishes and picks it upWhat is wrong with the sketch above#
The solution on this page is an outline, and the classes cannot be constructed. Each of these was checked by running the code:
Operator(1, 'a')fails withmissing 1 required positional argument: 'call_center'. The base class takes four arguments but the subclass passes three.SupervisorandDirectorfail withsuper(type, obj): obj ... is not an instance or subtype of type (Operator), because they callsuper(Operator, self)instead of naming their own class.- Escalation sets the wrong field.
escalate_callwritescall.level, but the dispatcher routes oncall.rank, so an escalated call would be sent to the same rank again. - The
notify_*methods and the one that hands a queued call to a freed employee are empty.
The three subclasses also add almost nothing over a single class with a rank, which is why the version above does without them.
Questions to expect next#
- Fairness. Taking the first free employee always favours the front of the list. Rotate or pick the one idle longest.
- VIP calls. Replace the FIFO queue with a priority queue ordered by priority, then arrival time.
- Concurrency. Two calls arriving at once must not both take the same employee. Lock around "find a free employee and assign", or serialize dispatch through one queue.
- Scale. One dispatcher is a single point of failure and a bottleneck. Partition by region or queue, and put the waiting calls in a durable message queue. The queue lab shows what happens when calls arrive faster than people can answer.
- Wait time. The longer the queue, the longer the wait for a new caller, which is the same relationship as in the load curve.