Filter Nodes by Taints and Tolerations
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:
nodes = [{"name":"n1","taints":[("gpu","true","NoSchedule")]}, {"name":"n2","taints":[]}]
print(schedulable_nodes(nodes, [("gpu","true")]))['n1', 'n2']
- Convert the input tolerations into a set for efficient lookup: tol={("gpu","true")}.
- Evaluate node "n1": Identify its
NoScheduletaints 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: ["n1","n2"].
- Sort the collected names alphabetically, which remains ["n1","n2"] in this case.
- The final output is ['n1', 'n2']
Constraints:
- Only
NoScheduletaints block scheduling. - A node is OK if every NoSchedule taint's (key,value) is in tolerations.
- Return node names sorted ascending.
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: ∀t∈NoScheduleTaints(node), (t.key,t.value)∈tolerations.
3. Step-by-Step Strategy
Continue the full explanation
You're reading the free preview. Unlock the complete walkthrough, the code editor, test runner and reference solution with Premium.
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.