Bin-Pack Pods onto Nodes
Problem Statement
The Kubernetes scheduler places a pod in two phases: filter the nodes that can fit the pod's resource requests, then score the survivors and pick the best. Reimplement that loop for a small cluster and report where every pod lands, which pods are stuck Pending, and how much capacity is left.
Background
A pod's requests are what the scheduler reserves — a node fits a pod only when its remaining CPU and remaining memory are both at least the pod's request. Nothing is overcommitted at schedule time.
Scoring here is the default LeastAllocated strategy: prefer the node with the most remaining CPU, so load spreads out instead of stacking on one machine. Ties go to the node that appears earlier in nodes.
Pods are processed strictly in the order given (a queue, one pod at a time), and each placement immediately shrinks that node's remaining capacity for the pods that follow. A pod that fits nowhere is unschedulable and reserves nothing — later, smaller pods can still be placed.
CPU is in millicores, memory in MiB, both integers.
Your Task
Implement:
def schedule_pods(nodes, pods):
Return a dict with keys, in this order:
- "placements": list of [pod_name, node_name] pairs, in the order pods were placed.
- "unschedulable": list of pod names that never fit, in input order.
- "remaining": list of [node_name, cpu_left, memory_left], one per node in the input node order.
Input Format
- nodes: list of dicts with "name", "cpu", "memory".
- pods: list of dicts with "name", "cpu", "memory".
Output Format
- The dict described above; all numbers are ints.
Sample
nodes = [{"name": "node-a", "cpu": 4000, "memory": 8192},
{"name": "node-b", "cpu": 4000, "memory": 8192}]
pods = [{"name": "infer-1", "cpu": 1500, "memory": 2048},
{"name": "infer-2", "cpu": 1500, "memory": 2048}]
print(schedule_pods(nodes, pods))
Output:
{'placements': [['infer-1', 'node-a'], ['infer-2', 'node-b']], 'unschedulable': [], 'remaining': [['node-a', 2500, 6144], ['node-b', 2500, 6144]]}
Both nodes tie on the first pod so node-a wins on order. That leaves node-a with 2500m against node-b's 4000m, so the second pod spreads to node-b.
Example:
nodes = [{"name": "node-a", "cpu": 4000, "memory": 8192}, {"name": "node-b", "cpu": 4000, "memory": 8192}]
pods = [{"name": "infer-1", "cpu": 1500, "memory": 2048}, {"name": "infer-2", "cpu": 1500, "memory": 2048}]
print(schedule_pods(nodes, pods)){'placements': [['infer-1', 'node-a'], ['infer-2', 'node-b']], 'unschedulable': [], 'remaining': [['node-a', 2500, 6144], ['node-b', 2500, 6144]]}Both nodes pass the filter for infer-1 and both have 4000m free, so the tie-break on input order sends it to node-a, leaving 2500m / 6144Mi there. For infer-2, node-b now has the most free CPU (4000m vs 2500m) and wins the score, so the replicas spread across nodes instead of stacking.
Constraints:
- 1 <= len(nodes) <= 20, 1 <= len(pods) <= 60
- CPU is in millicores, memory in MiB; all values are non-negative ints
- A node fits a pod only when remaining CPU AND remaining memory are both >= the request
- Score by most remaining CPU (LeastAllocated); ties broken by node order in
nodes - Pods are processed in the given order and placements are irrevocable — no backtracking
- An unschedulable pod consumes nothing and does not block later pods
1. Background Knowledge
This problem simulates the core logic of the Kubernetes Scheduler, specifically the Bin-Packing algorithm used in distributed systems. In Kubernetes, scheduling is a two-phase process: Filtering (predicates) and Scoring (priorities). Filtering eliminates nodes that cannot physically accommodate a pod's resource requests (CPU and memory). Scoring then ranks the remaining feasible nodes to select the optimal target. The LeastAllocated strategy mentioned is a common heuristic designed to balance load across the cluster, preventing "hotspots" where one node is overloaded while others remain idle.
Understanding resource constraints is critical. A node is only valid for a pod if its remaining capacity satisfies both CPU and memory requirements simultaneously. This is a multi-dimensional bin-packing problem, but simplified because the order of items (pods) is fixed. Unlike complex optimization problems where you might reorder items to maximize packing efficiency, here you must process pods strictly in the order they appear in the input queue. This makes the problem deterministic and sequential.
The concept of state mutation is also central. As each pod is placed, the node's available resources decrease immediately. This affects the feasibility of all subsequent pods. If a pod cannot fit on any node after filtering, it is marked as unschedulable (Pending). Importantly, unschedulable pods do not reserve resources; they simply skip the placement phase, allowing smaller subsequent pods to potentially fit on nodes that were previously full relative to the larger, stuck pod.
2. Algorithm Approach
The general approach is a Greedy Algorithm with a First-Fit variant based on a specific scoring metric. Since the order of pods is fixed, you iterate through the pod list one by one. For each pod, you perform two sub-steps:
- Filtering: Iterate through all nodes and check if the node's current remaining CPU and memory are greater than or equal to the pod's requests. Collect all nodes that pass this check.
- Scoring: If the list of feasible nodes is not empty, select the best node based on the LeastAllocated strategy. This means choosing the node with the maximum remaining CPU. If there is a tie in remaining CPU, the tie-breaker is the node's original index in the input list (lower index wins).
If no nodes pass the filtering step, the pod is added to the unschedulable list. If a node is selected, you update that node's remaining resources and record the placement. This process repeats for every pod in the input list.
3. Step-by-Step Strategy
- Initialize State: Create a mutable copy of the nodes list to track remaining resources. It is helpful to store nodes as objects or dictionaries with keys name, remaining_cpu, and remaining_memory. Initialize placements and unschedulable as empty lists.
- Iterate Through Pods: Loop through each pod in the pods list in order.
- Filter Feasible Nodes: For the current pod, create a list of candidate nodes. A node is a candidate if:
- node.remaining_cpu >= pod.cpu
- node.remaining_memory >= pod.memory
- Select Best Node:
- If the candidate list is empty, append the pod's name to unschedulable and continue to the next pod.
- If candidates exist, find the node with the highest remaining_cpu.
- Tie-Breaking: If multiple nodes have the same highest remaining_cpu, select the one that appears earliest in the original nodes list. You can achieve this by iterating through the original node list and checking feasibility, keeping track of the best node found so far.
- Update State: Once the best node is selected:
- Subtract the pod's CPU and memory requests from the node's remaining resources.
- Append [pod.name, node.name] to the placements list.
- Finalize Output: After processing all pods, construct the remaining list by iterating through the original node order and extracting the final remaining_cpu and remaining_memory for each. Return the dictionary with placements, unschedulable, and remaining.
4. Common Pitfalls
- Modifying Original Data: Be careful not to modify the original nodes input list directly if it is needed for the final output order. Use a separate data structure to track remaining resources, or ensure you can reconstruct the final state correctly.
- Tie-Breaking Logic: The problem specifies that ties in CPU go to the node appearing earlier in the input. A common mistake is using a standard max() function with a key, which might not guarantee stable ordering or might pick the last occurrence depending on implementation. Explicitly iterating and comparing indices is safer.
- Resource Units: Ensure you are comparing integers correctly. CPU is in millicores and memory in MiB. Do not convert units unless necessary; just compare the raw integers provided.
- Unschedulable Pods: Remember that unschedulable pods do not consume resources. Do not subtract their requests from any node. They simply fail to place and move on.
- Order of Operations: The problem states pods are processed in order. Do not sort pods by size or any other metric. The greedy choice is made per pod in the input sequence.
5. Time & Space Complexity
Let N be the number of nodes and P be the number of pods.
- Time Complexity: O(P×N). For each of the P pods, you iterate through all N nodes to filter and score. The filtering and scoring steps are linear with respect to the number of nodes. Since N and P are typically small in these problems, this is efficient.
- Space Complexity: O(N+P). You need space to store the mutable state of the N nodes (remaining resources) and the output lists (placements and unschedulable), which can grow up to size P. The remaining list also takes O(N) space.