OpenAI 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.

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: build an array that supports taking cheap snapshots and later querying the value of any index at any past snapshot, without paying the cost of copying the whole array on every snap(). The efficient solution stores, per index, a sparse list of (snap_id, value) pairs and binary-searches that list on get() rather than materializing full array copies — the model-state-checkpointing framing (as noted in this problem's source context) maps directly onto this pattern, since checkpointing large state cheaply and querying it later by version is the same underlying need. It tests whether a candidate reaches for a lazy, per-index versioning scheme instead of a naive full-copy snapshot.

Given a list of words sorted according to an unknown alphabet's ordering, the task is to reconstruct a valid character ordering: build a directed graph of precedence constraints from adjacent word comparisons, then topologically sort it (Kahn's algorithm or DFS-based), detecting cycles as an invalid/impossible ordering. The task is conceptually similar to inferring a token ordering from partial, pairwise evidence, which is plausibly why it resonates with companies doing tokenizer/vocabulary-adjacent ML work. It's a solid test of translating a word-comparison problem into a graph and correctly handling topological sort edge cases (cycles, ties, unreachable characters).

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 harder relative of LRU Cache: eviction is based on least frequency of use (with least-recently-used as a tiebreaker), requiring O(1) get and put. The standard solution uses a hash map from key to value/frequency plus a second structure — typically frequency buckets implemented as doubly linked lists, tracked with a pointer to the current minimum frequency — to keep every operation O(1). This is a genuinely advanced caching pattern relevant to systems needing usage-aware eviction beyond simple recency, which is why it appears in interview loops as a step up from LRU Cache once a candidate has demonstrated that baseline.

A simulation/design problem where you implement allocate and free operations over a fixed-size block of memory, tracking which addresses are in use versus free and associating each allocation with an ID so it can be freed later. At OpenAI this reportedly comes up in the context of GPU memory management, which fits — the underlying skill being tested is bookkeeping over a constrained resource with alloc/free semantics, directly analogous to managing GPU memory pools during training or inference. It rewards a clean choice of data structure for tracking free/used regions over brute-force scanning of every address on each call.

Simulates one step of Conway's Game of Life on a 2D grid, applying birth/death rules to every cell simultaneously based on its live-neighbor count. The standard follow-up, and the one OpenAI reportedly asks, is doing the update in-place without a second buffer — typically by encoding both the old and new state in each cell's bits temporarily — and then extending the board to be infinite/unbounded, where you can't just index into a fixed grid. That extension pushes the problem from array manipulation toward sparse-representation thinking, since only a finite set of live cells can realistically be tracked on an unbounded board.

This is a classic interval-scheduling problem: given a list of meeting time intervals, find the minimum number of rooms required so no two overlapping meetings share a room. The standard approach sorts start and end times separately (or uses a min-heap of end times) and sweeps through them, tracking how many meetings are simultaneously active to determine the peak concurrent overlap, which equals the answer. It's a strong, well-known signal for interval-scheduling reasoning, and its overlap-counting technique generalizes directly to resource-allocation and scheduling problems in real systems.

A string-design problem: implement encode and decode functions that pack an arbitrary list of strings into a single string and reliably recover the original list, even when the strings themselves contain delimiter-like characters. The standard solution prefixes each string with its length (e.g., '5#hello'), since naive delimiter-based joining breaks on strings that contain that delimiter. OpenAI reportedly frames this within a broader 'serialization family' of questions, testing whether a candidate reasons correctly about self-describing formats — a skill that generalizes directly to designing wire protocols or serialization schemes for real systems.

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.

Requires counting element frequencies with a hash map, then selecting the k most frequent using either a heap (O(n log k)) or bucket sort by frequency (O(n)). It's a common building block for ML preprocessing workflows — identifying the most frequent tokens, features, or events in a dataset before further processing — which is part of why it recurs in ML-adjacent interview loops. The bucket-sort approach in particular tests whether a candidate recognizes that frequency is bounded by array length and can exploit that to avoid a full sort.

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 stack-based string-processing problem: decode a nested, run-length-encoded string like "3[a2[c]]" into its expanded form, where the nesting can go arbitrarily deep. The standard approach pushes the current string and repeat count onto a stack whenever a '[' is seen and pops/multiplies/concatenates on ']'. It's a clean test of stack-based parsing and correctly handling nested state, which is exactly why it's used across companies as a string-processing check.

Word Ladder models words as nodes in an implicit graph, connecting two words if they differ by exactly one letter, and asks for the shortest transformation sequence from a start word to an end word via BFS. Because the graph isn't given explicitly, candidates must generate neighboring words on the fly (e.g., by trying all 26 letter substitutions at each position) and use a word dictionary/set for O(1) membership checks and visited tracking. Its practical relevance in interviews often ties to NLP transformations — reasoning about minimal edit-style paths between text tokens — which is one reason it recurs in ML-adjacent interview loops.