Scanning every backend for every request becomes expensive when a pool contains thousands of servers. Power of two choices, or P2C, samples two healthy candidates and assigns the request to the less loaded one.
Design a PowerOfTwoBalancer class:
PowerOfTwoBalancer(int backendCount) creates backends 0 through backendCount - 1, each with zero active requests.int acquire(int first, int second) compares the two supplied candidate backends, selects the one with fewer active requests, increments its count, and returns it.void release(int backend) decrements one active-request count without allowing it below zero.
first and second are distinct. They represent candidates already sampled by the load balancer, which keeps this exercise deterministic. If their active counts tie, select the smaller backend index.
Example 1:
Input:
Output:
Explanation: The fifth acquisition compares backends 3 and 1 when both have one active request. Backend 1 wins because tie-breaking uses backend index, not argument order.
Example 2:
Input:
Output:
Explanation: Releases affect later comparisons immediately. An extra release on an idle backend leaves its count at zero.
Constraints
2 <= backendCount <= 10^50 <= first, second, backend < backendCountfirst != second- At most
10^5 total calls are made to acquire and release. - A release on an idle backend leaves its count at
0.
Implement Power of Two Choicesmedium