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 hard difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Google.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Google during technical interviews.

Find conflicting pair using black-box run()

Company: Google

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Onsite

## Problem You are given a list `tests` of **n distinct test cases** (you can treat them as IDs or objects). You also have access to a **black-box** function: - `run(subset)` → returns **PASS** or **FAIL** `subset` is any list (or set) of test cases chosen from `tests`. ### Hidden property There exist **exactly two distinct test cases** `a` and `b` in `tests` such that: - `run(S)` returns **FAIL** **iff** both `a` and `b` are included in `S`. - If `S` contains **only one** of `{a, b}`, or **neither**, then `run(S)` returns **PASS**. In other words, the failure is caused only by the **interaction** of a specific pair; each test passes on its own. ## Task Return the two failing-interaction test cases `(a, b)` (or their indices in `tests`). ## Constraints / notes - You may call `run()` on any subsets you choose. - Assume `run()` is expensive; your goal is to minimize the number of calls. - `n` can be large (e.g., up to 10^5), so solutions that are \(O(n^2)\) in calls are not acceptable. ## Output Return the pair `{a, b}` (order does not matter).

Quick Answer: This question evaluates algorithm design and query-complexity reasoning, focusing on efficient search strategies for identifying an interacting pair via a costly black-box oracle.

You are given `tests`, a list of distinct integer test IDs. Exactly two of them, `a` and `b`, form a conflicting pair. A black-box function `run(subset)` behaves as follows: - returns `"FAIL"` if and only if both `a` and `b` are present in `subset` - otherwise returns `"PASS"` Your task is to identify the two conflicting test IDs while using as few black-box calls as possible. A solution that checks all pairs is too slow for large `n`. For this coding version, the judge passes a second argument `conflict_pair` only so the hidden `run(subset)` behavior can be simulated locally. Write your logic as if you only had access to `run(subset)`, and return the two conflicting IDs in the same order they appear in `tests`.

Constraints

2 <= len(tests) <= 10^5
`tests` contains distinct integers
`conflict_pair` contains exactly two values from `tests`
`run(subset)` returns `FAIL` iff both hidden conflicting IDs are in `subset`
An O(n^2) search over all pairs is not acceptable

Examples

Input: ([1, 2, 3, 4, 5, 6], (5, 2))

Expected Output: [2, 5]

Explanation: Only subsets containing both 2 and 5 fail. The returned order follows their order in `tests`.

Input: ([10, 20], (20, 10))

Expected Output: [10, 20]

Explanation: This is the smallest valid input. With only two tests, they must be the conflicting pair.

Input: ([-3, -1, 0, 7, 9], (-3, 9))

Expected Output: [-3, 9]

Explanation: Negative values are valid IDs. The conflict occurs only when both -3 and 9 are included.

Input: ([4, 8, 15, 16, 23, 42, 50, 60], (42, 23))

Expected Output: [23, 42]

Explanation: Both conflicting tests lie in the same half at first, so repeated halving isolates them quickly.

Hints

Split the current candidate set into two halves. If one half fails by itself, then both conflicting tests are inside that half.
If both halves pass, then the conflicting pair is split across the halves. Use one half as an anchor and binary search the other half.

Quick Overview

This question evaluates algorithm design and query-complexity reasoning, focusing on efficient search strategies for identifying an interacting pair via a costly black-box oracle.