Perplexity Implement-from-Scratch Coding interview questions

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.

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.

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.

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.

At batch 1 a decode attention kernel gives each KV head one thread block and leaves most of the GPU idle. The answer splits the sequence, carries a log-sum-exp with every partial output, merges them exactly, and survives the split that has no keys at all.

A runnable allocator hides an exception-safety defect and a payload-aliasing defect. Reduce each failure to a short operation sequence, then test ownership and content against separate oracles.

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.

The tensor has the right shape and every token ID is valid, yet one request receives another request's continuation. Reproduce the routing error and repair the launch-to-completion contract.