Identify all bad nodes with group tests
Overview
This question evaluates a candidate's skills in combinatorial group testing, parallel algorithm design under node-disjoint constraints, and complexity reasoning for identifying faulty elements.
xAI
Sep 22, 2025, 12:00 AM
Machine Learning Engineer
Onsite
Coding & Algorithms
0
0
You have N nodes. Each node is either good or bad (unknown to you).
You can call a function test(S) on a subset of nodes S:
-
test(S) = Trueiff all nodes in S are good . -
test(S) = Falseiff S contains at least one bad node .
Constraints
-
You may run multiple
test(...)calls in parallel rounds . - In the same parallel round, a node cannot appear in more than one test (tests must be node-disjoint within a round).
-
Each test must satisfy
|S| >= 2(you cannot test a single node).
Goal
Design an algorithm to identify all bad nodes.
What to discuss
- Any assumptions needed for identifiability (e.g., whether at least one good node exists).
-
Strategy to minimize:
-
total number of
testcalls, and/or - number of parallel rounds (depth), given the disjointness constraint.
-
total number of
- Time/round complexity analysis and edge cases.