Cracking The Coding Interview Together – Problem 7.2: Call Center

Imagine it is Black Friday. Your e-commerce platform is experiencing record-breaking traffic, and with that traffic comes an inevitable deluge of customer support requests. Calls are flooding into your customer service center. If your system routes a simple password reset call directly to a Director, you are wasting expensive executive time on a trivial task. Conversely, if a high-priority enterprise escalation is routed to a junior respondent who lacks the permissions to resolve it, you risk losing a million-dollar account due to slow resolution times.

This is the classic resource allocation problem. In system design and object-oriented programming, managing a hierarchical pool of workers under concurrent load is a fundamental challenge. Today, we are going to tackle Problem 7.2: Call Center from Cracking the Coding Interview. Our shared goal is to design a clean, scalable, and thread-safe call routing system that gracefully handles incoming calls, manages employee availability, and escalates issues seamlessly when lower-tier employees are overwhelmed.

Problem Statement

The core requirements of the problem are straightforward but require careful structural planning:

• We have a call center with three levels of employees: Respondent, Manager, and Director.
• An incoming call must be allocated to the first available Respondent.
• If the Respondent cannot handle the call (either because they are busy or the issue requires higher authority), the call must be escalated to a Manager.
• If the Manager is busy or cannot handle the call, it must be escalated to a Director.
• We need to design the classes and write the assignment logic for dispatchCall().

Analyze the Problem Together

Let's break down the constraints and find the "Aha!" moment of this design challenge. At first glance, this looks like a simple filtering problem: find an employee, check if they are free, and assign the call. But as senior engineers, we must look deeper.

What happens when everyone is busy? A naive approach might loop through an array of employees repeatedly (polling) or block the calling thread indefinitely. This is highly inefficient and does not scale. If we have 1,000 respondents, iterating through an array on every incoming call results in an $O(N)$ search time, which degrades rapidly under high concurrency.

Instead, we should think of this in terms of queues. We have two distinct types of queues we can leverage:

1. Employee Queues: Instead of searching for an available employee, we can maintain queues of available employees for each rank (Respondent, Manager, Director). When an employee becomes free, they push themselves back into their respective queue. This turns our assignment lookup into a highly efficient $O(1)$ operation.
2. Call Queue: If no employees are available at any level, incoming calls should not be dropped or block the system. They should be placed in a FIFO (First-In, First-Out) waiting queue until an employee becomes free.

Let's compare the naive approach against our queue-based architectural choice:

Questions for the Interviewer

In a real interview, a senior engineer never starts coding immediately. You must clarify the boundaries of the system. Here are the key questions we should ask:

• "Can a call be escalated dynamically mid-call?"
  Why it matters: If a respondent answers a call but realizes they cannot solve it, they need a way to trigger an escalation that preserves the call's state and routes it to the next tier.
• "Is this system running in a multi-threaded environment?"
  Why it matters: If multiple calls arrive simultaneously, or if employees finish calls concurrently, we must ensure our data structures are thread-safe to prevent race conditions (e.g., two calls being assigned to the same employee).
• "What is the behavior when the queue is full?"
  Why it matters: In a real-world system, we cannot queue infinite calls due to memory constraints. We should clarify if we need to implement a rejection policy (backpressure) or if we can assume an unbounded queue for this exercise.

Think About the Solution

Let's design our class hierarchy. We will use clean Object-Oriented Design (OOD) principles:

• Rank (Enum): Defines the hierarchy: RESPONDENT (0), MANAGER (1), DIRECTOR (2).
• Call: Represents an incoming call. It tracks its current rank requirement, the caller, and the assigned employee. It should have an escalate() method to increment its rank requirement.
• Employee (Abstract Class): Base class for Respondent, Manager, and Director. It holds a reference to the active call and handles the transition between busy and free states.
• CallHandler (The Orchestrator): This is the heart of our system. It manages the queues of available employees for each rank, the queue of waiting calls, and contains the core dispatchCall() and onCallCompleted() routing logic.

To ensure thread safety, we will use Java's ReentrantLock and concurrent collections like ConcurrentLinkedQueue. This prevents race conditions when multiple threads attempt to dispatch calls or complete calls at the same time.

Write Code and Explain

Let's implement this design in clean, production-ready Java.

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.concurrent.locks.ReentrantLock;

// 1. Define the Rank Enum
enum Rank {
    RESPONDENT(0),
    MANAGER(1),
    DIRECTOR(2);

    private final int value;
    Rank(int value) { this.value = value; }
    public int getValue() { return value; }
}

// 2. Represent the Call
class Call {
    private Rank minimalRank;
    private Employee handler;
    private final String callerId;

    public Call(String callerId) {
        this.callerId = callerId;
        this.minimalRank = Rank.RESPONDENT; // All calls start at Respondent level
    }

    public void setHandler(Employee employee) { this.handler = employee; }
    public Employee getHandler() { return handler; }
    public Rank getRank() { return minimalRank; }
    public String getCallerId() { return callerId; }

    public void incrementRank() {
        if (minimalRank == Rank.RESPONDENT) {
            minimalRank = Rank.MANAGER;
        } else if (minimalRank == Rank.MANAGER) {
            minimalRank = Rank.DIRECTOR;
        }
    }

    public void disconnect() {
        if (handler != null) {
            handler.completedCall();
        }
        System.out.println("Call from " + callerId + " disconnected.");
    }
}

// 3. Abstract Employee Class
abstract class Employee {
    protected Call currentCall = null;
    protected Rank rank;
    protected CallHandler callHandler;

    public Employee(CallHandler callHandler, Rank rank) {
        this.callHandler = callHandler;
        this.rank = rank;
    }

    public synchronized boolean receiveCall(Call call) {
        if (!isFree()) return false;
        currentCall = call;
        call.setHandler(this);
        return true;
    }

    public synchronized void completedCall() {
        if (currentCall != null) {
            currentCall = null;
            callHandler.makeEmployeeFree(this);
        }
    }

    public synchronized void escalateCall() {
        if (currentCall != null) {
            System.out.println("Escalating call from " + currentCall.getCallerId() + " by " + rank);
            currentCall.incrementRank();
            Call tempCall = currentCall;
            currentCall = null; // Free this employee
            callHandler.makeEmployeeFree(this);
            callHandler.dispatchCall(tempCall); // Re-dispatch the escalated call
        }
    }

    public synchronized boolean isFree() { return currentCall == null; }
    public Rank getRank() { return rank; }
}

// Concrete Employee Implementations
class Respondent extends Employee {
    public Respondent(CallHandler callHandler) { super(callHandler, Rank.RESPONDENT); }
}

class Manager extends Employee {
    public Manager(CallHandler callHandler) { super(callHandler, Rank.MANAGER); }
}

class Director extends Employee {
    public Director(CallHandler callHandler) { super(callHandler, Rank.DIRECTOR); }
}

// 4. The CallHandler (Orchestrator)
class CallHandler {
    private final int NUM_LEVELS = 3;
    // List of queues representing available employees at each level
    private final List<Queue<Employee>> employeeQueues;
    // Queue for calls that cannot be handled immediately
    private final Queue<Call> callQueue;
    private final ReentrantLock lock = new ReentrantLock();

    public CallHandler(int numRespondents, int numManagers, int numDirectors) {
        employeeQueues = new ArrayList<>(NUM_LEVELS);
        for (int i = 0; i < NUM_LEVELS; i++) {
            employeeQueues.add(new LinkedList<>());
        }
        callQueue = new LinkedList<>();

        // Initialize employees
        for (int i = 0; i < numRespondents; i++) employeeQueues.get(Rank.RESPONDENT.getValue()).add(new Respondent(this));
        for (int i = 0; i < numManagers; i++) employeeQueues.get(Rank.MANAGER.getValue()).add(new Manager(this));
        for (int i = 0; i < numDirectors; i++) employeeQueues.get(Rank.DIRECTOR.getValue()).add(new Director(this));
    }

    // Entry point for incoming calls
    public void dispatchCall(Call call) {
        lock.lock();
        try {
            Employee emp = getHandlerForCall(call);
            if (emp != null) {
                emp.receiveCall(call);
                System.out.println("Assigned call from " + call.getCallerId() + " to " + emp.getClass().getSimpleName());
            } else {
                System.out.println("No available employees. Queuing call from " + call.getCallerId());
                callQueue.add(call);
            }
        } finally {
            lock.unlock();
        }
    }

    // Helper to find the first available employee of appropriate rank or higher
    private Employee getHandlerForCall(Call call) {
        for (int level = call.getRank().getValue(); level < NUM_LEVELS; level++) {
            Queue<Employee> queue = employeeQueues.get(level);
            if (!queue.isEmpty()) {
                return queue.poll(); // Retrieve and remove the first available employee
            }
        }
        return null;
    }

    // Called when an employee finishes a call
    public void makeEmployeeFree(Employee emp) {
        lock.lock();
        try {
            System.out.println(emp.getClass().getSimpleName() + " is now free.");
            // Check if there is a waiting call that this employee can handle
            Call compatibleCall = findCompatibleCall(emp);
            if (compatibleCall != null) {
                callQueue.remove(compatibleCall);
                emp.receiveCall(compatibleCall);
                System.out.println("Assigned queued call from " + compatibleCall.getCallerId() + " to " + emp.getClass().getSimpleName());
            } else {
                // No waiting calls, return employee to their queue
                employeeQueues.get(emp.getRank().getValue()).add(emp);
            }
        } finally {
            lock.unlock();
        }
    }

    // Find the first call in the queue that this employee is qualified to handle
    private Call findCompatibleCall(Employee emp) {
        for (Call call : callQueue) {
            if (emp.getRank().getValue() >= call.getRank().getValue()) {
                return call;
            }
        }
        return null;
    }
}

Code Walkthrough

Let's trace how a call flows through our system:

1. Call Arrival: A call is created and passed to dispatchCall(Call call). We acquire a ReentrantLock to ensure that no other thread modifies our queues while we are routing this call.
2. Employee Lookup: getHandlerForCall() checks the queue corresponding to the call's required rank. If empty, it escalates the search to the next rank (e.g., if no Respondents are free, it checks Managers, then Directors).
3. Queuing: If no qualified employees are free, the call is added to callQueue.
4. Call Completion & Re-routing: When an employee finishes a call, they call completedCall(), which triggers makeEmployeeFree(). Instead of immediately going back to sleep, the employee checks the callQueue to see if there is a waiting call they are qualified to handle. If yes, they take it immediately. If not, they return to their respective availability queue.

Time & Space Complexity

Let's analyze the efficiency of our design to ensure it meets production standards.

• Time Complexity:
  • dispatchCall(): $O(1)$ average time. Since the number of levels is fixed (3), checking the queues is a constant-time operation.
  • makeEmployeeFree(): $O(C)$ where $C$ is the number of calls in the waiting queue. This is because we iterate through the waiting queue to find a compatible call. In practice, $C$ is small, but if it grows large, we could optimize this by maintaining separate waiting queues for each rank level, reducing this to $O(1)$.
• Space Complexity: $O(E + C)$ where $E$ is the total number of employees and $C$ is the number of active/queued calls. This is highly optimal as we only store references to active entities in memory.

Why This Problem Matters (The Senior Perspective)

This problem is a classic implementation of the Chain of Responsibility design pattern. In enterprise software, we use this pattern to decouple the sender of a request from its receivers by giving multiple objects a chance to handle the request. Real-world examples include:

• Logging Frameworks: A log message is passed down a chain (Debug -> Info -> Error). If a logger can handle that level, it processes it; otherwise, it passes it up.
• HTTP Middleware: In frameworks like Spring or Express, incoming requests pass through a chain of filters (Auth -> Rate Limiting -> Logging) before reaching the controller.

If we were building this for a production-grade cloud environment, we would transition from an in-memory queue to a distributed message broker like RabbitMQ or Apache Kafka. This would allow us to scale our "Employees" (which could be microservices or serverless workers) horizontally across multiple servers while maintaining strict FIFO ordering and fault tolerance.

Final Thoughts

Designing a call center is more than just writing classes; it is about managing state transitions, concurrency, and resource allocation cleanly. By using a queue-based approach and protecting our critical sections with locks, we built a system that is both highly performant and thread-safe.

As a next step, try extending this system: How would you implement a feature where a call is automatically disconnected if it sits in the queue for more than 5 minutes? (Hint: Look into scheduled executors or dead-letter queues).

Keep coding, keep designing, and we will see you in the next system design breakdown!