Katkat
Back

Find a Hidden Number When Each Comparison Answer Arrives One Call Late

OpenAISoftware Engineer · Onsite
HardSoftware EngineerOnsiteSoftware Engineering Fundamentals

Last updated

Find a hidden integer from 1 to n using a comparison API whose answers arrive one call late: each call submits a new guess but returns the result for the previous one. Build a correct search first, then reduce the worst-case number of calls. It tests binary search under delayed feedback and worst-case analysis.

A hidden integer x lies in the range 1 to n. You can learn about it only through an API call check(g), which compares a guess g with x. The twist is that the API's answer is delayed by one call: each call to check(g) submits the guess g, but returns the comparison result for the guess submitted in the previous call. The very first call returns nothing (None). A result says whether that earlier guess was too low (-1), correct (0) or too high (1).

Write a function find_hidden(n, check) that returns x, using as few calls to check as possible in the worst case. Start with a correct version, then improve the worst-case number of calls, and explain how many calls your approach needs as a function of n.

The exact API contract was not reported; the one above is the working assumption for this exercise.

Clarifying Questions

  • Is the delay always exactly one call, or can answers arrive at unpredictable later times?
  • Is n known in advance?
  • Is the goal to minimize the worst-case number of calls, or the average?
  • Must the function end by having check confirm x with a result of 0, or is deducing x enough?
  • Is there a limit on the total number of calls?

Hints

Hint 1

Correct first: Before optimizing, consider the simplest way to run an ordinary binary search on top of an API that always answers one call late, and count its calls.

Hint 2

Make the waiting call useful: The call that fetches the previous answer must itself submit some guess; think about where to place that guess so it helps regardless of which answer arrives.

Follow-up questions

  • The delay is now `d` calls instead of one. How does your strategy generalize?
  • Several guesses may be submitted in one call and answered together one call later. How does that change the search?
  • Answers can now be wrong with a small probability. How would you still find `x` reliably?
  • The answers can arrive out of order, each tagged with its guess. What changes?