Optiver Implement-from-Scratch Coding interview questions

Both kernels are ten lines of shuffles. The round is decided by the lines around them: lanes past n that return early, a float sum that changes bits with the grid size or with atomics, and a three-kernel scan that moves twice the bytes it needs.

One atomicAdd per element passes every test and puts 131,072 updates on a single address when the router collapses. The answer counts the serialized updates, privatizes them per warp and per block, and then removes the atomics from the combine entirely with an index the sort already built.

Forty lines of Python, and graders run property tests against them. The answer gets the three invariants right first, then the one copy-on-write case most implementations get backwards.

The attention math is ten lines. The grade comes from where the new keys land, which query head reads which KV head, and the causal mask when a chunk of queries sits at the end of a longer cache.

Everyone can sort and cumsum. The grader feeds you tied logits, p = 1 on a 128K vocabulary and a temperature of zero, and checks whether your kept set depends on the order of the sort.

A scheduler is a loop over three queues and a budget. The answer gets the order of those loops right, shows what the budget costs in milliseconds of TPOT, and tests the invariants a grader will check.

The accept rule is one line. The residual distribution, the bonus token, rows that drafted fewer tokens and a test that can tell a lossless verifier from a subtly biased one are the rest of the grade.

A disconnect arrives after launch, then the request ID is reused. Implement deferred reclamation and prove that late or duplicate completions cannot emit stale output or free another request's pages.

Matching a prefix is a trie walk. The grade is in the edge split, which cached tokens a running request pins, and an eviction loop that turns parents into leaves without ever freeing a slot twice.

RoPE is a rotation per pair of dimensions. The bugs live in which dimensions pair up, which position each row of a ragged batch is at, what left padding does to position ids, and the precision of the angle at position 100,000.

Two nibbles per byte and a scale per 128 weights sounds like bookkeeping. The grader checks the sign extension, the nibble order, what happens when K is odd or not a multiple of the group, and whether your error test has a bound or just a vibe.

The tutorial kernel loads a whole row into one block and breaks the moment the row is a 128,256-entry vocabulary. The answer writes the looped version, keeps it free of NaNs when a whole tile is masked, and tests it the way a grader will.

Two loops and an index formula, and most attempts get the index wrong by one. The answer writes reduce-scatter and all-gather over a simulated ring, proves the result matches a direct sum when p does not divide the length, and turns the byte count into the reason small messages avoid the ring.

Beam search reshuffles which hypotheses survive every step, and a naive cache copies every survivor's history. The answer forks block tables instead, gets the release order right so the last sharer writes in place, and proves it against a beam search that never pages.

A request costs anything from ten tokens to a hundred thousand, and you only learn the real cost when it finishes. The answer reserves at admission, refunds at completion, fails fast on requests that can never fit, and tests the bound the bucket is supposed to guarantee.

Two prompts with the same 16 tokens in block 3 must not share block 3 unless blocks 0 to 2 match too. The answer chains the hashes, keeps freed blocks hittable until memory is needed, evicts tails before heads, and proves a colliding hash cannot hand a request the wrong KV.

The stop string arrives as three tokens, the euro sign arrives as two, and the client has already been sent half of both. The answer holds back exactly the text that could still become a stop, decodes bytes incrementally, and tests the stream against a reference that sees the whole output at once.