Google·Software Engineer·Technical Phone Screen·Senior

Senior

Jun 2026

Summary

Google SWE interview with a tricky black-box debugging puzzle that pushed well beyond brute force. The core challenge was finding two 'poisoned' test cases using as few calls as possible, and the conversation quickly escalated into algorithm design territory.

Questions Asked (1)

You have a black-box function that takes a list of test cases and returns pass or fail. Exactly two test cases are 'poisoned': the function only fails when both are present simultaneously. Given the full list, find the two poisoned test cases while minimizing the number of calls to the function. Can you do better than O(n^2)?

Algorithms & Data StructuresTechnical Trade-offs

Author's notes

My first instinct was just pair every test case with every other and call it a day.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Model the problem as finding a unique pair in a set where the oracle returns true only for that pair. Use a divide-and-conquer strategy to isolate the two poisoned tests by splitting the list and testing subsets, achieving O(n log n) calls. Alternatively, use group testing with binary encoding to identify the pair in O(log n) calls by assigning each test a unique bit pattern and testing groups based on bits.

Pro tip: Clarify the oracle's behavior: it returns 'fail' only when both poisoned tests are in the input list; otherwise it returns 'pass'. This binary output allows efficient group testing. Also, mention that if the function's failure is not guaranteed to be deterministic or if there are constraints on the number of tests, the approach may vary.

1. Understand the problem and constraints

Restate the problem: exactly two poisoned tests cause failure only when both are present. The goal is to minimize calls to the black-box function. Confirm that the function returns a boolean and that we can test any subset of the full list.

2. Consider naive approaches and their complexity

A brute-force pairwise check would require O(n^2) calls. We need a better strategy. Think about divide-and-conquer or group testing to reduce calls.

3. Design a divide-and-conquer algorithm

Split the list into two halves. Test each half: if a half fails, it contains both poisoned tests; if it passes, it contains at most one. Recursively narrow down until the pair is found. This yields O(n log n) calls in the worst case.

4. Explore group testing with binary encoding

Assign each test a unique binary code of length k = ceil(log2 n). For each bit position, test the group of tests with that bit set to 1. The pattern of failures across these k tests reveals the two poisoned tests via their bitwise XOR. This uses O(log n) calls.

5. Compare and discuss trade-offs

Compare the O(n log n) divide-and-conquer and O(log n) group testing approaches. Discuss assumptions: group testing requires that the function fails only when both are present, and that we can test arbitrary subsets. Mention that group testing is optimal in terms of calls but may require more complex setup.

Key Points to Mention

The problem is equivalent to finding a unique pair in a set with a boolean oracle that returns true only for that pair.
Divide-and-conquer can reduce calls to O(n log n) by recursively testing halves.
Group testing with binary encoding can achieve O(log n) calls by testing groups based on bit positions.
The XOR of the two poisoned tests' binary codes equals the pattern of failures across bit tests.
Assumptions: the function is deterministic, and we can test any subset of the full list.
Trade-offs: O(log n) is optimal but may require more calls if n is small; O(n log n) is simpler to implement.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.