How should I practice Budgeted API Inference with Out-of-Order Feedback?

Start by reading the full statement, solve the visible examples, then compare the pattern against related OpenAI onsite interview problems in FastPrep.

Is Budgeted API Inference with Out-of-Order Feedback associated with OpenAI?

FastPrep tags this as a OpenAI onsite interview coding practice problem when the problem catalog has that company and stage context.

Budgeted API Inference with Out-of-Order Feedback

OpenAI● HardFULLTIMEONSITE INTERVIEW

Problem statement

A fixed hidden state is one of n candidate IDs, from 0 through n - 1. You do not receive the hidden state. Instead, responseTable[q][s] gives the response code that query q would return if the hidden state were s.

Replay the supplied events to maintain the possible states and decide which query to call next. Initially, every state is possible, every query is available, and no calls have been used.

Choose a query

For a query, group the current candidates by their response codes in its row. Its score is the size of the largest group. A query is separating if this score is smaller than the number of current candidates.

A CALL chooses an available separating query with the smallest score, breaking ties by the smallest query ID. A pending query and a query that already received an accepted response are unavailable. Do not issue a call when the budget is exhausted, at most one candidate remains, or no available query is separating. This is a specified next-query policy; you are not asked to minimize the total number of calls over all possible future responses.

Process events in array order

Each event has three integers [op, a, b]:

[0, 0, 0] means CALL. If a query is chosen, consume one unit of budget, make it pending, and use this event's zero-based index as its request ID. A skipped call creates no request.
[1, requestId, code] means RESPONSE. If that request is still pending, keep only the current candidates s for which responseTable[q][s] == code, then close the request and mark its query as answered. Apply the response to the current candidates, even if other requests answered first.
[2, requestId, 0] means TIMEOUT. If that request is still pending, close it and make its query available again. A timeout does not change the candidates or refund the used call. A later CALL may choose that query again, using a new request ID and another budget unit.

Ignore a response or timeout whose referenced request does not exist yet, came from a skipped call, or is already closed. In particular, duplicate and late responses to a timed-out request cannot change the candidates or close a newer retry. Events are processed in the given order; their request IDs may arrive out of order.

After every event, append [issuedQuery, candidateCount, callsUsed] to the answer. issuedQuery is the query ID issued by that event, or -1 otherwise. Return these rows in event order.

All responses accepted while their request is pending are consistent with at least one fixed hidden state, so the candidate set never becomes empty. Payloads of ignored responses need not be consistent.

Streaming follow-up

A response above is a complete logical message. Explain how to extend the same state machine when a response arrives in fragments: correlate fragments with their request, buffer until a complete response is available, and commit it once. Discuss how timeout, retry, and out-of-order completion interact with that boundary. Transport parsing and concurrency are outside the judged function.

Function

replayInference(responseTable: int[][], budget: int, events: int[][]) → int[][]

Examples

Example 1

responseTable = [[0,0,1,1],[0,1,0,1]]budget = 3events = [[0,0,0],[0,0,0],[1,1,1],[1,0,0],[0,0,0]]return = [[0,4,1],[1,4,2],[-1,2,2],[-1,1,2],[-1,1,2]]

Both queries initially have largest group size 2, so query 0 is issued first. It is pending, so the next call issues query 1. Request 1 responds first and keeps candidates {1,3}. Request 0 then keeps only candidate 1. The final call is skipped.

Example 2

responseTable = [[0,1,2]]budget = 2events = [[0,0,0],[2,0,0],[0,0,0],[1,0,0],[1,2,2]]return = [[0,3,1],[-1,3,1],[0,3,2],[-1,3,2],[-1,1,2]]

Request 0 times out after consuming a call. The retry at event 2 issues query 0 with request ID 2. The late response for request 0 is ignored. The response to request 2 identifies candidate 2.

Constraints

1 <= responseTable.length <= 100.
Every row has the same length n, where 1 <= n <= 100.
0 <= responseTable[q][s] <= 100.
0 <= budget <= 500 and 0 <= events.length <= 500.
Each event has exactly three entries and one of the stated operation shapes. Response codes are between 0 and 100. Referenced request IDs are between 0 and events.length - 1.
All accepted responses are consistent with one fixed hidden state. Ignored responses are exempt from this condition.