Algorithm · Google · Hard
Requirements You receive items t_1, ..., t_N. An oracle named runTest takes a Set[Item] and returns a Boolean: it yields true exactly when the supplied set includes no bad pair, and false when at least one bad pair is present. Report all bad pairs (t_i, t_j). Use as few oracle invocations as possible. Examples The second test passes because {1,2,3,4} does not contain both endpoints of the only bad pair, (2,5). Notes This is a classic adaptive group-testing problem, often…
Checking your access…