Find All Faulty GPU Nodes with Parallel Group Tests That Cannot Share Nodes
Company: xAI
Role: Machine Learning Engineer
Category: Software Engineering Fundamentals
Difficulty: medium
Interview Round: Onsite
A cluster has `n` GPU nodes, numbered `0` to `n - 1`, and some of them are bad. The only diagnostic is a group test: `test(S)` runs a job on a set `S` of nodes and returns `False` if at least one node in `S` is bad, or `True` if every node in `S` is good.
Tests can run in parallel, with two restrictions:
- a node cannot take part in two tests that run at the same time;
- every test must include at least two nodes (`|S| >= 2`).
Design an algorithm that identifies exactly which nodes are bad, as efficiently as possible, and implement it. Model the parallelism as rounds: one call to `run_tests` is one round of tests running at the same time.
```python
def run_tests(groups: list[list[int]]) -> list[bool]:
"""Runs every group as one parallel round and returns one result per group.
Groups in one call must be pairwise disjoint, and each must contain at least two nodes."""
def find_bad_nodes(n: int, run_tests) -> set[int]:
...
```
```hint What a failure means
Consider how the meaning of a failing test changes depending on what you already know about the other nodes in it.
```
```hint Count rounds, not only tests
Once you have a strategy that works, ask how many nodes it can resolve in one round, and how that number can grow from one round to the next.
```
### Constraints and Clarifications
- Tests are reliable: the same set always gives the same result.
- A node's status does not change while the procedure runs.
- The procedure must return the exact set of bad nodes whenever the test results make that set identifiable.
### Clarifying Questions
- What does "efficient" mean here: the number of parallel rounds (wall-clock time), the total number of tests (cluster time), or both?
- Is there a known bound on, or an estimate of, how many nodes are bad?
- Does a test's duration or reliability depend on how many nodes it includes?
- Is at least one good node, or a pair of good nodes, guaranteed? What should happen if nearly every node is bad?
- May one round mix tests of different sizes, and may a node sit out a round?
### What a Strong Answer Covers
- How a test result is interpreted, and why a node already known to be good turns a group test into a test of a single node
- A strategy for finding the first good nodes, with its cost when bad nodes are common
- A round schedule that respects disjointness and the minimum group size
- A correctness argument: every node is classified, and every inference is justified
- Cost in both rounds and tests, when bad nodes are rare and when they are common
- The case in which the bad set cannot be identified at all
- How the approach would change if the test itself could be flaky
### Follow-up Questions
- If you know that only a handful of the `n` nodes are bad, how can you use far fewer tests than one per node?
- Tests become flaky: a set of good nodes occasionally fails. How do you adapt, and how confident can you be in each verdict?
- A test's duration grows with the number of nodes in it. How does that change your choice of group sizes?
- How would you run this continuously on a production cluster where nodes join, leave and fail over time?
Overview: An algorithm design question about finding every faulty GPU node when the only tool is a group test that fails if any node in the set is bad. Tests need at least two nodes and parallel tests cannot share nodes, so it tests adaptive testing strategies, identifiability, and cost in rounds and tests.