Minimize calls to find all bad test pairs
Company: Google
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
You have \(n\) atomic tests \(t_1, t_2, \dots, t_n\).
You are given access to a black-box function:
```python
bool runTest(set<Test> S)
```
which behaves as follows:
- `runTest(S) == True` if the subset \(S\) contains **no** incompatible (bad) pair of tests.
- `runTest(S) == False` if the subset \(S\) contains **at least one** incompatible (bad) pair of tests.
There is some unknown set of unordered **bad pairs** \((t_i, t_j)\), where \(i \ne j\). You do **not** know in advance which pairs are bad or how many bad pairs there are.
Your goal is to discover **all** bad pairs while making as few calls to `runTest` as possible. You may adaptively choose each subset \(S\) based on the results of previous calls.
### Tasks
1. Design an algorithm that, using only calls to `runTest`, finds **all** bad pairs \((t_i, t_j)\).
2. Analyze the number of calls to `runTest` your algorithm requires, as a function of:
- \(n\): the total number of tests, and
- \(k\): the total number of bad pairs.
3. Argue why your algorithm is correct (i.e., why it will eventually find every bad pair and not report any good pair as bad).
You do not need to provide full production code, but describe the algorithm clearly enough that it could be implemented.
Quick Answer: This question evaluates a candidate's competency in algorithm design and query complexity, focusing on adaptive group-testing, combinatorial search, and reasoning about information-theoretic bounds for identifying defective test pairs.
You have n atomic tests numbered 0 to n - 1. Some unknown unordered pairs of tests are incompatible, called bad pairs. A black-box oracle runTest(S) returns True if the subset S contains no bad pair, and False if S contains at least one bad pair.
In this non-interactive version, you are given bad_pairs only so your code can simulate the oracle. Implement the following deterministic oracle-discovery strategy and return both the bad pairs it discovers and the number of oracle calls it makes.
Strategy:
1. Process vertices from right to left: v = n - 1, n - 2, ..., 0.
2. Maintain all bad pairs already discovered among vertices greater than the current v.
3. For the suffix vertices v + 1 through n - 1, greedily partition them into color classes such that no discovered bad pair appears inside one color class. Since all suffix-suffix bad pairs have already been discovered, every color class is truly compatible internally.
4. For each color class C, find all bad partners of v inside C using recursive group testing:
- Call runTest({v} union C).
- If the oracle returns True, v has no bad pair with any test in C.
- If C has size 1 and the oracle returns False, that single pair is bad.
- Otherwise split C into two halves and recurse on both halves.
Return all discovered bad pairs sorted lexicographically, where each pair is represented as [i, j] with i < j, along with the exact number of runTest calls made by this strategy.
Constraints
- 0 <= n <= 500
- 0 <= len(bad_pairs) <= n * (n - 1) / 2
- Each bad pair contains two distinct test indices in the range [0, n - 1]
- bad_pairs may be given in any endpoint order
Examples
Input: (0, [])
Expected Output: ([], 0)
Explanation: There are no tests and therefore no oracle calls are needed.
Input: (4, [])
Expected Output: ([], 3)
Explanation: For v = 2, 1, and 0, the algorithm queries the compatible suffix once and finds no bad pairs. v = 3 has an empty suffix.
Input: (4, [(0, 2)])
Expected Output: ([[0, 2]], 7)
Explanation: The single bad pair is found while processing v = 0. Recursive group testing splits the suffix until test 2 is isolated.
Input: (5, [(4, 0), (1, 3), (4, 1), (2, 4)])
Expected Output: ([[0, 4], [1, 3], [1, 4], [2, 4]], 12)
Explanation: The input pairs are unordered, but the output normalizes and sorts them. The suffix-coloring strategy makes exactly 12 oracle calls.
Input: (4, [(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)])
Expected Output: ([[0, 1], [0, 2], [0, 3], [1, 2], [1, 3], [2, 3]], 6)
Explanation: Every pair is bad. Each suffix color class becomes a singleton, so each oracle call directly identifies one bad pair.
Hints
- If a candidate set C is internally compatible, then runTest({v} union C) tells you whether v conflicts with at least one element of C.
- Process tests from right to left so that when handling v, all bad pairs inside the suffix v + 1 ... n - 1 are already known and can be used to build compatible groups.