Katkat
Back

Find conflicting pair using black-box run()

GoogleSoftware Engineer · Onsite
HardSoftware EngineerOnsiteCoding & Algorithms

Last updated

This problem tests your ability to optimize search operations within a hidden set of dependencies by minimizing calls to a costly black-box oracle.

Problem Statement

You are given a collection of n items, labeled 0 to n-1. There exists exactly one pair of items (i, j) that is "conflicting," where i < j. You do not know which pair is conflicting, but you have access to a black-box oracle function run(subset).

The run(subset) function takes a list of integers (a subset of the n items) and returns True if the conflicting pair is entirely contained within the subset, and False otherwise. Your goal is to identify the unique pair (i, j) using the minimum number of calls to run().

Function Signature

def find_conflicting_pair(n: int) -> Tuple[int, int]:

Constraints

  • 2 <= n <= 10^5
  • The oracle is deterministic.
  • run() is computationally expensive; aim for a query complexity of O(log^2 n) or better.

Example 1

Input: n = 4 (Conflicting pair: (1, 2))

  • run([0, 1, 2]) -> True (contains 1 and 2)
  • run([0, 1]) -> False
  • run([2, 3]) -> False

Edge Cases

  • n = 2: The only pair is (0, 1).
  • Large n: Ensure your search strategy does not default to O(n) linear scans.

Note

Think of this as a search problem where you need to isolate one element of the pair first, then the other.

Hints

Hint 1

Can you use binary search to determine if the conflicting pair exists within a specific range of indices [0, k]?

Hint 2

If you know the conflicting pair exists within a range [0, k], can you use a second binary search to find the first element `i` by checking if the pair exists within [0, m]?

Hint 3

Once you have identified the first element `i`, can you use another binary search to identify the second element `j` by checking if the pair `(i, x)` exists for various values of `x`?

Follow-up questions

  • What is the total query complexity of your solution in terms of big-O notation?
  • How would your approach change if the oracle returned the number of conflicting pairs present in the subset instead of a boolean?
  • If the oracle has a 5% chance of returning an incorrect result (noisy oracle), how would you modify your search strategy to ensure correctness?