Spread Pods Across Zones for Anti-Affinity

mediumPROKubernetes Scheduling & RolloutsSystems & InfrastructureML Systems & Infrastructure 1

Problem Statement

To satisfy topology spread constraints, place pods across zones so the difference between the most-loaded and least-loaded zone stays minimal. Report the max skew after greedily placing each pod in the currently-least-loaded zone.

Background

Given zones (each starting with some existing pod count) and a number of new pods to place, assign each new pod one at a time to the zone with the fewest pods (ties broken by zone index). After placing all, the skew is max(counts) - min(counts).

Your Task

def max_skew(initial, new_pods):

initial: list of ints, current pod count per zone.
new_pods: int, pods to place.
Return the final skew (int).

Input Format

initial (list of ints), new_pods (int).

Output Format

A single int.

Sample

print(max_skew([0, 0, 2], 3))

Output:

Example

Input

print(max_skew([0, 0, 2], 3))

Output

Reasoning

Start with the initial zone counts $[0, 0, 2]$ and identify the zone with the fewest pods to place the first of the 3 new pods. Zones 0 and 1 are tied at 0, so the pod goes to Zone 0 (lowest index), updating counts to $[1, 0, 2]$ .
Place the second pod in the currently least-loaded zone. Zone 1 has 0 pods, which is less than Zone 0 (1) and Zone 2 (2), so the pod goes to Zone 1, updating counts to $[1, 1, 2]$ .
Place the third pod in the least-loaded zone. Zones 0 and 1 are tied at 1 pod, so the pod goes to Zone 0 (lowest index), updating counts to $[2, 1, 2]$ .
Calculate the final skew by finding the difference between the maximum and minimum pod counts in the final state $[2, 1, 2]$ : $\text{skew} = \max(2, 1, 2) - \min(2, 1, 2) = 2 - 1 = 1$ .
The final output is 1

Constraints

Place each pod into the least-loaded zone (ties: smaller index).
Skew = max(counts) - min(counts) after all placements.
initial is non-empty.

Learn this in

Orchestration & ScalingSystems & Networking

More from ML Systems & Infrastructure 1

Spot vs On-Demand Expected-Cost Decisionmedium Minimum-Cost Job Scheduling Across Priced Windowshard Deduplicate Retried Pipeline Runs by Idempotency Keymedium Retry with Capped Exponential Backoff and Jitter Capmedium Critical Path Length of a Pipeline DAGmedium

Concept primerPREVIEW

1. Background Knowledge

In Kubernetes, topology spread constraints ensure that pods are distributed evenly across failure domains (zones, nodes, racks) to improve fault tolerance. The core metric is skew, defined as the difference between the maximum and minimum pod counts across all zones. A skew of 0 means perfect balance; a higher skew indicates uneven distribution.

This problem models a greedy load-balancing scenario. Instead of solving a complex optimization problem, we use a simple heuristic: always place the next pod in the zone with the fewest pods. This is analogous to the Huffman coding or Dijkstra's algorithm pattern where we repeatedly extract the minimum element from a collection. The greedy choice is locally optimal and, for this specific problem, leads to a globally optimal (or near-optimal) skew.

The key insight is that we don't need to simulate every pod placement if we can reason about the final state. However, since the problem asks us to "greedily place each pod," a direct simulation is acceptable and often clearer. The tie-breaking rule (lowest zone index) ensures determinism when multiple zones have the same count.

2. Algorithm Approach

The approach is a greedy simulation using a min-heap (priority queue) for efficient minimum extraction.

Initialize: Create a min-heap containing tuples of (pod_count, zone_index) for each zone. The heap property ensures the smallest count is always at the root.
Simulate Placement: For each of the new_pods pods:

Extract the zone with the minimum count from the heap.
Increment that zone's count by 1.
Push the updated (new_count, zone_index) back into the heap.

Compute Skew: After all pods are placed, extract all counts from the heap (or track them separately) and compute max(counts) - min(counts).

Alternatively, since the number of zones is typically small, a simple linear scan to find the minimum each time is sufficient and avoids heap overhead.

3. Step-by-Step Strategy

PRO

Continue the full explanation

You're reading the free preview. Unlock the complete walkthrough, the code editor, test runner and reference solution with Premium.

PRO

Editor locked

The code editor is locked for Pro problems. It is only available for free problems. Please upgrade to gain access to the code editor for all problems.

solution.py

Python 3.13

Test results