About this question

Load Balancing with Two Choices

Hard · Probability & Statistics · Quant Trader interview question · probability, load-balancing, algorithms, asymptotic-analysis

You are designing a distributed system for processing incoming requests. You have $n$ servers (bins) and $n$ requests (balls). Each request is assigned to a server using a load balancing strategy. Strategy 1: For each request, you randomly select one server and assign the request to it. It is known that the maximum load (number of requests assigned to any server) is $O(\frac{\log n}{\log \log n})$. Strategy 2: For each request, you randomly select two servers independently and assign the request