How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Onsite rounds at xAI.

What role is this question designed for?

This question is commonly asked for Machine Learning Engineer candidates at xAI during technical interviews.

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.

Input: ([], -1)

Expected Output: ([], 0)

Explanation: There are no nodes, so U is empty and no tests are performed.

Input: ([1], 0)

Expected Output: ([], 0)

Explanation: The only node is the known good node, so U is empty and there is nothing to test.

Input: ([0, 1, 1, 0, 1], 2)

Expected Output: ([0, 3], 7)

Explanation: U = [0, 1, 3, 4]. The full block fails, both halves are explored, and indices 0 and 3 are the failing singletons. The exact recursion makes 7 tests.

Input: ([0, 1], 1)

Expected Output: ([0], 1)

Explanation: U = [0]. The singleton block fails immediately, so index 0 is bad and exactly 1 test is used.

Solution

def solution(nodes, known_good):
    n = len(nodes)
    if n == 0:
        return ([], 0)

    u = [i for i in range(n) if i != known_good]
    m = len(u)
    if m == 0:
        return ([], 0)

    prefix_bad = [0] * (m + 1)
    for i, idx in enumerate(u):
        prefix_bad[i + 1] = prefix_bad[i] + (1 if nodes[idx] == 0 else 0)

    bad_indices = []
    test_calls = 0

    def has_bad(l, r):
        return prefix_bad[r] - prefix_bad[l] > 0

    def dfs(l, r):
        nonlocal test_calls
        if l >= r:
            return

        test_calls += 1

        if not has_bad(l, r):
            return

        if r - l == 1:
            bad_indices.append(u[l])
            return

        mid = l + (r - l) // 2
        dfs(l, mid)
        dfs(mid, r)

    dfs(0, m)
    return (bad_indices, test_calls)

Time complexity: O(n). Space complexity: O(n).

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.

Quick 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.