Qualcomm Gen AI (Staff): The Coding Rounds, Solved

1. Quick anchor

Qualcomm's loop is famously fundamentals-heavy — the coding rounds lean on real data structures, OS/concurrency, and low-level reasoning far more than a pure-product company's loop does, and that stays true even for an applied Gen AI role. For a staff-level Gen AI req you should expect roughly four coding-adjacent rounds:

Round A is a gate you clear. Rounds B–D are where you're levelled. Most candidates over-prepare A and under-prepare B — the highest-return hour in your prep is B, because almost nobody can write a batching scheduler on a whiteboard and everyone can write a two-pointer.

Where this sits in the loop. In practice the first two slots on the calendar are usually the generic ones — a plain coding screen, then a classic distributed-systems design round — with the Gen-AI-specific depth coming after:

So Round A below is deliberately thin — it's five DSA problems given a Gen-AI framing, useful as warm-up and as a bridge into Round B. If you're preparing the actual round-one screen, go to Round 1 for the Qualcomm pattern reweighting, the ranked 45-problem hit list, the bit-manipulation set, and the C/OS/Linux/Python fundamentals — none of which live on this page.

How the solutions here are written

Everything below is pseudocode — tagged python so it syntax-highlights, but written to be spoken at a whiteboard, not pasted into an IDE. No imports, no library calls doing the hard part. That's deliberate: in an interview the grader is watching your invariants and your edge cases, and real code hides both behind idioms. When you practice, say the invariant out loud before you write the loop.

Each problem follows the same shape: prompt → clarify → approach → pseudocode → complexity → follow-ups → what's being scored. Work them in that order; the clarify step is worth as many points as the code.

Pair with: the system-design primer The full DSA curriculum

2. Round A — the DSA filter

Five problems that are ordinary DSA wearing Gen-AI clothes. Solve them as DSA; mention the framing in one sentence at the end. Interviewers notice when the framing is genuine and cringe when it's decoration.

These five are a bridge, not a curriculum. The real round-one prep — pattern reweighting, the ranked 45, bits, and the fundamentals rapid-fire — is on Round 1: The Coding Screen, and the full 80-problem plan is in the DSA track.

A1 · Longest cached prefix over KV blocks

Requests arrive as token-ID lists. The engine caches KV in fixed blocks of 16 tokens. Given the cache and a new request, return the number of leading tokens whose KV can be reused.

Clarify. Block size fixed? Yes, 16. Is the cache a flat map or a tree? Tree — a block's contents depend on every token before it. Are token IDs enough to identify a block? No, and this is the whole problem.

Approach. The key insight to say before writing anything: the KV for block $i$ is a function of blocks $0..i$, not of block $i$ alone. So the cache key must be a chained hash — h_i = hash(h_{i-1}, tokens_i) — exactly like a Merkle chain. Then the cache is a trie keyed on chained hashes, and "longest cached prefix" is a walk down that trie.

BLOCK = 16
 
class Node:
    children  = {}      # chained_hash -> Node
    block_id  = None    # physical KV block
    refcount  = 0       # live sequences using it
    last_used = 0
 
def longest_cached_prefix(root, tokens):
    node, h, matched, t = root, SEED, [], 0
    while t + BLOCK <= len(tokens):              # only FULL blocks are cacheable
        h = chain_hash(h, tokens[t : t + BLOCK]) # parent hash folded in
        child = node.children.get(h)
        if child is None:
            break
        matched.append(child.block_id)
        child.last_used = now()
        node, t = child, t + BLOCK
    return matched, t          # t = tokens whose prefill we can skip
 
def insert(root, tokens, block_ids):
    node, h = root, SEED
    for i, blk in enumerate(block_ids):
        h = chain_hash(h, tokens[i*BLOCK : (i+1)*BLOCK])
        if h not in node.children:
            node.children[h] = Node(block_id=blk, refcount=0)
        node = node.children[h]

Complexity. $O(T/B)$ hash-and-lookup per request, $T$ = prompt length. Memory $O(\text{cached blocks})$.

Follow-ups you should have answers for.

• Why not hash each block independently? Because two different prefixes ending in the same 16 tokens would collide onto the same KV, and the KV would be wrong. Silent, catastrophic, and the classic bug in a naive implementation.
• Why only full blocks? A partial trailing block is still being written; its KV isn't final. Sharing it would mean sharing mutable state.
• Block size tradeoff? Small blocks → finer-grained hits, more bookkeeping and more fragmentation. Large blocks → cheaper metadata, but a 1-token divergence throws away the whole block.
• Hash collisions? A 64-bit chained hash has real collision probability at scale, and a collision returns someone else's KV. Either verify token IDs on match, or use a wide enough hash that you can argue the birthday bound.

Scored on: noticing the chaining requirement unprompted. That single observation is the difference between "wrote a trie" and "understands prefix caching."

A2 · LRU evictor with pinning and a tree constraint

Evict a KV block to make room. Blocks are LRU-ordered, some are pinned by running sequences, and blocks form the prefix tree from A1.

Clarify. Can I evict a pinned block? No — a running sequence is reading it. Can I evict a block whose children are cached? Not without orphaning them.

Approach. Standard $O(1)$ LRU (hash map + doubly linked list), plus two predicates: refcount == 0 and children.empty(). The second is the one candidates miss — freeing an interior node strands its descendants, whose chained hashes now point through a hole.

class LRU:
    map  = {}          # key -> DListNode
    head = None        # most recently used
    tail = None        # least recently used
 
    def touch(self, key):                 # O(1)
        n = self.map[key]; self.unlink(n); self.push_front(n)
 
    def evict_one(self):
        n = self.tail
        while n is not None:
            if n.refcount == 0 and len(n.children) == 0:
                self.unlink(n)
                n.parent.children.pop(n.hash)   # keep the trie consistent
                free_block(n.block_id)
                return n.block_id
            n = n.prev                    # skip pinned / interior nodes
        return NONE                       # nothing evictable -> caller must preempt
 
    def pin(self, key):   self.map[key].refcount += 1
    def unpin(self, key):
        n = self.map[key]; n.refcount -= 1
        if n.refcount == 0: self.touch(key)     # only now does it re-enter LRU age

Complexity. $O(1)$ amortized for touch/pin/unpin. evict_one is $O(1)$ in the common case and $O(k)$ when it has to skip $k$ pinned blocks — worth stating that a pathological workload makes eviction linear, and that the fix is a separate "evictable" list that blocks enter on refcount → 0.

Follow-ups. What if nothing is evictable? Then you're out of KV and must preempt a running sequence — that's the hand-off into B3. What order do you free within a sequence? Leaves first, i.e. newest blocks first, so the shared prefix survives for other sequences.

Scored on: the leaf-first constraint, and the refcount → 0 re-entry into LRU age.

A3 · Fuse BM25 and vector results

Two ranked lists over the same corpus. Return the top 20 fused.

Clarify. Are the scores comparable? No — BM25 is unbounded and corpus-dependent, cosine is in [-1,1]. Do I have full scores or just ranks? Assume ranks are reliable, scores are not.

Approach. Reciprocal-rank fusion, because rank is scale-free and needs no calibration:

Then a bounded min-heap for the top-$n$ instead of sorting everything.

def rrf_fuse(lists, weights, n, K=60):
    score = defaultdict(0.0)
    for l, ranked in enumerate(lists):
        for rank, doc in enumerate(ranked, start=1):
            score[doc] += weights[l] / (K + rank)
 
    heap = MinHeap(capacity=n)              # ordered by score
    for doc, s in score.items():
        if heap.size < n:        heap.push((s, doc))
        elif s > heap.peek()[0]: heap.pop(); heap.push((s, doc))
    return heap.drain_descending()

Complexity. $O(N)$ to accumulate, $O(N \log n)$ to select. Sorting all of score is $O(N \log N)$ — avoidable, and they're watching.

Follow-ups. Why $K{=}60$? It damps the dominance of rank 1: without it, being first in one list beats being second in both. $K$ is the knob for "how much do I trust a single retriever's top hit." When is RRF wrong? When the retrievers have genuinely different quality — then weight them (w_l), calibrated on a labeled set. What if a doc appears in only one list? It still scores; that's a feature — a doc found only by BM25 (an exact ID, a rare token) is often the right answer.

A4 · How many accelerators does this reservation calendar need?

Given (start, end) reservations, return the minimum number of devices, and the peak concurrency.

Approach. Two classic patterns, and knowing they're the same question asked two ways is the point. Minimum devices = peak concurrency (interval partitioning).

def min_devices(jobs):                  # greedy + min-heap of end times
    jobs.sort(key=start)
    ends = MinHeap()
    for (s, e) in jobs:
        if ends.size > 0 and ends.peek() <= s:
            ends.pop()                  # a device freed up; reuse it
        ends.push(e)
    return ends.size
 
def peak_concurrency(jobs):             # sweep line
    events = []
    for (s, e) in jobs:
        events.append((s, +1)); events.append((e, -1))
    events.sort(key=lambda ev: (ev[0], ev[1]))   # -1 BEFORE +1 at equal time
    cur = best = 0
    for (_, delta) in events:
        cur += delta
        best = max(best, cur)
    return best

The tie is the interview. At t, one job ends and another starts. If intervals are half-open [s, e) they share a device, so the -1 must sort first — which the (time, delta) tuple gives you for free since -1 < +1. If they're closed, flip it. Ask which convention applies before you write it; that question alone is worth more than the code.

Complexity. $O(N \log N)$ both ways.

Follow-ups. Streaming version (reservations arrive online)? You lose the global sort — use a running counter plus a min-heap and accept that "minimum" becomes "minimum so far." Which do you actually deploy? The sweep-line, because you also want the shape of the peak for autoscaling, not just its height.

A5 · Bitmap block allocator

KV blocks are tracked in a bitmap (1 = free). Allocate a contiguous run of n.

Qualcomm asks bit manipulation. This is that question with a purpose attached.

W = 64                                   # bits per word
 
def find_free_run(bm, n):
    i, N = 0, len(bm) * W
    run = 0
    while i < N:
        w = bm[i // W]
        if w == 0:                       # entire word allocated -> skip it whole
            run = 0
            i = (i // W + 1) * W
            continue
        if (w >> (i % W)) & 1:           # this bit is free
            run += 1
            if run == n:
                return i - n + 1
        else:
            run = 0
        i += 1
    return -1
 
def set_range(bm, start, length, value):
    while length > 0:
        wi, off = start // W, start % W
        k = min(length, W - off)
        mask = (ONES >> (W - k)) << off   # NOT ((1<<k)-1)<<off — k==64 overflows
        bm[wi] = (bm[wi] & ~mask) if value == USED else (bm[wi] | mask)
        start  += k
        length -= k

The bit tricks to name out loud. w & -w isolates the lowest set bit. ctz(w) is its index — use it to jump straight to the next free bit instead of stepping. w & (w-1) clears it. popcount(w) gives free-block accounting in one instruction. And the landmine: (1 << k) - 1 overflows when k == W — the shift is undefined in C and wraps in most languages. Writing ONES >> (W - k) instead is exactly the kind of detail a Qualcomm interviewer is looking for.

Complexity. $O(N/W)$ with word skipping in the sparse case, $O(N)$ worst case. Note the follow-up before they ask: contiguous allocation is why paged KV exists. Paged attention removed this problem by allowing non-contiguous blocks — so the honest answer is "in production I wouldn't need a contiguous run at all, and that's the whole design win."

3. Round B — Gen-AI systems coding

This is the round that decides your level. Every problem here is a real component of a serving stack.

B1 · Sampling: temperature, top-k, top-p

Given raw logits over a 128K vocabulary, sample the next token with temperature, top-k, top-p, and a repetition penalty.

Clarify. Ask two questions and you've already outscored most candidates: "What order do you want them applied?" and "Is temperature=0 supposed to mean greedy?" (It does, and it's a special case — dividing by zero is the bug everybody ships once.)

Approach. Order matters and it is not arbitrary:

penalties → temperature → top-k → top-p → renormalize → sample

Penalties act on raw logits (before temperature rescales the gaps). Top-k prunes to a fixed candidate set; top-p then prunes that set by cumulative mass. Doing top-p first and top-k second would make k meaningless.

def sample_next(logits, temp, k, p, penalty, history):
    # 1. repetition penalty, on RAW logits
    for tok in set(history):
        logits[tok] = logits[tok] / penalty if logits[tok] > 0 else logits[tok] * penalty
 
    # 2. greedy short-circuit — never divide by zero
    if temp == 0:
        return argmax(logits)
 
    # 3. temperature
    for t in range(V):
        logits[t] /= temp
 
    # 4. top-k via QUICKSELECT: O(V), not O(V log V)
    if k > 0 and k < V:
        kth = quickselect_desc(logits, k)     # k-th largest logit
        for t in range(V):
            if logits[t] < kth: logits[t] = NEG_INF
 
    # 5. numerically stable softmax over survivors
    m = max(logits)
    probs, Z = [0.0] * V, 0.0
    for t in range(V):
        if logits[t] > NEG_INF:
            probs[t] = exp(logits[t] - m)     # subtract max or exp() overflows
            Z += probs[t]
    for t in range(V): probs[t] /= Z
 
    # 6. top-p (nucleus) over the k survivors only
    keep = []
    if p < 1.0:
        order = sort_desc_by_prob(surviving_tokens)   # <= k items, not V
        cum = 0.0
        for t in order:
            keep.append(t); cum += probs[t]
            if cum >= p: break                # INCLUSIVE -> always >= 1 token
    else:
        keep = surviving_tokens
 
    # 7. renormalize and sample
    Z2 = sum(probs[t] for t in keep)
    r, acc = uniform(0, 1) * Z2, 0.0
    for t in keep:
        acc += probs[t]
        if acc >= r: return t
    return keep[-1]                           # float-rounding guard

Complexity. $O(V)$ for the penalty, temperature, quickselect, and softmax passes; $O(k \log k)$ for the nucleus sort. The trap is sorting the full 128K vocabulary — that's $O(V \log V)$ per token, per sequence, per step, and at batch 64 it will genuinely show up in your profile. Quickselect first, sort the survivors.

Follow-ups.

• Why is the top-p cut inclusive? Because with p=0.1 and a distribution whose top token has mass 0.4, an exclusive cut yields the empty set. You must always keep at least one token.
• Batched? Every step above is per-row; the only cross-row work is that you can't early-exit a batch on the shortest nucleus. Real kernels do this on-device — mention it, don't write it.
• Min-p? A newer alternative: keep tokens with prob >= min_p * max_prob. It adapts to distribution sharpness where top-p doesn't, and it's a one-line change here.
• Determinism? Same seed + same batch composition, or it isn't reproducible — because floating-point reduction order changes with batch shape. Say this; it's a real production surprise.

Scored on: the ordering, quickselect, the stable softmax, and the temp == 0 guard. Four details, four signals.

B2 · Per-tenant rate limiter for an LLM API

Limit each tenant to RPM and TPM. Output tokens are unknown at admission time.

Clarify. "Requests per minute or tokens per minute?" — both, and that's the interesting part. Then: distributed or single node? (Distributed.) Hard limit or burst-tolerant? (Burst-tolerant → token bucket, not fixed window.)

Approach. Token bucket for both dimensions. The Gen-AI-specific twist, and the thing that separates this from the textbook problem: you don't know the cost of the request until it's finished. So you reserve pessimistically at admission and settle at completion.

# Bucket state per (tenant, dimension): {tokens, last_refill}. All mutations atomic.
 
def admit(tenant, req, now):
    est = req.prompt_tokens + (req.max_tokens or DEFAULT_MAX)   # pessimistic reserve
    # ---- atomic section (Redis Lua / CAS) ----
    rpm = refill(load(tenant, "rpm"), now)
    tpm = refill(load(tenant, "tpm"), now)
    if rpm.tokens < 1 or tpm.tokens < est:
        wait = max((1 - rpm.tokens) / rpm.rate,
                   (est - tpm.tokens) / tpm.rate)
        store(rpm); store(tpm)
        return REJECT(429, retry_after=wait)
    rpm.tokens -= 1
    tpm.tokens -= est
    store(rpm); store(tpm)
    # ---- end atomic ----
    return ADMIT(reservation=est)
 
def settle(tenant, reservation, actual, now):
    # atomic: refund what we over-reserved. NEVER let tokens exceed capacity.
    tpm = refill(load(tenant, "tpm"), now)
    tpm.tokens = min(tpm.capacity, tpm.tokens + max(0, reservation - actual))
    store(tpm)
 
def refill(b, now):
    b.tokens = min(b.capacity, b.tokens + (now - b.last_refill) * b.rate)
    b.last_refill = now
    return b

Complexity. $O(1)$, one round trip per admission.

Follow-ups — this is where the round is won.

• Why not a fixed window? Boundary bursts: a tenant sends its full quota at 11:59:59 and again at 12:00:00, i.e. 2× the limit in one second. Sliding-window log fixes it but stores every timestamp. Token bucket gets burst tolerance at $O(1)$ state.
• Why must it be atomic? Read-modify-write from $N$ gateway replicas races, and every racer sees enough budget. Push the whole decision into one atomic script (Redis Lua) or one CAS loop.
• Whose clock? The store's, not the caller's. Client or replica clock skew silently grants or denies budget.
• Redis on the hot path is a round trip per request. Shard the bucket: give each of $N$ replicas rate/N locally, rebalance every few seconds. You trade exactness for latency — say the tradeoff explicitly and name the error bound.
• What if max_tokens is unset? Then you must reserve a default ceiling, or a single unbounded request can blow the quota. This is a real API-design coupling: the rate limiter is why max_tokens should have a server-side default.
• Fairness beyond quotas? Quotas cap a tenant; they don't decide who goes next when everyone's under quota. That needs a scheduler selector — deficit round-robin for fair shares, priority within a share. Name the split between the limiter (admission) and the selector (ordering); it's exactly how production systems structure it.

B3 · The continuous-batching scheduler

Write the scheduler loop for an LLM engine. Requests arrive continuously; KV memory is finite.

This is the single highest-value problem in this document. Almost nobody can write it; it is entirely writable once you've seen it once.

Clarify. Is prefill chunked or atomic? (Chunked.) Fair across tenants or FIFO? (Fair.) What happens when KV runs out — reject or preempt? (Preempt.)

Approach. One loop, four phases: retire → admit → guard → step. The invariant to state before writing: every scheduled step must fit in the KV budget and the token budget, and no admitted sequence may be starved indefinitely.

MAX_BATCH_TOKENS = 8192          # prefill chunk tokens + decode tokens per step
 
def scheduler_loop():
    running, waiting = [], FairQueue()      # FairQueue = deficit round-robin by tenant
 
    while True:
        # ---------- 1. retire finished ----------
        for r in running.finished():
            kv.release(r.blocks)            # blocks with refcount 0 fall into prefix LRU
            running.remove(r); emit_done(r)
 
        # ---------- 2. admit, budgeted ----------
        budget = MAX_BATCH_TOKENS - len(running)      # each decode costs exactly 1 token
        prefills = []
        while budget > 0 and not waiting.empty():
            r = waiting.peek()                        # fair pick, NOT FIFO
            if r.cached_blocks is None:
                r.cached_blocks, r.skipped = prefix_cache.match(r.tokens)   # A1
            need = kv.blocks_for(len(r.tokens) - r.skipped)
            if need > kv.free():
                break                                  # head-of-line: stop admitting
            chunk = min(r.remaining_prompt(), budget, MAX_PREFILL_CHUNK)
            prefills.append((r, chunk))
            budget -= chunk
            r.advance_prompt(chunk)
            if r.prompt_done():
                waiting.pop(); running.append(r)
 
        # ---------- 3. guard KV for this step ----------
        while kv.free_blocks() < projected_growth(running):
            victim = running[-1]                       # NEWEST first: least sunk cost
            if victim.prompt_len < RECOMPUTE_THRESHOLD:
                kv.release(victim.blocks); victim.reset_to_prompt()   # recompute later
            else:
                swap_out(victim.blocks)                 # copy KV to host DRAM
            running.remove(victim); waiting.requeue_front(victim)
 
        # ---------- 4. one fused step ----------
        outputs = engine.step(prefill=prefills, decode=running)
        for r, tok in outputs:
            r.append(tok)
            if tok == EOS or r.hit_stop_sequence() or r.len >= r.max_tokens:
                r.mark_finished()
            else:
                stream_to_client(r, tok)

Why each decision is the way it is — say all five:

1. Decode costs 1 token, prefill costs its chunk length. That single accounting rule is what lets one budget govern both and is the essence of chunked prefill.
2. Cap the prefill chunk. Without it, one 200K-token prompt consumes the entire step and every decoder stalls — the noisy-neighbor bug, in code.
3. Preempt the newest, not the oldest. The newest has the least sunk cost, and evicting the oldest creates a starvation cascade where the requests nearest completion keep dying.
4. Recompute vs swap. Recompute is cheap for short prompts (you re-run prefill); swap wins for long ones (transfer beats FLOPs). The crossover is measurable — state that you'd measure it rather than guessing.
5. Fair pick, not FIFO. FIFO is trivially gamed by a tenant that submits 10K requests. Deficit round-robin bounds each tenant's share regardless of submission volume.

Complexity. $O(\text{running} + \text{admitted})$ per step. The loop runs every ~20–100 ms, so it must be cheap; anything $O(V)$ or $O(\text{cache size})$ in here is a bug.

Follow-ups. Head-of-line blocking in step 2 — one request needing 400 blocks blocks smaller ones behind it. Fix: skip-ahead with an anti-starvation counter (after $M$ skips, reserve for it). Priority classes? Separate FairQueues with a weighted selector, and let batch jobs be preemptible by definition. How do you know the batch is right-sized? Watch TPOT p95 against the roofline knee — see the system-design primer §4.4.

B4 · Paged KV allocator with copy-on-write

Allocate KV in fixed blocks. Support forking a sequence (parallel sampling, beam search, shared system prompts) without copying its KV.

Approach. Two structures: a physical block pool, and a per-sequence block table mapping logical block index → physical block. Forking copies the table, not the blocks, and bumps refcounts. Copy happens lazily, on write.

class KVAllocator:
    free_list = [...]                 # physical block ids
    refcount  = {}                    # block id -> int
 
    def alloc(self):
        if not self.free_list:
            b = prefix_lru.evict_one()          # A2
            if b is NONE: raise OutOfKV         # caller preempts (B3 step 3)
            self.free_list.append(b)
        b = self.free_list.pop()
        self.refcount[b] = 1
        return b
 
    def fork(self, seq):
        child = Sequence(block_table=list(seq.block_table))   # shallow copy
        for b in child.block_table:
            self.refcount[b] += 1
        return child
 
    def append_token(self, seq, tok):
        i = seq.length // BLOCK
        if i >= len(seq.block_table):                 # need a new block
            seq.block_table.append(self.alloc())
        else:
            b = seq.block_table[i]
            if self.refcount[b] > 1:                  # ---- copy-on-write ----
                nb = self.alloc()
                copy_block(b, nb)
                self.refcount[b] -= 1
                seq.block_table[i] = nb
        write_kv(seq.block_table[i], seq.length % BLOCK, tok)
        seq.length += 1
 
    def release(self, seq):
        for b in seq.block_table:
            self.refcount[b] -= 1
            if self.refcount[b] == 0:
                prefix_lru.offer(b)      # don't free — keep as a cache candidate

The non-obvious observation, and the reason to reach for this design: only the last, partially-filled block is ever written after a fork. Every earlier block is complete and immutable. So a fork of a 4,000-token sequence copies at most one 16-token block — 0.4% of the KV — and shares the rest. That's how n=8 parallel samples cost ~1× the memory of one, and it's the sentence that lands this problem.

Complexity. $O(1)$ alloc/append amortized; fork is $O(\text{blocks})$ in refcount bumps but zero data movement.

Follow-ups. Internal fragmentation? Bounded by BLOCK - 1 tokens per sequence — with 16-token blocks and 500-token completions that's under 3%, versus the 60–80% waste of contiguous pre-allocation. Why release into an LRU instead of freeing? Because a refcount-0 block is still a valid cached prefix someone may want back; freeing it throws away work. That link between the allocator and the prefix cache is the design's real payoff.

B5 · Streaming with stop sequences and UTF-8 boundaries

Stream tokens to the client over SSE. Support stop sequences. Two hazards: a stop string can span multiple tokens, and a UTF-8 character can span multiple tokens.

Clarify. Should the stop string appear in the output? (No — truncate before it.) Multiple stop sequences? (Yes.) Must output be byte-exact? (Yes — you cannot emit a partial multi-byte character or the client renders a replacement glyph.)

Approach. The governing rule: never emit text you might have to retract. So hold back (a) any suffix that could still grow into a stop sequence, and (b) any trailing incomplete UTF-8 sequence.

STOPS = ["</s>", "\nUser:", "```"]
 
def stream(engine, seq, send):
    buf = ""
    for tok in engine.tokens(seq):
        buf += detokenize(tok)
 
        # 1. a complete stop sequence -> truncate, emit, finish
        cut = earliest_index_of_any(buf, STOPS)
        if cut >= 0:
            send(safe_utf8_prefix(buf[:cut]))
            return finish(reason="stop")
 
        # 2. hold back the longest suffix that is a PROPER PREFIX of some stop
        hold = 0
        for s in STOPS:
            for L in range(min(len(s) - 1, len(buf)), 0, -1):
                if buf.endswith(s[:L]):
                    hold = max(hold, L)
                    break
 
        # 3. hold back a dangling multi-byte character
        emit = safe_utf8_prefix(buf[: len(buf) - hold])
 
        if emit:
            send(emit)
        buf = buf[len(emit):]
 
    send(safe_utf8_prefix(buf))          # flush; a dangling partial is dropped
    finish(reason="length" if seq.len >= seq.max_tokens else "eos")
 
def safe_utf8_prefix(s):
    # walk back from the end past continuation bytes (0b10xxxxxx) to the last
    # complete character boundary
    i = len(s)
    while i > 0 and is_continuation_byte(s[i-1]):
        i -= 1
    if i > 0 and not is_complete_at(s, i-1):     # lead byte announces more bytes
        i -= 1
    return s[:i]

Complexity. Step 2 is $O(\sum |s_i|)$ per token with the naive scan — fine for a handful of short stop strings. If stop sequences are many or long, build an Aho-Corasick automaton once per request and stream through it in $O(1)$ amortized per byte. Say that; don't build it.

Follow-ups — the operational half, which is where staff shows up.

• Client disconnects mid-stream. You must propagate cancellation to the engine and free the KV. Otherwise you generate tokens into a dead socket and pay for every one. This is the most common expensive bug in a serving stack.
• SSE keepalives. If TTFT is 3 seconds, proxies may close an idle connection. Send a comment heartbeat (: ping\n\n) while waiting for the first token.
• Backpressure. A slow client's socket buffer fills. Do not block the engine's step loop on a socket write — buffer per-connection with a bound, and drop the connection when it's exceeded. One slow reader must not stall the batch.
• Why not just detokenize per token? Because tokenizers are not byte-aligned; detokenize(tok) can return an incomplete character on its own. Incremental detokenization must carry state.

B6 · Semantic cache lookup

Cache LLM responses by meaning, not by exact string.

def semantic_lookup(query, ctx, tau=0.93):
    e = embed(query)
    key_scope = (ctx.tenant, ctx.model_version,
                 ctx.prompt_template_hash, ctx.tool_schema_hash)
 
    # tenant + version go in the ANN FILTER, never in a post-filter:
    # post-filtering breaks top-k semantics AND leaks timing across tenants
    hits = ann.search(e, k=5, filter=key_scope)
 
    for h in hits:                          # descending similarity
        if cosine(e, h.vec) < tau: break    # sorted, so first miss ends the scan
        if h.expires_at <= now():  continue
        if not authorized(ctx.user, h.acl): continue
        metrics.hit(tier="semantic")
        return h.response
    metrics.miss()
    return MISS
 
def semantic_store(query, response, ctx, ttl):
    if ctx.had_tool_calls or ctx.personalized or ctx.time_sensitive:
        return                              # never cache these
    ann.upsert(embed(query), response, filter=key_scope(ctx),
               acl=ctx.acl, expires_at=now() + ttl)

The sentence that matters: this is the only cache in the stack that can return a wrong answer. An exact cache and a prefix cache are always correct by construction; a semantic cache is a similarity bet.

Follow-ups.

• How do you pick $\tau$? It's an eval problem with a number, not a vibe. Build a labeled set of query pairs (equivalent / not equivalent), sweep $\tau$, and choose the point where false-hit rate ≤ 1%. Re-run it whenever the embedding model changes.
• The classic failure? Negation. "Is X safe?" and "Is X not safe?" embed close and mean opposites. Also numbers and dates: "revenue in 2024" vs "2025."
• Invalidation? You don't invalidate — you version. Model version, prompt template hash, and tool schema hash are all in the key, so shipping a prompt change simply misses the old entries and they age out.
• Multi-turn? Embed a compacted representation of the conversation, not just the last message, or you'll serve a cached answer to "what about the second one?"
• When would you not ship it? When the workload has low repetition — you'd pay an embedding call per request for a 2% hit rate. Measure repetition first.

B7 · Speculative decoding: the accept/reject loop

A small draft model proposes $\gamma$ tokens; the large target model verifies them in one forward pass. Write the verification.

Approach. The target scores all $\gamma$ draft positions plus one in a single pass (that's the whole trick — one target forward for up to $\gamma+1$ tokens). Then modified rejection sampling accepts a prefix.

def speculative_step(target, draft, ctx, gamma):
    # 1. draft proposes gamma tokens autoregressively (cheap: small model)
    proposals, q = [], []
    c = ctx
    for _ in range(gamma):
        qi = draft.next_dist(c)
        x  = sample(qi)
        proposals.append(x); q.append(qi); c = c + [x]
 
    # 2. ONE target forward pass scores all gamma+1 positions
    p = target.dists(ctx, proposals)        # p[0..gamma]
 
    # 3. modified rejection sampling
    out = []
    for i in range(gamma):
        x = proposals[i]
        r = uniform(0, 1)
        if r < min(1.0, p[i][x] / q[i][x]):
            out.append(x)                   # accept
        else:
            resid = normalize(elementwise_max(0, p[i] - q[i]))
            out.append(sample(resid))       # reject: resample from the residual
            return out                      # and stop — later drafts are invalid
    out.append(sample(p[gamma]))            # all accepted -> a FREE bonus token
    return out

Why it's lossless — say this, it's the whole point. For any token $x$: $P(\text{propose } x) \cdot P(\text{accept}) + P(\text{reject}) \cdot P(\text{resample } x)$ telescopes to exactly $p(x)$. The max(0, p − q) residual is precisely the mass the acceptance test under-delivers, so the composed distribution equals the target's. Speculative decoding is not an approximation. Candidates who say "it trades a little accuracy for speed" have just told you they haven't read the paper.

Expected speedup. With per-token acceptance rate $\alpha$, expected tokens per target pass is $\frac{1 - \alpha^{\gamma+1}}{1 - \alpha}$. At $\alpha{=}0.8, \gamma{=}4$: ~3.4 tokens per target forward. Qualcomm's own Cloud AI results put speculative decoding alone at ~1.5–2×, and ~4× when stacked with MXFP6 weight compression — a good number to have ready, since it shows you read the platform's material.

When it hurts — the follow-up they're really asking:

• Low $\alpha$ (draft mismatched to domain): you pay the draft cost and reject most of it. Net loss.
• Large batch: the target is already compute-saturated, so verifying $\gamma+1$ positions is no longer "free." Speculative decoding buys latency in the memory-bound, small-batch regime; it can cost throughput in the compute-bound one. Best answer: make $\gamma$ adaptive on batch size and measured $\alpha$ — shrink it as load rises.
• Memory: a second model resident, competing with KV for capacity — which matters less on a 768 GB part than on a 192 GB one.

4. Round C — concurrency and OS

Qualcomm's coding rounds lean on threading fundamentals harder than most product companies. These three cover the ground, and each has a direct analogue in a serving stack.

C1 · N threads emitting in strict round-robin

Threads 0..N-1 must produce output in the order 0,1,2,...,N-1,0,1,.... Implement it. (The two-thread odd/even version is the classic Qualcomm warm-up; do the general case.)

Approach. A shared turn counter under a mutex, and — the detail the question exists to test — the right wakeup primitive.

turn = 0
m    = Mutex()
cv   = [Cond() for _ in range(N)]        # ONE CONDVAR PER THREAD
 
def worker(i):
    while True:
        lock(m)
        while turn % N != i and not done:  # WHILE, not IF: spurious wakeups are real
            wait(cv[i], m)
        if done:
            unlock(m); return
        emit(i)
        turn += 1
        signal(cv[(i + 1) % N])           # wake exactly the one thread that can run
        unlock(m)
 
def shutdown():
    lock(m); done = True
    for c in cv: signal(c)                # every thread must be able to observe it
    unlock(m)

Why signal on a single shared condvar is a bug. With one condvar for all $N$ threads, signal() wakes an arbitrary waiter. If it wakes thread 3 when it's thread 1's turn, thread 3 re-checks its predicate, goes back to sleep — and nobody else was woken. Lost wakeup, deadlock. Two correct fixes: broadcast() on the shared condvar (correct, but $O(N)$ wakeups per turn — a thundering herd for $N{=}64$), or one condvar per thread with targeted signal() (correct and $O(1)$). Say both, choose the second, and explain the cost you avoided. For $N{=}2$ the shared-condvar signal happens to work — which is exactly why the odd/even version teaches the wrong lesson and why interviewers generalize it.

Follow-ups. Without condition variables? Atomic turn counter + spin, or $N$ binary semaphores where thread $i$ waits on sem[i] and posts sem[i+1] — cleaner, no mutex at all. Fairness/starvation? Strict round-robin is starvation-free by construction. Where does this show up for real? Ordered emission from parallel workers — the sequence numbering that keeps a streaming response in order when generation is fanned out.

C2 · Micro-batch collector: flush at max size or max wait

Collect incoming requests into batches. Flush when the batch reaches MAX_BATCH or when the oldest item has waited MAX_WAIT, whichever comes first.

q          = Deque()
m, cv      = Mutex(), Cond()
MAX_BATCH  = 32
MAX_WAIT   = 10ms
 
def enqueue(item):
    lock(m)
    q.push_back((item, arrival=now()))
    if len(q) == 1 or len(q) >= MAX_BATCH:
        signal(cv)                       # first item starts the clock; full flushes now
    unlock(m)
 
def collector():
    while True:
        lock(m)
        while q.empty():
            wait(cv, m)
        deadline = q.front().arrival + MAX_WAIT     # OLDEST item, not newest
        while len(q) < MAX_BATCH and now() < deadline:
            wait_until(cv, m, deadline)             # loop: spurious wakeup OR timeout
        batch = q.pop_front_upto(MAX_BATCH)
        unlock(m)
        dispatch(batch)                             # never hold the lock across I/O

Three details, three signals.

1. The deadline comes from the oldest item. If you compute it from "now" on each wakeup, a steady arrival stream defers the flush forever and your p99 is unbounded. Anchoring on the oldest item bounds queueing delay by MAX_WAIT for every item, always.
2. while, not if, around both waits. wait_until returns on spurious wakeup, on signal, and on timeout — you cannot tell which without re-checking the predicate.
3. Release the lock before dispatch. Holding a mutex across a network call serializes your producers behind your consumer.

Follow-ups. Adaptive MAX_WAIT? Yes — shrink it as load rises (you'll hit MAX_BATCH anyway) and grow it when idle. How does this relate to continuous batching? It's the degenerate ancestor: continuous batching flushes every step and admits mid-flight, so MAX_WAIT collapses to one step time and the queueing-vs-throughput tradeoff mostly disappears. Saying that connection out loud is a strong move — it shows you know why the industry moved on from static batching.

C3 · Bounded in-flight work, load shedding, cancellation

Your gateway fronts an engine that can serve ~64 concurrent requests. Traffic spikes to 3×. Write the admission path.

sem           = Semaphore(MAX_INFLIGHT)
QUEUE_BUDGET  = 200ms          # max time we're willing to spend waiting for a slot
 
def handle(req):
    if not sem.acquire(timeout=QUEUE_BUDGET):
        metrics.shed(req.tenant)
        return Response(503, retry_after=jittered_backoff())   # shed, don't queue
    try:
        remaining = req.deadline - now()      # the queue ATE some of the budget
        if remaining <= 0:
            return Response(504, "deadline exceeded while queued")
        ctx = Context(deadline=remaining, cancel_on=req.client_disconnected)
        return engine.generate(req, ctx)      # ctx must reach the scheduler
    finally:
        sem.release()                         # a leak here is permanent capacity loss

The argument to make out loud. By Little's Law, $N = \lambda T$. If arrival rate $\lambda$ exceeds service capacity, the queue grows without bound and queueing time is added to every request — so instead of some requests failing, all of them miss SLO, and you've converted a partial outage into a total one. A bounded queue with fast shedding is strictly better: some requests get a clean, retryable 503 and the rest are served correctly. Say the line: "an unbounded queue is where your latency SLO goes to die."

Follow-ups. Per-tenant fairness on top? The semaphore is global — a single tenant can hold all 64 slots. Add per-tenant caps or a fair-share selector before the semaphore. Priority? Two semaphores with a reserved pool for interactive traffic, so batch work can never consume the last slot. Why does cancellation matter so much here? Because an LLM request keeps generating — and keeps costing money and KV — long after the client is gone. ctx has to reach the engine's running set, not stop at the HTTP handler. Retry storms? jittered_backoff, always: without jitter, every shed client retries at the same instant and you've built a self-inflicted DDoS.

5. Round D — low-level design

D1 · The object model for /v1/chat/completions

Design the classes for an OpenAI-compatible chat-completions server that fronts multiple engines, supports streaming, caching, routing, and guardrails.

Clarify. Streaming and non-streaming both? (Yes.) Multiple backends? (Yes.) Tool calling? (Yes.) Multi-tenant? (Yes.)

Approach. Name the seams, not the fields. The design goal is that adding a backend, a routing policy, a cache tier, or a guardrail each touches exactly one class.

# ---------- wire types ----------
class ChatRequest:
    model; messages[]; tools[]; tool_choice
    stream; max_tokens; temperature; top_p; stop[]
    user; idempotency_key; deadline; tenant
 
class Message:       role; content_parts[]; tool_calls[]; tool_call_id
class Chunk:         id; model; delta; finish_reason; usage?
class Usage:         prompt_tokens; completion_tokens; cached_tokens; reasoning_tokens
 
# ---------- seams (one implementation each, swap freely) ----------
interface Router:     select(req, ctx) -> Endpoint
interface Cache:      lookup(req, ctx) -> Response | MISS ;  store(req, resp, ctx)
interface Guardrail:  on_input(req) -> Verdict ;  on_output(chunk) -> Verdict
interface Engine:     generate(req, ctx) -> Iterator[Chunk]
interface Tokenizer:  count(messages, tools) -> int
interface UsageSink:  record(tenant, usage, model, latency)
interface Middleware: handle(req, ctx, next) -> Iterator[Chunk]
 
# ---------- the service ----------
class ChatCompletionsService:
    chain = [Auth, Quota, Budget, Idempotency, GuardrailIn,
             CacheLookup, Route, Generate, GuardrailOut, CacheStore, Usage]
 
    def complete(self, req, ctx):
        stream = self.chain.run(req, ctx)        # ALWAYS a stream internally
        return stream if req.stream else collect(stream)   # collect for non-stream

The five decisions worth defending.

1. One internal code path. Generate a stream always; collapse it for non-streaming callers. Two separate paths is how you end up with stop sequences honored in one mode and not the other — a real bug in real servers.
2. Idempotency as middleware. idempotency_key → (status, response) in a short-TTL store. A retried POST returns the original result rather than generating (and billing) twice. Note the interaction: a streaming response can only be replayed if you buffered it, so the honest rule is idempotent replay for non-streaming, and "in-flight, attach to the existing stream" for streaming.
3. finish_reason is a closed taxonomy — stop | length | tool_calls | content_filter — and it is not the error channel. Errors are a separate type with their own taxonomy (invalid_request | rate_limit | overloaded | upstream_timeout | internal), because clients branch on them differently: some are retryable, some never are.
4. Context is threaded everywhere. Deadline, cancellation, tenant, trace ID, budget. It's the only way cancellation reaches the engine and the only way traces stitch together. Follow the OpenTelemetry GenAI conventions for span and attribute names rather than inventing your own.
5. Response echoes a resolved fingerprint — the concrete model version plus a hash of (prompt template, decoding params, tool schema). When a client reports "quality dropped Tuesday," that field is how you find out what actually changed.

Follow-ups. Where does the router's policy live? In config, reloadable, versioned — never in code, or every model migration is a deploy. Adding a new backend? One Engine implementation. If it requires touching anything else, the abstraction is wrong. Where do you enforce max_tokens defaults? At the edge, before the quota check — the rate limiter's reservation math (B2) depends on a bounded estimate existing.

6. Pre-flight: how to run the round

The seven-step protocol. Same for every problem above; run it even when the answer is obvious, because the process is half the score.

1. Restate the problem in one sentence. Catches misunderstandings while they're free.
2. Clarify with two or three questions — input shape, edge conventions, scale. (In B1 that's "what order?"; in A4 it's "half-open or closed intervals?")
3. State the invariant before writing the loop. "Every scheduled step fits the KV budget and no admitted sequence is starved."
4. Brute force out loud, then improve. Never write the brute force unless asked.
5. Write it, narrating the non-obvious lines only. Silence for two minutes reads as being stuck.
6. Trace one example by hand — especially an edge case (empty input, $n{=}1$, everything pinned).
7. State complexity and the tradeoff you took. Then name one thing you'd change for production.

What separates the levels on the same problem:

A two-week drill schedule, if that's your budget:

7. Flashcards

• Prefix-cache keys must be chained — block $i$'s hash folds in block $i{-}1$'s.
• Evict prefix-cache blocks leaf-first, and only at refcount == 0.
• RRF: Σ w / (60 + rank). Rank is scale-free; raw scores are not.
• Sampling order: penalty → temperature → top-k → top-p → renormalize → sample. temp == 0 short-circuits to argmax.
• Quickselect for top-k ($O(V)$); sort only the survivors. Never sort 128K logits.
• Softmax: subtract the max first, or exp overflows.
• Top-p cut is inclusive — always keep ≥ 1 token.
• LLM rate limits are two-dimensional (RPM and TPM); reserve pessimistically, refund on settle.
• Scheduler: decode costs 1 token, prefill costs its chunk. Preempt the newest.
• Paged KV + COW: only the last partial block is ever copied on fork.
• Streaming: hold back any suffix that could become a stop sequence, and any partial UTF-8 char.
• Speculative decoding is lossless — the residual max(0, p−q) makes it exact.
• One condvar per thread + targeted signal beats broadcast; a shared condvar + signal deadlocks for $N > 2$.
• Micro-batch deadline anchors on the oldest item.
• Bounded queue + shed > unbounded queue. N = λT.
• (1 << k) - 1 overflows at k == wordsize. Use ONES >> (W - k).

8. Further reading

Sampling and tokenization — Temperature, top-k, top-p explained · Reference top-k/nucleus implementation · BPE from scratch · minbpe

Serving internals — Continuous batching, explained · Cohere: serving fairness · QEfficient — Qualcomm's model onboarding library

Rate limiting — Token bucket, from the ground up · Distributed rate limiter breakdown

The loop itself — Qualcomm interview process (2026) · Qualcomm SWE interview guide · Candidate experiences · Staff Engineer questions, Glassdoor