Google New Grad Onsite: Find Two Test Cases That Fail Only Together

Role: Software Engineer, New Grad
Result: Later updated as not a rejection
Report time: January 2026

Coding: identify an interacting failing pair

A black-box function run(subset) executes a chosen subset of test cases.

Exactly two test cases are incompatible: run fails when both are present in the submitted subset, and passes when only one or neither is present. Given the full list of test cases, identify the incompatible pair.

The candidate produced an O(n log n) approach during the interview.

Their divide-and-conquer explanation was:

1. Split the current set in half and run each half.
2. If one half fails, both tests are inside it; recurse into that half.
3. If both halves pass, the pair is split across the halves.
4. Fix one side and binary-search portions of the other side to locate one member, then locate the other.

The discussion later became ambiguous about whether complexity should count only oracle calls or the total number of test cases processed by all calls. The candidate noted that a linear-cost run changes the overall analysis.

Practice limitation

This is a complete interactive-oracle prompt, but FastPrep's standard algorithm runner accepts fixed batch parameters and does not expose an adaptive run(subset) callback. Publishing the hidden pair as ordinary input would change the task, so no practice link is supplied.

The candidate initially expected rejection but later edited the post to say it was not a rejection.