Identify all bad nodes with group tests
Company: xAI
Role: Machine Learning Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
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) = True` iff **all nodes in S are good**.
- `test(S) = False` iff **S contains at least one bad node**.
## Constraints
1. You may run multiple `test(...)` calls **in parallel rounds**.
2. In the same parallel round, **a node cannot appear in more than one test** (tests must be node-disjoint within a round).
3. 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 `test` calls, and/or
- number of parallel rounds (depth), given the disjointness constraint.
- Time/round complexity analysis and edge cases.
Quick Answer: 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.
You have N nodes. Each node is either good or bad. In the original interview version, you only learn information through a function test(S), which returns True iff every node in S is good, and False otherwise. Because single-node tests are forbidden, the problem is not always identifiable unless you already know at least one good node. So in this coding version, you are given an array nodes where nodes[i] is 1 for a good node and 0 for a bad node, plus an index known_good that is guaranteed to point to a good node (or -1 when the array is empty). Implement the following deterministic strategy and return both the bad indices and the number of test calls it performs:
1. Let U be all indices except known_good, in increasing order.
2. To process a non-empty block B of U, perform one conceptual test on {known_good} union B.
3. If the test passes, then every node in B is good.
4. If the test fails and |B| = 1, that node is bad.
5. Otherwise split B into two halves in its current order: left half has floor(|B|/2) elements, right half gets the rest. Process the left half first, then the right half.
Return a tuple (bad_indices, test_calls), where bad_indices is sorted in increasing order. Note: for this exact strategy, reusing the same trusted good node means the number of parallel rounds equals the number of test calls under the node-disjoint-per-round rule.
Constraints
- 0 <= len(nodes) <= 200000
- Each nodes[i] is either 0 or 1
- If len(nodes) == 0, then known_good == -1
- If len(nodes) > 0, then 0 <= known_good < len(nodes) and nodes[known_good] == 1
Examples
Input: ([1, 1, 0, 1, 0, 1], 0)
Expected Output: ([2, 4], 9)
Explanation: U = [1, 2, 3, 4, 5]. The full block fails, then the recursion explores both halves. Only indices 2 and 4 end up as failing singletons. The exact strategy performs 9 tests.
Input: ([1, 1, 1, 1], 2)
Expected Output: ([], 1)
Explanation: U = [0, 1, 3]. The first test on the entire block passes, so all remaining nodes are good and recursion stops immediately.
Hints
- A known-good node turns test({known_good} ∪ B) into an all-good check for the whole block B.
- If a block fails, do not inspect every element immediately. Split the block in half and recurse; a failing block of size 1 pinpoints a bad node.