Filter Nodes by Taints and Tolerations

mediumPROKubernetes Scheduling & RolloutsSystems & InfrastructureML Systems & Infrastructure 1

Problem Statement

A pod can only schedule onto nodes whose NoSchedule taints it tolerates. Return the names of schedulable nodes.

Background

Each node has a list of taints (key, value, effect). Only effect == "NoSchedule" taints block scheduling. A pod carries tolerations (key, value). A node is schedulable if for every one of its NoSchedule taints, the pod has a matching toleration (same key and value). Taints with other effects are ignored here.

Your Task

def schedulable_nodes(nodes, tolerations):

nodes: list of {"name": str, "taints": [(key, value, effect), ...]}.
tolerations: list of (key, value) tuples.
Return the sorted list of schedulable node names.

Input Format

nodes (list of dicts), tolerations (list of tuples).

Output Format

A sorted list of strings.

Sample

nodes = [{"name":"n1","taints":[("gpu","true","NoSchedule")]}, {"name":"n2","taints":[]}]
print(schedulable_nodes(nodes, [("gpu","true")]))

Output:

['n1', 'n2']

Example

Input

nodes = [{"name":"n1","taints":[("gpu","true","NoSchedule")]}, {"name":"n2","taints":[]}]
print(schedulable_nodes(nodes, [("gpu","true")]))

Output

['n1', 'n2']

Reasoning

Convert the input tolerations into a set for efficient lookup: $\text{tol} = \{(\text{"gpu"}, \text{"true"})\}$ .
Evaluate node "n1": Identify its NoSchedule taints as $[("gpu", "true")]$ . Since the pair $("gpu", "true")$ exists in the toleration set, the node is schedulable.
Evaluate node "n2": It has an empty taint list, so there are no blocking taints. The condition is vacuously true, making the node schedulable.
Collect the names of all schedulable nodes: $[\text{"n1"}, \text{"n2"}]$ .
Sort the collected names alphabetically, which remains $[\text{"n1"}, \text{"n2"}]$ in this case.
The final output is ['n1', 'n2']

Constraints

Only NoSchedule taints block scheduling.
A node is OK if every NoSchedule taint's (key,value) is in tolerations.
Return node names sorted ascending.

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, taints are applied to nodes to repel pods that are not explicitly allowed to schedule there. A taint is a triple of (key, value, effect). The effect field determines how the taint influences scheduling. The most common effect for this problem is NoSchedule, which prevents new pods from being scheduled onto the node unless they carry a matching toleration. Other effects like NoExecute or PreferNoSchedule exist, but per the problem statement, only NoSchedule taints are relevant; all others should be ignored.

A toleration is a (key, value) pair carried by a pod. For a pod to tolerate a specific NoSchedule taint, the pod must have a toleration whose key and value both match the taint's key and value exactly. If a node has multiple NoSchedule taints, the pod must tolerate every one of them. If a node has no NoSchedule taints, it is trivially schedulable for any pod.

This problem models the core scheduling constraint check: given a set of nodes with taints and a pod's tolerations, determine which nodes the pod can land on. It is a filtering problem where each node is independently evaluated against the toleration set.

2. Algorithm Approach

The approach is a straightforward filtering pattern:

Convert the list of tolerations into a set of (key, value) tuples for $O(1)$ lookup.
For each node, extract only the taints where effect == "NoSchedule".
Check whether every such taint's (key, value) pair exists in the toleration set.
If the check passes, add the node's name to the result list.
Return the result list sorted alphabetically.

This is essentially a universal quantification check: $\forall t \in \text{NoScheduleTaints(node)},\ (t.\text{key}, t.\text{value}) \in \text{tolerations}$ .

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.