Q4 - Rebalancing a Cache Cluster

Scenario: Google runs a cluster of n cache servers laid out in a row. Server i currently holds load[i] cached items. To rebalance, in one step a server hands a single item to a neighbor sitting directly beside it.

Every server should end up holding the same number of items (the total is guaranteed to divide evenly by n).

Your task: Return the minimum number of handoffs needed to level out the cluster.

Input:  load = [4, 4, 0, 0, 2]
Output: 8
Why: the target is 2 each (10 items over 5 servers), so the deviations are [+2, +2, -2, -2, 0].
        In a row, each gap must carry the running surplus on its left: |2| + |4| + |2| + |0| = 8.

Input:  load = [3, 3, 3]
Output: 0
Why: every server already holds the target of 3, so there is nothing to move.

Part 1: A Single Rack Row

Start where the interviewer starts. The servers sit in a row, so each one only touches the neighbor on its left and its right, and the two ends do not wrap. Your first instinct might be to simulate the moves; resist it. The number of ways to shuffle items explodes, and you do not need any of them, because the answer is pinned down by the layout. It falls out in three steps.

Step 1: Find the target and each server's deviation

Everything levels to the same value, average = total / n. What matters per server is not its raw load but how far it sits from that target, its deviation load[i] - average. A positive deviation is a surplus to ship out; a negative one is a deficit to fill.

load =        [ 4,  4,  0,  0,  2 ]     target = 10 / 5 = 2
deviation =   [+2, +2, -2, -2,  0 ]     (load[i] - 2)

Step 2: Each gap carries the running surplus to its left

Between server i and server i + 1 there is exactly one gap, and it is the only path items can take between the left part of the row and the right part. So if the first i + 1 servers hold a combined surplus S above target, every one of those S items has to cross that single gap: exactly |S| handoffs, no more, no fewer. And S is just the running total of the deviations.

running surplus S at each gap (prefix sum of the deviations):

   gap after server 0:   +2               =  2    ->  2 items cross
   gap after server 1:   +2 +2            =  4    ->  4 items cross
   gap after server 2:   +2 +2 -2         =  2    ->  2 items cross
   gap after server 3:   +2 +2 -2 -2      =  0    ->  0 items cross

Step 3: Sum the absolute gap loads

Add |S| across every gap. That total is the minimum number of handoffs.

answer = |2| + |4| + |2| + |0| = 8

The whole computation is one pass: carry the running surplus, and add its absolute value at each gap.

prefix = 0                      # running surplus that must cross the current gap
moves = 0
for i in range(n - 1):          # a row of n servers has n - 1 gaps
    prefix += load[i] - average
    moves += abs(prefix)

Watch it run on Example 1. Each gap simply carries the running surplus to its left, and you add those up:

1 / 4

# O(n) time | O(1) extra space
def min_line_moves(load):
    n = len(load)
    average = sum(load) // n
    prefix = 0                      # running surplus = items that must cross the current gap
    moves = 0
    for i in range(n - 1):          # a row of n servers has n - 1 gaps
        prefix += load[i] - average
        moves += abs(prefix)
    return moves

Part 2: The Real Ring

Nailed the row? Good, because this is the version the interviewer actually cares about. In production the cache is not a row, it is a consistent-hash ring: the servers sit in a circle, so the last one is a neighbor of the first. You have one more gap to work with, the one that wraps around.

Input:  load = [4, 4, 0, 0, 2]    (now a ring: server 4 is also next to server 0)
Output: 6
Why: same servers as Example 1, but routing some of the surplus the short way around the
        loop levels everything in 6 handoffs, two fewer than the 8 the row needed.

That extra gap changes everything, and it comes down to two steps.

Step 1: One free choice shifts every gap

On the row, every gap's load was forced. On the ring there is a loop, so now you get one free choice: how much charge, t, to send across the wrap gap (and in which direction). Pushing t around the loop shifts every gap by the same t, so gap i now carries S[i] - t instead of S[i], where S is the prefix sums from Part 1, all n of them now, since the wrap adds the last gap.

prefix sums of the deviations, now n of them:   S = [ 2, 4, 2, 0, 0 ]

send t around the loop, and gap i carries |S[i] - t|:
   t = 0  (same as the row):   |2| + |4| + |2| + |0| + |0|  =  8

Step 2: The best t is the median

Minimizing a sum of absolute distances |S[i] - t| has a famous answer: the best t is the median of the S values. So sort the prefix sums, take the middle one, and sum the absolute deviations from it.

sort S = [ 0, 0, 2, 2, 4 ],   median = 2

cost at t = 2:   |2-2| + |4-2| + |2-2| + |0-2| + |0-2|  =  0 + 2 + 0 + 2 + 2  =  6

Watch that shift sweep across the ring. The five gap values get one shared t, and the median is the shift that makes the total smallest:

1 / 5

# O(n log n) time | O(n) space   (O(n) if you use quickselect for the median)
def min_ring_moves(load):
    n = len(load)
    average = sum(load) // n
    prefix, running_sum = [], 0
    for x in load:
        running_sum += x - average
        prefix.append(running_sum)          # prefix[n - 1] is always 0
    prefix.sort()
    median = prefix[n // 2]
    return sum(abs(p - median) for p in prefix)

Picking the median is the whole move. It is the kind of small, clean insight Google interviewers like to watch you reach for out loud.

Complexity Analysis

Part 1 (the row): O(n) time and O(1) extra space. One pass with a running total, nothing stored.

Part 2 (the ring): O(n log n) time if you sort the prefix sums for the median, or O(n) with quickselect; O(n) space for the prefix array. Both beat any attempt to search over t directly. (Use 64-bit integers for the totals, since the loads can be large.)

Final Notes

1. On a line, every cut is forced. The single gap between two halves must carry the entire surplus of one side, so the cost is just the sum of the absolute prefix sums of the deviations. Realizing there is no choice to make is the unlock for Part 1.
2. A loop buys you one free variable. The ring adds a single degree of freedom (how much flows around the wrap), which shifts all the gap loads by the same t. Spotting that free variable is the leap from Part 1 to Part 2.
3. Minimizing a sum of absolute distances means the median. This little fact shows up everywhere (meeting points, 1D clustering, this). The moment the cost looked like sum of |S[i] - t|, the answer was the median of S. Keep that pairing handy.
4. Talk through the line first, even though the ring is the real question. Solving the row cleanly is what hands you the prefix sums you need for the ring. Stating it out loud, then extending it, reads far better than jumping straight to the clever bit.

The jump from line to ring is what this question turns on: one extra edge, one free variable, and the answer becomes the median of the prefix sums. Google likes questions where a tiny change in the setup demands a new idea, so keep this one in your pocket. 🚀