GPU Node Group Test — Identify Bad Nodes

There are `N` nodes, some good and some bad. You can call `test(S)` on a set `S` of nodes (with `|S| ≥ 2`) which returns `True` only if every node in `S` is good. Tests can run in parallel, but no node can appear in two concurrent tests at the same time. Identify all bad nodes as efficiently as possible. Requirements N nodes, each independently good or bad. API: test(S) → bool. Returns True iff every node in S is good. Returns False if S contains at least one bad node. Constraints: |S| ≥ 2 (you cannot test a single node directly), and the same node cannot participate in two parallel test calls simultaneously. Goal: identify every bad node. Discuss complexity in number of test calls and in wall-clock rounds when calls are parallelized. Canonical OA signature (the problem guarantees at least 2 good nodes always exist — with fewer, no test can disambiguate the lone good node): from typing import Set, Callable def find_faulty_nodes(n: int, test: Callable[[Set[int]], bool]) -> Set[int]: ... # nodes labeled 0..n-1; test(S) is True iff every node in S is good, and requires |S| >= 2. # Returns the set of faulty node indices. Notes The natural strategy is to first find one known-good node, then use it to test every other node in pairs (test({good, candidate}) is True iff candidate is good). Finding a good node fast: pair-test disjoint pairs in parallel. Any pair that returns True gives you two good nodes immediately. If all pairs are False, you have at least one bad node per pair, and a logarithmic split-and-test on a single pair still resolves quickly because |S| = 2 is the smallest legal set. Once a good node is known, the remaining N − 1 candidates can be tested in parallel — but each test occupies the good node, so the parallelism is bounded by how many copies of "good node + one candidate" you can run concurrently (which is 1, since the same node cannot be in two simultaneous tests). The trick: as soon as you confirm a second good node, you double parallelism; with g known-good nodes you can run g tests in parallel. Total tests: O(N). Parallel rounds: O(log N) once enough good nodes are known. When faults are rare, beat O(N) total tests with divide-and-conquer: once a known-good node exists, test whole halves — a half returning True is entirely clean and skipped, recursing only into dirty halves. This costs O(d log N) tests for d faulty nodes, near the information-theoretic limit (the same idea as COVID-19 pool testing). Be explicit about edge cases: more than N/2 nodes are bad (you cannot guarantee finding a good node by random pairing — fall back to a 3-way / k-way test). Production follow-ups the interviewer may push on: test can flake, so re-run a False result before trusting it; when parallel tests are expensive, prefer the divide-and-conquer variant to cut total test calls; and if some nodes are likelier bad (older hardware), test those first. Preparation Practice articulating both the sequential O(N) approach and the parallel O(log N) round-count. Be ready to handle the "more than half are bad" follow-up: a |S| = 3 test plus elimination quickly bounds the bad set. Sketch the algorithm as pseudo-code with a Pool.submit(test, S) style; the round wants to see you reason about the no-overlap constraint.