Find Servers That Handled Most Number of Requests

Find Servers That Handled Most Number of Requests

What is this problem about?

The Find Servers That Handled Most Number of Requests interview question is a load-balancing simulation. You have $k$ servers and a stream of requests. Each request arrives at time $t$ and takes $d$ time to process. A request is assigned to server (i % k) if it's free. If not, you check server (i+1) % k, and so on, until you find a free server or check all $k$. You need to find which server(s) handled the maximum number of requests.

Why is this asked in interviews?

Companies like Amazon and Cisco ask this to test your ability to manage multiple dynamic states. It requires tracking both "when each server becomes free" and "which servers are currently available." It evaluates proficiency with Heap (Priority Queue) and Ordered Set data structures.

Algorithmic pattern used

This problem follows the Two-Structure Priority Queue pattern.

1. Busy Servers: Use a Min-Heap to store (free_time, server_id) for servers currently working.
2. Available Servers: Use an Ordered Set (like TreeSet in Java) or two heaps to store IDs of servers that are currently idle.
3. Logic for Request $i$ at time $t$:
   • Move all servers from "Busy" to "Available" if their free_time <= t.
   • In the "Available" set, search for the smallest server ID $\geq i \% k$.
   • If not found, pick the smallest overall ID in the set (wrap around).
   • If a server is found, increment its count and move it to "Busy" with free_time = t + duration.

Example explanation

$k=3$, Requests: (t:1, d:5), (t:2, d:2), (t:3, d:3)

1. Request 0 ($t=1$): All free. $0 \% 3 = 0$. Server 0 takes it. Busy: {(6, 0)}.
2. Request 1 ($t=2$): Server 0 is busy. $1 \% 3 = 1$. Server 1 takes it. Busy: {(6, 0), (4, 1)}.
3. Request 2 ($t=3$): Servers 0, 1 busy. $2 \% 3 = 2$. Server 2 takes it. All servers handled 1 request.

Common mistakes candidates make

• Linear Search: Checking servers one by one for every request ($O(N imes K)$), which fails for large $k$. The Ordered Set makes this $O(N \log K)$.
• Wrap-around logic: Failing to correctly implement the search for "first server $\geq i \% k$."
• Heap management: Not clearing all free servers from the busy heap before trying to assign the current request.

Interview preparation tip

Master the use of Sorted Sets (TreeSet in Java, std::set in C++). They are essential for "next available" problems where you need to search for a value greater than or equal to a target in a dynamic collection.