OpenAI Interview: Design a Distributed Crossword Solver

Part of the OpenAI system design question bank. The question is representative of the round. The analysis and solution are this site's own.

Problem statement

The service takes a grid description and a dictionary, and returns one assignment of words to slots in which every crossing letter matches. Clues are ignored; generating grids is out of scope; one solution is enough.

The interviewer is not looking for the cleverest single-machine algorithm. The reported expectation is a distributed job system: prove one machine is too slow, then split the search across workers, handle dead ends and stuck workers, and stop everyone when one finds an answer. Candidates who spend the hour tuning the algorithm lose.

Clarifying questions

• Grid size? About 50 × 50 with about 100 slots, lengths 3 to 15.
• Dictionary? About a million words, uppercase letters only.
• Latency? Minutes are acceptable. The job runs asynchronously.
• Is a solution guaranteed to exist? Not always. If none exists, the system must eventually say so, or give up after a time limit.
• Can a word repeat? Assume no.
• Workload? Many puzzles submitted per day, so the system should share a worker pool.

What makes it hard

The search space is enormous. A slot of length 7 may have tens of thousands of dictionary candidates. With 100 slots, the raw number of assignments is the product of those counts, a number with hundreds of digits. No machine enumerates that.

Pruning cuts most of it: once a word is placed, crossing slots have fixed letters, and their candidate lists shrink. But hard grids still leave a search tree with billions of nodes, and its shape is unpredictable. One branch dies in a millisecond; another runs for an hour before failing.

So the driving tension is parallelism versus the irregular shape of the search. Splitting the work is easy; keeping every worker busy on a tree whose subtrees differ by orders of magnitude is the real problem.

flowchart TB
  R[Empty grid]:::svc --> A1[Slot 12 = ORBITAL]:::svc
  R --> A2[Slot 12 = CAPITAL]:::svc
  R --> A3[Slot 12 = ...]:::svc
  A1 --> B1[Slot 7 = ...]:::svc
  A1 --> B2[dead end]:::bad
  A2 --> B3[Slot 7 = ...]:::svc
  B3 --> C1[... 100 levels deep]:::svc
  classDef svc fill:#f4f1e8,stroke:#315e55,color:#171717;
  classDef bad fill:#fbe9e4,stroke:#c4492d,color:#171717;

Key idea. Show one machine is too slow in two minutes, then spend the round on splitting an irregular search tree and keeping workers busy.

Key concepts

Backtracking search

Depth-first search over assignments: pick a slot, try a candidate word, check consistency, recurse, and undo on failure. It uses little memory, because it holds only the current path.

Constraint propagation

After placing a word, update the candidate lists of every crossing slot to words that match the new fixed letters. If any list becomes empty, backtrack immediately instead of discovering the dead end many levels later.

Most constrained variable first

Choose the next slot with the fewest remaining candidates. It fails early when it will fail, which prunes the tree near the top, where pruning saves the most.

Work stealing

Idle workers take part of a busy worker's unexplored work. It balances an irregular tree without knowing its shape in advance.

Key idea. Depth-first search with propagation and smart slot choice on each worker; work stealing across workers.

1. Requirements

Before reading on. State the functional requirements and the one property the system must have when a solution exists.

1.1 Functional requirements

• Accept a grid (slots with position, direction, length) and a dictionary.
• Return one valid fill, or report that none was found within the time limit.
• Let clients check status and cancel.
• Share a worker pool across many puzzles.

1.2 Non-functional requirements

• Completeness: if a solution exists, the search eventually finds it, given enough time.
• Speed: minutes for typical hard grids.
• Utilization: workers stay busy until the job ends.
• Fault tolerance: a dead worker loses at most its current task, which is redone.
• Prompt termination: when one worker succeeds, all others stop within seconds.

1.3 The constraint versus the property

Completeness is the property: no branch may be dropped. Irregular work is the constraint: task sizes are unknown, which drives splitting and stealing.

1. Back-of-the-envelope estimation

• Candidates per slot: tens of thousands for common lengths. With 100 slots, the unpruned product is far beyond 10^100.
• Pruned search: a hard grid may still need billions of nodes. At 1 million nodes per second per core (each node filters candidate lists with bitset operations), 10 billion nodes take 10,000 core-seconds, about 3 hours on one core, or about 1 minute on 200 cores.
• Dictionary index in memory: 1 million words; a bitset per (length, position, letter) is 15 × 15 × 26 ≈ 5,850 bitsets. If each covers only the words of its length, the biggest length bucket may hold about 150,000 words, 19 KB per bitset, so the whole index is roughly 100 MB. Every worker holds a copy.
• Task messages: a task is a partial assignment, a few hundred bytes. Even 100,000 tasks are tiny.

Key idea. Hours on one core, a minute on a few hundred. The index fits on every worker; tasks are tiny.

1. API design

POST /v1/puzzles
  {slots: [{id, row, col, dir: "across"|"down", length}], dictionary_id, time_limit_s}
  -> 202 {job_id}
GET  /v1/puzzles/:job_id
  -> {status: queued|running|solved|unsolvable|timed_out|cancelled,
      solution?: {slot_id: word}, nodes_explored, elapsed_s}
POST /v1/puzzles/:job_id/cancel

POST /v1/dictionaries   {words[]} -> {dictionary_id}   // preprocessed into bitsets once

Internal:

task = {job_id, task_id, assignment: {slot_id: word}, parent_task_id, depth}
worker -> coordinator: lease_task, report {task_id, result: solved|exhausted|split, subtasks[]}
coordinator -> workers: stop {job_id}

1. Data model

jobs   (job_id, status, grid_ref, dictionary_id, time_limit_s, solution_json,
        created_at, finished_at, nodes_explored)
tasks  (job_id, task_id, assignment_json, status: queued|leased|done,
        worker_id, lease_expires_at, attempt)
solved flag: Redis key job:{job_id}:solved  (plus pub/sub channel job:{job_id}:stop)
dictionary index: files per dictionary_id, loaded into worker memory

The job is complete, and unsolvable, only when every task is done with no solution. Tracking outstanding tasks per job makes that check exact.

1. High-level design

5.1 One machine, brute force

Enumerate assignments in order. It never finishes.

5.2 Fix 1: backtracking with propagation on one machine

Depth-first search, most constrained slot first, forward checking after each placement, and bitset candidate filtering. Easy grids finish in seconds. Hard grids still take hours.

5.3 Fix 2: split the tree into tasks

Choose the first slot with the most constrained rule, and create one task per candidate word: each is a subtree. If that gives too few tasks for the pool, expand one more level. Put tasks in a queue; workers lease them and run DFS below them.

flowchart LR
  CO[Coordinator]:::svc -->|seed tasks: top of tree| TQ[[Task queue]]:::new
  TQ --> W1[Worker 1: DFS]:::svc
  TQ --> W2[Worker 2: DFS]:::svc
  TQ --> W3[Worker N: DFS]:::svc
  W1 -->|solved / exhausted / split| CO
  classDef svc fill:#f4f1e8,stroke:#315e55,color:#171717;
  classDef new fill:#ffffff,stroke:#c4492d,stroke-width:2px,stroke-dasharray:5 3,color:#171717;

5.4 Fix 3: dynamic splitting and work stealing

Static tasks are unequal. When the queue runs low, busy workers split their remaining frontier and push part of it back. Idle workers can also ask a busy worker directly for part of its work.

5.5 Fix 4: early termination

The first worker to find a solution writes it, sets the solved flag, and publishes a stop message. Others check the flag every few thousand nodes and stop.

5.6 The composed design

sequenceDiagram
  autonumber
  actor C as Client
  participant CO as Coordinator
  participant Q as Task queue
  participant W as Workers
  participant R as Redis flag
  C->>CO: submit grid
  CO->>CO: propagate, choose first slots, seed ~10x workers tasks
  CO->>Q: tasks
  loop until solved or all tasks exhausted
    W->>Q: lease task
    W->>W: DFS below task, check flag every 4k nodes
    alt queue low
      W->>Q: push half of own frontier
    end
    W->>CO: exhausted or split
  end
  W->>R: solved (first writer wins)
  W->>CO: solution
  CO->>W: stop job (pub/sub)
  CO-->>C: solution

Key idea. Propagate on each worker, seed many tasks, rebalance by splitting and stealing, and stop everyone on the first success.

1. Deep dives

6.1 Proving one machine is too slow

Before reading on. Give the interviewer a two-minute estimate that shows a distributed design is needed.

Use round numbers. Suppose each slot has on average 10,000 candidates before crossings are known. Propagation shrinks later slots sharply, so assume the effective branching factor falls to about 1.3 per level after the first few levels. The top levels still branch by thousands. Even 10,000 × 1,000 × 100 × 1.3^90 is over 10^19 nodes in the worst case. Real hard grids land far below that thanks to pruning, but in the billions. At a million nodes per second, a billion nodes is about 17 minutes, and ten billion is about 3 hours. That is enough to justify parallelism; do not spend more time on it.

6.2 Fast candidate filtering

For each word length L, keep a bitset for each (position, letter): bit i is set if word i of length L has that letter at that position. The candidates for a slot of length 7 with pattern A _ _ L E _ _ are the AND of three bitsets: A at position 0, L at position 3, and E at position 4. Counting set bits gives the candidate count for choosing the most constrained slot. These operations run on machine words, 64 bits at a time.

Track used words with one more bitset to prevent repeats.

6.3 Splitting the work

Before reading on. You have 200 workers. How many tasks do you create at the start, and how?

Seed about 10 times the worker count, around 2,000 tasks, so that finished tasks leave room to rebalance. The coordinator runs the search to a shallow depth: choose the most constrained slot, branch on its candidates, propagate, and continue breadth-first until the frontier has at least 2,000 nodes. Each frontier node becomes a task.

Order the queue sensibly: tasks whose remaining slots have more candidates are more likely to contain a solution. Some systems also randomize the order, which helps when solutions are clustered in a few subtrees.

6.4 Load balancing

Subtrees differ by orders of magnitude. With static tasks, most workers finish early and wait while a few grind through huge subtrees.

Two dynamic mechanisms fix it.

Splitting on demand. A worker's DFS stack holds its unexplored siblings at each level. When the global queue drops below a threshold, a busy worker takes the unexplored siblings nearest the root, which are the largest remaining subtrees, and pushes them back as new tasks.

Stealing. An idle worker asks a random busy worker for work; the busy worker gives away half of its shallowest unexplored siblings. Randomized stealing balances load well in theory and practice.

Either way, a task is a partial assignment, so moving work costs a few hundred bytes.

6.5 Early termination

A solved flag in Redis per job, written with set-if-not-exists so only the first solution counts. The finder also publishes a stop message on a channel per job. Workers check the flag every few thousand nodes, a microsecond cost, as a backstop for a missed message. The coordinator marks the job solved and drops its remaining tasks.

6.6 Failures and completeness

Tasks are leased with a timeout and a heartbeat. If a worker dies, its lease expires and the task returns to the queue. Duplicate work after a lease expiry is harmless, because search has no side effects; if two workers solve the same subtree, the first write wins.

Completeness requires exact bookkeeping. A task is marked done only when its worker reports it exhausted or when all tasks it split off are accounted for. A split creates child tasks and marks the parent's remaining work as given away, in one step. The job is unsolvable only when the count of outstanding tasks reaches zero with no solution.

Long tasks can report checkpoints: the current path. A retried task then resumes near where the dead worker stopped instead of repeating hours of search.

6.7 Multiple puzzles

Many jobs share the worker pool. Schedule tasks fairly across jobs, and give each job a maximum share of workers, so one huge puzzle cannot starve short ones. Enforce each job's time limit: when it passes, the coordinator stops the job and reports "timed out."

6.8 The worker's search, in code

Before reading on. Write the core of the depth-first search, including where the worker checks the stop flag and how it hands work away.

def solve(assignment, domains, stop, stats, give_away):
    # assignment: slot -> word; domains: slot -> bitset of remaining candidates
    if all(slot in assignment for slot in domains):
        return assignment
    stats.nodes += 1
    if stats.nodes % 4096 == 0 and stop.is_set():
        raise Stopped()

    slot = min((s for s in domains if s not in assignment),
               key=lambda s: popcount(domains[s]))          # most constrained first
    for word in candidates(domains[slot]):
        new_domains = forward_check(domains, slot, word)    # None if any crossing is empty
        if new_domains is None:
            continue
        if give_away.requested():                           # another worker is idle
            give_away.push(remaining_siblings(slot, word))  # hand off untried words at this level
        result = solve({**assignment, slot: word}, new_domains, stop, stats, give_away)
        if result:
            return result
    return None

Point out three things: the stop check is cheap and periodic; forward_check returns early on any empty domain; and work is given away at the shallowest level where the worker notices a request, since the untried siblings there are the biggest subtrees available. A real implementation copies bitsets on write and undoes changes on backtrack instead of copying dictionaries, which keeps memory flat.

6.9 Knowing when a grid is too hard

Some grids have no solution, and some would take days. Give every job a time limit and a node budget. Report progress honestly: nodes explored, the deepest point reached, and tasks outstanding. When the limit hits, return "timed out" with those numbers, which helps the user decide whether to loosen the grid or the dictionary.

A good estimate of remaining work helps: sample random paths down the tree and estimate its size from the branching seen, a technique known as Knuth's estimator. It is rough, and it is better than nothing when a user asks whether to wait.

1. Variants

7.1 Randomized local search

Fill the grid with random candidates and repair conflicts step by step, as in simulated annealing or min-conflicts search. It can be fast on large, loose grids and cannot prove that no solution exists. It parallelizes trivially: run many independent searches with different seeds. The job system stays the same.

7.2 Finding all solutions

Remove early termination and collect solutions. Completeness bookkeeping matters even more, and output can be huge; stream it.

7.3 A SAT solver

Encode slots and crossings as boolean constraints and use a SAT solver. Portfolio solvers run several strategies in parallel and stop when one succeeds, which is the same distributed pattern at a higher level.

7.4 At ten times the puzzles

With many concurrent puzzles, the pool becomes a shared scheduler problem. Give each job a share of workers, prioritize short jobs so they finish quickly, and cap any single job at a fraction of the pool. The dictionary index is shared read-only memory across all jobs on a worker.

1. The transferable pattern

This is distributed tree search with dynamic load balancing. The same pattern solves scheduling problems, theorem proving, game-tree search, and hyperparameter searches with early stopping: seed many small tasks, split or steal when workers idle, keep side effects out of the search so retries are free, and account exactly for outstanding work so "not found" is trustworthy.

Review: the 30-second answer

• Show one machine fails. Billions of nodes after pruning; hours on one core.
• Smart DFS per worker. Most constrained slot first, forward checking, bitset filters.
• Seed about ten tasks per worker. Shallow frontier nodes as partial assignments.
• Split the largest remaining subtrees or steal on demand. Keep every worker busy.
• Stop fast; account exactly. Solved flag plus pub/sub; unsolvable only when outstanding tasks reach zero.

Quiz

Sources and further reading

• Scheduling Multithreaded Computations by Work Stealing analyzes randomized work stealing.
• Constraint satisfaction problem covers backtracking, forward checking, and variable ordering.
• Min-conflicts algorithm describes the local-search alternative.
• Leased tasks in a queue are the same pattern as multi-tenant CI/CD, without its exactly-once pressure.