FastPrepSecret Number Search with One-Call-Delayed Feedback
Problems/Secret Number Search with One-Call-Delayed Feedback

Secret Number Search with One-Call-Delayed Feedback

OpenAI logoOpenAI● MediumFULLTIMEPHONE SCREEN
QuestionExamples

Problem statement

Source note: The report asks for binary search when each oracle call returns the comparison for the previous guess. This authored practice replays a valid response transcript under an explicit midpoint protocol, without exposing the secret as input. Bounds, response codes, first-call behavior and stopping rules are authored. The unseen second part is not reconstructed. Approximate source match: 90%.

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.

The problem statement continues
Pro

Examples

Example 1

upperBound = 10feedback = [2,1,1,-1,-1,1,1,0]return = 7

The 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.

02 · Example 2
FastPrep Pro
Reported in 1 OpenAI interview this week

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
$8.25/month

$99 billed yearly — or $19 month-to-month. Cancel anytime.

Free plan — 2 of 2 free unlocks used this week
All OpenAI interview questionsSee OpenAI hiring insights
CodePython 3
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
import heapq
from collections import defaultdict
 
class Solution:
def solve(self, values, queries):
# Build the adjacency structure
n = len(values)
graph = defaultdict(list)
for u, v in queries:
graph[u].append(v)
 
best = [float("inf")] * n
heap = [(0, 0)]
while heap:
cost, node = heapq.heappop(heap)
if cost > best[node]:
continue
Run and Submit unlock with Pro
FastPrep Pro
Reported in 1 OpenAI interview this week

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
$8.25/month

$99 billed yearly — or $19 month-to-month. Cancel anytime.

Free plan — 2 of 2 free unlocks used this week