Anthropic Interview Questions

A design problem requiring O(1) get and put operations with least-recently-used eviction, implemented by combining a hash map (for O(1) lookup) with a doubly linked list (for O(1) reordering and eviction from either end). This exact structure underlies real inference key-value caches — it's reportedly one of the most frequently asked design questions at companies building LLM inference systems, since eviction policy for a bounded cache maps directly onto managing GPU memory for attention KV caches. It's a strong test of whether a candidate can compose two data structures to get O(1) across every required operation, not just some of them.

This is a concurrency-design problem: given a starting URL and a getUrls(url) API, you must crawl all pages on the same hostname using multiple threads while avoiding revisiting a URL and safely sharing a visited set across threads. It tests whether a candidate can combine BFS/DFS-style graph traversal with real thread-safety mechanisms — locks, thread pools, or concurrent data structures — rather than just describing multithreading in the abstract. AI labs like Anthropic and OpenAI ask it because it mirrors real infrastructure work: crawling the web at scale to build training data corpora, where correctness and non-duplication under concurrency genuinely matter.

A foundational data-structure design problem: implement insert, search, and startsWith operations for a prefix tree, typically using nested hash maps or fixed-size child arrays per node. It tests whether a candidate understands how tries achieve O(L) lookups (L = word length) independent of dictionary size, and can reason cleanly about node structure and end-of-word marking. It's a common warm-up before harder trie-based follow-ups like wildcard search or autocomplete, and is frequently used to gauge comfort with recursive tree-like structures.

Given a string and a dictionary of words, this asks whether the string can be segmented into a space-separated sequence of dictionary words. The standard solution is DP where dp[i] indicates whether the prefix of length i can be segmented, checking all dictionary words as potential suffixes ending at each position. It's a foundational string-DP problem and often a stepping stone to the harder Word Break II, testing whether a candidate can define and fill a boolean DP array correctly.

This design problem asks for a counter that records hits with timestamps and can report the number of hits in the past 300 seconds. It's typically implemented with a queue (or a fixed-size circular buffer of timestamp/count pairs) that evicts entries falling outside the trailing time window as new hits arrive. It tests whether a candidate can design a data structure for a sliding time window under both single-hit and (in a common follow-up) batched-hit conditions.

A design problem requiring a hash map from key to a list of (timestamp, value) pairs, plus binary search to efficiently find the value at or before a queried timestamp. It tests whether a candidate can combine a hash map with binary search rather than resorting to a linear scan, since values are appended with strictly increasing timestamps. It's a natural fit for companies dealing with versioned or time-stamped storage — Anthropic and OpenAI probe it in the context of retrieving the right version of a model checkpoint by timestamp, a real pattern in ML infrastructure.

A design problem: encode a binary tree into a string and reconstruct an identical tree from that string, typically via a preorder traversal with explicit null markers, or a BFS-based level encoding. The candidate must design a format that's unambiguous enough for deserialization to rebuild structure without extra information. Interview relevance frequently maps to data persistence — serializing structured data for storage or transmission and reliably reconstructing it — which is why it shows up across companies handling tree-like or hierarchical data on disk or over the wire.

Merging k sorted linked lists efficiently requires either a min-heap holding the current head of each list (repeatedly popping the smallest and pushing its successor) or a divide-and-conquer pairwise merge, both achieving O(N log k). It tests whether a candidate can extend the two-list merge pattern to k lists and reason about the resulting complexity rather than defaulting to an O(Nk) linear scan across lists. Correct pointer management across multiple linked lists under time pressure is the practical difficulty.

A classic topological-sort problem: given courses and prerequisite pairs, return a valid ordering (or detect that no valid ordering exists due to a cycle). It tests whether a candidate can build an adjacency list, track in-degrees, and run Kahn's BFS algorithm (or DFS with visited/in-progress marking) to order and cycle-detect simultaneously. Its broad company reach reflects how often real systems need this exact shape of problem — resolving build or package dependency order, or task scheduling graphs — making it a reliable signal for graph traversal fluency.

A grid graph-traversal problem: count connected components of '1' cells using DFS, BFS, or Union-Find, being careful with boundary checks and marking visited cells so you don't recount. It's one of the most common entry points into grid-based graph problems and is often used as a warm-up before harder multi-source or Union-Find variants. The core signal is whether a candidate can translate a 2D grid into an implicit graph and correctly implement flood-fill without off-by-one or infinite-loop bugs.

For each element, this asks how many elements to its right are strictly smaller than it — a problem that resists brute force at scale (O(n^2)) and instead calls for an order-statistics structure. Common approaches are a modified merge sort that counts cross-inversions during the merge step, or a Binary Indexed Tree (Fenwick tree) over coordinate-compressed values. It's a solid test of whether a candidate can adapt a familiar algorithm (merge sort) to simultaneously answer a counting query, or apply a Fenwick tree correctly with coordinate compression.