Coding round · 130 problems
The coding round, for AI engineers.
LLM-specific problems (tokenizers, attention, sampling, retrieval, evals, agent loops), practical multi-stage builds, and classic algorithms and systems. Every solution has passing tests, its complexity, and the follow-up a staff interviewer asks next. Each page hides the solution until you reveal it.
130 problems · 0 practised · practical builds mirror the multi-stage format many AI labs use; no question here is claimed to come from a specific company.
1Two SumGiven an integer array nums and a target, return the indices of the two distinct elements that sum to target. Exactly one solution exists.2Group AnagramsGiven a list of strings, group the strings that are anagrams of each other.3Top K Frequent ElementsGiven an integer array nums and integer k, return the k most frequent elements in any order.4Product of Array Except SelfReturn an array where output[i] is the product of all elements of nums except nums[i], without using division, in O(n).5Longest Consecutive SequenceGiven an unsorted integer array, return the length of the longest run of consecutive integers, in O(n) time.6Subarray Sum Equals KGiven an integer array (may contain negatives) and k, return the number of contiguous subarrays whose sum equals k.73SumReturn all unique triplets in nums that sum to zero.8Container With Most WaterGiven heights of vertical lines, find two lines that with the x-axis hold the most water and return that area.9Longest Substring Without Repeating CharactersReturn the length of the longest substring of s with no repeated characters.10Minimum Window SubstringGiven strings s and t, return the smallest substring of s that contains every character of t (with multiplicity), or an empty string.11Sliding Window MaximumGiven nums and window size k, return the maximum of each contiguous window of size k.12Valid ParenthesesGiven a string of brackets ()[]{}, determine whether every opener is closed by the matching type in the correct order.13Daily TemperaturesGiven daily temperatures, return for each day how many days until a warmer temperature (0 if none).14Largest Rectangle in HistogramGiven bar heights of a histogram with width 1, return the area of the largest rectangle.15Basic Calculator IIEvaluate a string expression with non-negative integers, + - * / and spaces; integer division truncates toward zero.16Search in Rotated Sorted ArrayGiven a rotated sorted array of distinct integers and a target, return its index or -1 in O(log n).17Koko Eating BananasGiven pile sizes and h hours, find the minimum integer eating speed k so all piles are finished within h hours (one pile per hour max).18Median of Two Sorted ArraysGiven two sorted arrays, return the median of their combined elements in O(log(min(m, n))).19Find Peak ElementGiven an array where adjacent elements differ, return the index of any peak (strictly greater than its neighbours, with out-of-bounds treated as -infinity) in O(log n).20Time Based Key-Value StoreDesign a store with set(key, value, timestamp) and get(key, timestamp) that returns the value with the largest timestamp <= the given one, or an empty string.21Reverse Linked ListGiven the head of a singly linked list, reverse the list in place and return the new head.22Merge K Sorted ListsGiven k sorted linked lists, merge them into one sorted linked list and return its head.23Copy List with Random PointerEach node has a next pointer and a random pointer to any node or null. Return a deep copy of the list.24Linked List Cycle II (Find Cycle Start)Given a linked list, return the node where a cycle begins, or None if there is no cycle, using O(1) extra space.25Binary Tree Level Order TraversalReturn the values of a binary tree level by level, left to right, as a list of lists.26Validate Binary Search TreeDetermine whether a binary tree is a valid BST: every node's left subtree holds strictly smaller keys and its right subtree strictly larger keys.27Lowest Common Ancestor of a Binary TreeGiven a binary tree and two nodes p and q in it, return their lowest common ancestor.28Serialize and Deserialize Binary TreeDesign functions that serialize a binary tree to a string and deserialize that string back into an identical tree.29Binary Tree Maximum Path SumA path is any sequence of connected nodes with no node repeated; return the maximum sum over all non-empty paths.30Kth Smallest Element in a BSTGiven the root of a BST and an integer k, return the kth smallest value (1-indexed).31Binary Tree Right Side ViewReturn the values visible when looking at a binary tree from the right side, top to bottom.32Construct Binary Tree from Preorder and Inorder TraversalGiven preorder and inorder traversals of a binary tree with unique values, reconstruct and return the tree.33Kth Largest Element in an ArrayReturn the kth largest element of an unsorted array without fully sorting it.34Find Median from Data StreamDesign a structure supporting add_num(x) and find_median() over a stream of integers.35Task SchedulerGiven CPU tasks labeled by letters and a cooldown n between identical tasks, return the minimum number of time units to finish all tasks (idling allowed).36K Closest Points to OriginGiven a list of 2D points and an integer k, return the k points closest to the origin (any order).37Merge IntervalsGiven a list of intervals [start, end], merge all overlapping intervals and return the result.38Meeting Rooms IIGiven meeting time intervals [start, end), return the minimum number of rooms required.39Insert IntervalGiven sorted non-overlapping intervals and a new interval, insert it and merge as needed, returning sorted non-overlapping intervals.40Employee Free TimeGiven each employee's sorted list of non-overlapping working intervals, return the finite intervals during which all employees are free.41Number of IslandsGiven an m x n grid of '1' (land) and '0' (water), return the number of islands, where an island is a group of land cells connected horizontally or vertically.42Course Schedule II (Topological Sort)Given numCourses and prerequisite pairs [course, prereq], return any valid order to take all courses, or an empty list if a cycle makes it impossible.43Clone GraphGiven a reference to a node in a connected undirected graph, return a deep copy where each node has a value and a list of neighbors.44Word LadderGiven beginWord, endWord and a word list, return the number of words in the shortest transformation sequence changing one letter at a time, with every intermediate word in the list; return 0 if impossible.45Network Delay Time (Dijkstra)Given directed weighted edges (u, v, w) over nodes 1..n and a source k, return the time for a signal from k to reach all nodes, or -1 if some node is unreachable.46Redundant Connection (Union-Find)A tree of n nodes had one extra edge added. Given the edge list, return the edge that can be removed to restore a tree; if several, return the one that appears last.47Alien DictionaryGiven a list of words sorted in an unknown alphabet's lexicographic order, return a string of the letters in a valid order, or empty string if the ordering is invalid.48Critical Connections (Tarjan Bridges)Given n servers and undirected connections, return all critical connections: edges whose removal disconnects some servers.49Cheapest Flights Within K StopsGiven flights (from, to, price), find the cheapest price from src to dst using at most k stops, or -1 if none exists.50Accounts MergeGiven accounts as [name, email1, email2, ...], merge accounts that share any email and return each merged account as name followed by its sorted emails.51Coin ChangeGiven coin denominations and an amount, return the fewest coins needed to make the amount, or -1 if impossible (unlimited coins of each kind).52Longest Increasing Subsequence (O(n log n))Given an integer array, return the length of the longest strictly increasing subsequence.53Edit DistanceGiven two strings, return the minimum number of single-character inserts, deletes, or substitutions to convert one into the other.54Word BreakGiven a string s and a dictionary of words, return whether s can be segmented into a sequence of one or more dictionary words.55Longest Common SubsequenceGiven two strings, return the length of their longest common subsequence.56House Robber IIHouses are arranged in a circle; adjacent houses cannot both be robbed. Given each house's money, return the maximum amount you can rob.57Decode WaysA message of digits is encoded with A=1..Z=26. Return the number of ways to decode it.58Partition Equal Subset SumGiven an array of positive integers, return whether it can be split into two subsets with equal sums.59Burst BalloonsBursting balloon i earns nums[left]*nums[i]*nums[right] where left/right are current neighbors (out of bounds = 1). Return the maximum coins from bursting all balloons.60Best Time to Buy and Sell Stock with CooldownGiven daily prices, maximize profit with unlimited transactions, where after selling you must wait one day before buying again (hold at most one share).61Implement TrieImplement a prefix tree supporting insert(word), search(word) for exact match, and starts_with(prefix).62Word Search IIGiven an m x n board of letters and a list of words, return all words that can be formed by sequentially adjacent (4-directional) cells, using each cell at most once per word.63Search Autocomplete System (Top-3 by Frequency)Design an autocomplete system initialized with historical sentences and counts. input(c) appends c to the current query and returns the top 3 historical sentences with that prefix, ranked by count desc then lexicographically; '#' ends the query, records it, and returns [].64Longest Palindromic SubstringReturn the longest palindromic substring of s.65Encode and Decode List of StringsDesign encode(list[str]) -> str and decode(str) -> list[str] such that decode(encode(x)) == x for any strings, including empty strings and strings containing any delimiter.66strStr via KMP (and Rabin-Karp)Return the index of the first occurrence of needle in haystack, or -1. Achieve linear time.67LRU Cache from ScratchImplement an LRU cache with get(key) and put(key, value) in O(1), evicting the least-recently-used entry when capacity is exceeded. Do not use OrderedDict.68LFU Cache in O(1)Implement an LFU cache with get and put in O(1). On eviction remove the least-frequently-used key; break ties by least-recently-used.69Rate Limiter: Token Bucket and Sliding-Window LogImplement two per-client rate limiters with allow(client_id) -> bool: a token bucket (capacity, refill rate per second) and a sliding-window log (max N requests in any trailing W seconds). Clock must be injectable.70Consistent Hashing Ring with Virtual NodesImplement a consistent hash ring with add_node, remove_node, and get_node(key). Each physical node owns V virtual points to smooth load distribution.71In-Memory Key-Value Store with TTL (Lazy + Active Expiry)Build a KV store with set(key, value, ttl=None), get(key), delete(key), and sweep() that actively reclaims expired keys. Expired keys must never be returned.72KV Store with Nested TransactionsImplement a KV store supporting set, get, delete, begin, rollback, and commit. Transactions nest: rollback undoes only the innermost; commit applies all open transactions. Rollback/commit with no open transaction returns False.73Snapshot ArrayImplement SnapshotArray(length) with set(index, val), snap() returning a snapshot id, and get(index, snap_id) returning the value at that index when that snapshot was taken.74Design Hit CounterDesign a counter with hit(timestamp) and get_hits(timestamp) returning hits in the past 300 seconds (inclusive window (t-300, t]). Timestamps are non-decreasing seconds and many hits can share a second.75Randomized Set: O(1) Insert, Remove, GetRandomImplement a set with insert(val), remove(val), and get_random() all in average O(1), where get_random returns each present element with equal probability.76In-Memory File SystemImplement ls(path), mkdir(path), add_content_to_file(path, content), and read_content_from_file(path). ls on a file returns [filename]; on a directory returns sorted children. mkdir and add_content create missing parents.77Versioned (MVCC) Key-Value StoreImplement put(key, value) -> version using a global monotonically increasing version, get(key, version=None) returning the value as of that version (latest if None), and delete(key) -> version.78In-Memory SQL-like TableImplement Table(columns) with insert(row: dict), select(columns, where=None, order_by=None, limit=None) where where is a list of (column, op, value) conjuncts and order_by is a list of (column, 'asc'|'desc'). Optionally create_index(column) for equality lookups.79Flatten Nested List IteratorGiven an arbitrarily nested list of integers, implement an iterator with next() and has_next() that yields the integers in order, lazily.80Peeking IteratorWrap any iterator to support peek() (return next element without advancing), next(), and has_next(). Must work for iterators that may yield None.81Concurrent Web Crawler (Thread Pool)Given a start URL and a blocking fetch(url) -> list[str] of links, crawl every reachable page on the same hostname concurrently using a thread pool and return the set of visited URLs.82Asyncio Crawler with Bounded ConcurrencyImplement an asyncio crawler that, given an async fetch(url) -> list[str], visits all same-host pages while never running more than N fetches at once.83Bounded Blocking QueueImplement a thread-safe bounded queue where put blocks while full and get blocks while empty, with optional timeouts.84Thread-Safe Token Bucket Rate LimiterImplement a token bucket with a refill rate and burst capacity that supports try_acquire(n) and reports how long to wait, safe under concurrent callers.85Writer-Preferring Read-Write LockImplement a read-write lock allowing many concurrent readers or one writer, where waiting writers block new readers so writers cannot starve.86Retry Decorator with Exponential Backoff and JitterWrite a decorator that retries a function on specified exceptions using capped exponential backoff with full jitter, re-raising after max attempts.87Thread-Safe LRU Cache Decorator with TTLImplement a memoizing decorator with a max size (LRU eviction) and per-entry time-to-live that is safe to call from multiple threads.88Parallel DAG Task ExecutorGiven tasks and their dependencies, run every task once its dependencies finish, executing independent tasks in parallel and passing upstream results as arguments; detect cycles.89External Merge SortSort a stream of integers too large for memory, given that at most chunk_size items fit in RAM: produce sorted runs on disk, then k-way merge them lazily.90Merge K Sorted IteratorsWrite a generator that lazily merges k sorted (possibly infinite) iterators into one sorted stream, with an optional key and stable tie-breaking.91Reservoir SamplingReturn a uniform random sample of k items from a stream of unknown length in a single pass using O(k) memory.92Count-Min SketchImplement a Count-Min Sketch supporting add(item, count), estimate(item), and merge, sized from error epsilon and failure probability delta.93HyperLogLog Cardinality EstimationImplement a simplified HyperLogLog that estimates the number of distinct items in a stream, supports merging, and corrects for small cardinalities.94Top-K Heavy Hitters (Misra-Gries)In one pass with O(k) memory, find all items occurring more than n/k times in a stream, returning candidate counts and the top candidates.95Hash Join and Sort-Merge JoinImplement an inner equi-join of two lists of dict rows on given key columns, once as a hash join and once as a sort-merge join, handling duplicate keys and NULLs.96Tumbling and Sliding Window AggregationGiven (timestamp, value) events, compute per-window sums for tumbling windows of a given size and for sliding (hopping) windows of a given size and slide.97Stream Deduplication with Idempotency Keys and WatermarkProcess an at-least-once event stream so each idempotency key is emitted exactly once, keeping bounded state by evicting keys older than a watermark and dropping events that arrive too late.98LSM Tree: Memtable Flush and SSTable CompactionBuild a tiny LSM store: writes go to a memtable that flushes to immutable sorted SSTables when full; reads check newest first; deletes write tombstones; compaction merges SSTables keeping the newest version and dropping tombstones.99Distributed Group-By with Partial AggregatesCompute per-key count, sum, min, max and avg over rows spread across partitions using a map-side combine, a hash shuffle to R reducers, and a final reduce.100Parse and Evaluate a SQL WHERE ClauseGiven a WHERE expression with comparisons, AND/OR/NOT, IN lists, parentheses, numbers and quoted strings, compile it into a predicate over dict rows.101Byte-Pair Encoding: Train Merges and EncodeImplement BPE from scratch. `train_bpe(corpus, num_merges)` splits each text on whitespace, represents every word as characters plus an end-of-word marker `</w>`, and repeatedly merges the most frequent adjacent pair (ties broken by the lexicographically smallest pair) until `num_merges` merges are learned or no pairs remain. `encode(word, merges)` tokenises a new word by applying the learned merges in rank order.102Byte-Fallback Detokenizer with StreamingA SentencePiece-style vocab maps ids to pieces. Normal pieces use `▁` for a leading space; byte-fallback pieces look like `<0xE2>` and stand for one raw byte. Write `decode(ids, vocab)` that returns the text (dropping the single leading space the first piece introduces), and a `StreamDecoder` whose `push(id)` returns only the text that is now complete, holding back partial UTF-8 sequences, plus `flush()` for the end of stream.103Numerically Stable Softmax with TemperatureWrite `softmax(logits, temperature=1.0)` that returns a probability distribution. It must not overflow for logits like `[1000, 1001]`, must treat `-inf` logits as masked (probability 0), must return a one-hot on the first argmax when `temperature == 0` (greedy), and must raise `ValueError` on empty input, negative temperature, or when every logit is masked.104Top-k, Top-p and Min-p Sampling with a Seeded RNGImplement `filter_probs(logits, top_k=0, top_p=1.0, min_p=0.0)` that converts logits to probabilities and keeps a token only if it survives all active filters: in the `top_k` most likely (0 disables), in the smallest prefix of the sorted distribution whose cumulative mass reaches `top_p`, and with probability at least `min_p` times the top probability. Renormalise the survivors. Then `sample(logits, rng, temperature, ...)` applies temperature first, filters, and draws with the given `random.Random`; temperature 0 is greedy.105Beam Search with Length NormalisationGiven `step_fn(prefix) -> dict[token, logprob]`, implement `beam_search(step_fn, beam_width, max_len, eos, alpha)`. Keep the `beam_width` best live hypotheses per step; a hypothesis that emits `eos` moves to a finished list. Rank candidates by total log-probability (ties: lexicographic token order). At the end, return the best finished-or-live hypothesis by `logprob / len(seq) ** alpha` (alpha = 0 means raw log-probability).106Scaled Dot-Product Attention with a Causal MaskUsing only Python lists, implement `attention(Q, K, V, causal=False)` where `Q` is `Tq x d`, `K` is `Tk x d` and `V` is `Tk x dv`. Compute `softmax(Q K^T / sqrt(d)) V` row by row. With `causal=True`, query i (aligned to the **end** of the key sequence, so `Tq <= Tk` works for incremental decoding) may only attend to keys at positions `<= i + (Tk - Tq)`.107Multi-Head and Grouped-Query Attention ShapesImplement multi-head self-attention on lists: project `X` (T x d_model) with `Wq`, `Wk`, `Wv` (d_model x d_model for queries; d_model x (n_kv_heads * head_dim) for keys and values), split into heads, run causal attention per head, concatenate, and project with `Wo`. Support grouped-query attention, where `n_heads` query heads share `n_kv_heads` key/value heads (`n_heads % n_kv_heads == 0`). Also write `kv_cache_bytes(layers, n_kv_heads, head_dim, seq_len, batch, bytes_per_value)`.108KV-Cache Incremental Decode EquivalenceBuild a one-layer, one-head toy decoder: deterministic token embeddings (seeded), projections Wq, Wk, Wv, causal attention, and an unembedding to logits. Implement `full_forward(tokens)` that recomputes every position from scratch and a `KVCache` class whose `step(token)` projects only the new token, appends its K and V, and attends over the cache. Prove they produce the same logits at every position and the same greedy continuation, and count projection calls to show the saving.109Cosine Top-k with a Bounded HeapWrite `top_k_cosine(query, corpus, k)` where `corpus` maps doc id to an embedding. Return the `k` most similar `(id, score)` pairs by cosine similarity, highest first, ties broken by smaller id. Skip zero vectors (cosine is undefined), raise on a zero query or a dimension mismatch, and use a size-k min-heap so memory stays O(k) for any corpus size.110BM25 Scoring from ScratchImplement a `BM25` class over a list of documents with parameters `k1=1.5`, `b=0.75`. Tokenise by lowercasing and extracting `[a-z0-9]+`. Use the non-negative IDF `log(1 + (N - df + 0.5) / (df + 0.5))`. Provide `score(query, doc_index)` and `search(query, k)` returning `(doc_index, score)` pairs, highest first, ties by lower index, omitting zero scores.111Reciprocal Rank FusionWrite `rrf(rankings, k=60, weights=None)` that fuses several ranked lists of doc ids (best first) into one. Each list contributes `weight / (k + rank)` with 1-based ranks; a doc repeated within one list counts only at its first rank. Return `(doc_id, score)` sorted by score descending, ties by doc id.112Recursive Sentence-Aware Chunker with Token OverlapWrite `chunk(text, max_tokens, overlap_tokens)` (tokens = whitespace words). Split recursively: paragraphs on blank lines, then sentences on `.`, `!` or `?` followed by whitespace, and only a sentence longer than `max_tokens` is cut into word windows. Greedily pack sentences into chunks of at most `max_tokens`; when starting a new chunk, carry over the trailing whole sentences of the previous chunk whose total is at most `overlap_tokens` (and that still leave room for the next sentence). Raise `ValueError` unless `0 <= overlap_tokens < max_tokens`.113Maximal Marginal Relevance DiversificationImplement `mmr(query, docs, k, lam)` where `docs` maps id to embedding. Iteratively select the doc maximising `lam * sim(query, d) - (1 - lam) * max(sim(d, s) for s in selected)` (the max term is 0 when nothing is selected yet), using cosine similarity. Ties go to the smaller id. Return up to `k` ids in selection order.114Tenant-Scoped Semantic Cache with TTLBuild `SemanticCache(embed, threshold, ttl_seconds, max_per_tenant, clock)`. `get(tenant, query)` first tries an exact hit on the normalised query (NFKC, casefold, collapse whitespace, strip trailing `?!.`), then falls back to the most similar cached query **in the same tenant** with cosine >= `threshold`. Expired entries (older than TTL by the injected clock) never hit. `put(tenant, query, answer)` evicts the least recently used entry when a tenant exceeds `max_per_tenant`.115Async LLM Client: Token Bucket, Semaphore, Retries with JitterWrite an asyncio `LLMClient(transport, tpm, max_concurrency, max_retries, base_delay, max_delay, rng, clock)`. `complete(prompt, max_tokens)` estimates tokens (`len(prompt) // 4 + 1 + max_tokens`), waits on a tokens-per-minute bucket, limits in-flight calls with a semaphore, and calls `await transport(prompt, max_tokens) -> (text, tokens_used)`. On `RetryableError` it refunds the estimate and retries with full-jitter exponential backoff (or the error's `retry_after`), up to `max_retries`; other exceptions propagate immediately. After success it reconciles the bucket with the real usage. Use an injected fake clock so tests take milliseconds.116SSE Stream Parser that Reassembles Tool-Call ArgumentsA streaming LLM API sends Server-Sent Events. Each event's `data:` is JSON: `{"type":"text","delta":...}`, `{"type":"tool_call_start","index","id","name"}`, `{"type":"tool_call_delta","index","args":<partial JSON string>}`, `{"type":"tool_call_end","index"}`, and finally `data: [DONE]`. Bytes arrive in arbitrary chunks that can split lines, CRLFs and multi-byte UTF-8 characters. Write `StreamAssembler.feed(chunk: bytes)` and `result()` returning the full text and the parsed arguments of every tool call; `result()` must raise if the stream ended early or a tool call never closed.117JSON-Schema-Lite Validator with a Repair Retry LoopWrite `validate(value, schema, path="")` supporting `type` (object, array, string, integer, number, boolean, null), `properties`, `required`, `additionalProperties: false`, `items`, `enum`, `minimum`/`maximum`, `minLength`/`maxLength`. Return a list of errors like `"/items/1/qty: expected integer"`. Then `generate_json(llm, schema, messages, max_attempts)` calls `llm(messages) -> str`, strips a Markdown code fence if present, parses and validates, and on failure appends the bad output and a user message listing the errors before retrying. Return `(obj, attempts)` or raise after `max_attempts`.118Prompt-Injection-Safe Tool Router with an AllowlistModel output proposes tool calls like `{"name": ..., "arguments": {...}}`. Write `ToolRouter(tools, allowed_domains).route(call, session_allowlist, tainted)` returning a `Decision(allowed, reason, needs_approval)`. Reject unknown tools (exact name match only), tools not in this session's allowlist, missing or extra arguments, and wrong argument types (exact type: a bool is not an int). For URL parameters require `https` and a hostname equal to, or a subdomain of, an allowed domain. If the context is `tainted` (it contains untrusted content such as a fetched web page) a `write` tool is not executed but returned with `needs_approval=True`.119Minimal Agent Loop with Budgets and Stop ReasonsWrite `run_agent(model, tools, task, max_steps, max_tokens, max_consecutive_errors, max_repeats)`. Each step calls `model(transcript)`, which returns `{"type": "final", "content": ...}` or `{"type": "tool", "name": ..., "args": {...}}` plus an optional `usage` token count. Run tools and append their output (or the exception text, flagged `is_error`) to the transcript. Stop with an explicit reason: `final`, `max_steps`, `token_budget`, `repeated_call` (the same tool with identical arguments more than `max_repeats` times) or `tool_errors` (more than `max_consecutive_errors` failures in a row).120Eval Harness with a Paired Bootstrap Confidence IntervalTwo systems A and B were scored on the same n eval items (`a[i]`, `b[i]`). Write `paired_bootstrap(a, b, n_resamples, alpha, seed)` that resamples item indices with replacement, computes the mean of `b[i] - a[i]` for each resample, and returns the observed mean difference, the percentile confidence interval `(lo, hi)`, and the fraction of resamples where B is not better (`<= 0`). Also write `unpaired_bootstrap` that resamples A and B independently, and show the paired CI is much tighter on the same data.121LLM-Judge Position-Bias Check by Swapping OrderA pairwise judge `judge(first, second) -> "first" | "second" | "tie"` compares two answers. For each pair `(a, b)`, call it in both orders, map both verdicts back to `A`/`B`/`tie`, and record the final verdict only when the two orders agree (otherwise `tie`). Return the consistency rate, the rate at which decisive verdicts favour the first slot, a two-sided exact sign-test p-value for that first-slot rate against 0.5, and the per-pair verdicts.122Cohen's Kappa and Quadratic-Weighted KappaWrite `cohen_kappa(a, b)` for two raters' categorical labels on the same items: `(p_o - p_e) / (1 - p_e)` where `p_o` is observed agreement and `p_e` the agreement expected from each rater's label frequencies. Return 1.0 when `p_e == 1` and the raters agree perfectly. Then write `weighted_kappa(a, b, categories, weights="quadratic")` for ordinal labels, where disagreement weight is `((i - j) / (k - 1)) ** 2` (or the absolute value for `"linear"`) and kappa is `1 - observed_weighted_disagreement / expected_weighted_disagreement`.123Retrieval Metrics: Recall@k, MRR and nDCG@kGiven a ranked list of retrieved doc ids and graded relevance labels `qrels: dict[doc, int]` (0 = not relevant), implement `recall_at_k`, `mrr` (reciprocal rank of the first relevant doc, 0 if none) and `ndcg_at_k` with gain `2**rel - 1` and discount `log2(rank + 1)`. Duplicate ids in the ranking count only once. Then `evaluate(runs, qrels, k)` averages each metric over queries, **skipping** queries with no relevant documents and reporting how many were skipped.124Prompt-Cache Cost SimulatorSimulate prompt caching over a time-ordered request log. Each request has a timestamp, a `prefix_id` (identity of the exact cacheable prefix), `prefix_tokens`, `suffix_tokens` and `output_tokens`. Pricing (illustrative, per million tokens): input, output, cache-write multiplier (e.g. 1.25), cache-read multiplier (e.g. 0.1), TTL in seconds (refreshed on every hit) and a minimum cacheable prefix length. Return total cost, cost without caching, hits and writes. Also write `break_even_reads(write_mult, read_mult)`: the fewest cache reads after one write for caching to cost no more than not caching.125Token-Budget Context Packer with DedupeAssemble a context window. Items have `id`, `text`, `score`, `tokens` (> 0) and `pinned` (system prompt, user question: always included). Write `pack(items, budget, near_dup=0.8)`: raise if pinned items exceed the budget; drop candidates whose normalised text duplicates, or whose word-trigram Jaccard similarity is at least `near_dup` with, a higher-scored kept item or a pinned item; then choose candidates to maximise total score within the remaining budget using greedy-by-density (score per token) and the classic fix of also trying 'best single item first, then greedy fill', keeping whichever set scores higher. Return pinned items, then chosen items in their original order.126In-Memory Key-Value Store: TTL, Transactions, SnapshotsBuild an in-memory key-value store in four stages, each extending the last. The final version supports get/set/delete, per-key TTL against an injected clock, nested BEGIN/ROLLBACK/COMMIT, and snapshot/restore.127Rate-Limited LLM Request SchedulerBuild the scheduler that sits in front of an LLM provider. Requests carry a tenant, model, estimated tokens and a priority lane. Dispatch must respect a provider rate limit, per-tenant token quotas, priority with starvation protection, and track cost per tenant.128Document Ingestion Pipeline with Dedupe and TombstonesBuild the ingestion side of a RAG index. Documents arrive with an id and a version, possibly out of order and repeated. Chunk and embed them, never pay to embed the same content twice, re-embed only what changed on update, and handle deletes so late writes cannot resurrect a deleted document.129LLM Eval Runner with Caching and a Regression GateBuild an eval harness that runs a model over a test set, survives flaky APIs, avoids paying twice for the same call, and decides whether a candidate model may ship relative to a baseline.130Tool-Using Agent Runtime with Budgets, Checkpoints and ApprovalBuild the runtime loop for a tool-using agent. A policy (the model) maps history to a tool call or a final answer. The runtime must bound work, survive a restart mid-run, and never run a side-effecting tool without human approval.