Secret Number Search with One-Call-Delayed Feedback
Problem statement
A secret integer is between 1 and upperBound, inclusive. A guessing service has a one-call delay: a call submits a new guess but returns the comparison for the immediately preceding call's guess.
You receive the recorded feedback array from the deterministic binary-search protocol below. Reconstruct the search and return the secret integer. The secret and the submitted guesses are not provided as inputs.
Examples
Example 1
upperBound = 10feedback = [2,1,1,-1,-1,1,1,0]return = 7The submitted guesses are [5,5,8,8,6,6,7,7]. The third response is still about the second guess, 5, even though the newly submitted guess is 8. The last response confirms that the preceding guess, 7, is the secret.
Unlock this recently reported problem
FastPrep Pro gives you full access to interview problems reported within the last week.
- Full problem statement and constraints
- 1 more worked example, explained
- Guided hints and editorial
- Run your code on real test cases
$99 billed yearly — or $19 month-to-month. Cancel anytime.