Openai·Software Engineer·Onsite - System Design / Architecture·Senior

SeniorPrefer not to say

Jun 2026

Summary

System design round at OpenAI for a software engineer role. The question was a full deep-dive into crossword puzzle solving, which sounds like a fun toy problem until you're 20 minutes in and they're asking about constraint propagation and worst-case complexity.

Questions Asked (1)

Design a system that solves a crossword puzzle. Given a 2D board, a list of slots with positions and directions, and a word dictionary, return a completed board or confirm no solution exists. Walk through brute-force backtracking up to optimized approaches, and analyze worst-case complexity.

Algorithms & Data StructuresSystem DesignTechnical Trade-offs

Author's notes

I started with the naive thing, try every word in every slot, and they let me run with it for a bit before nudging toward optimization.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by modeling the problem as a constraint satisfaction problem (CSP) with variables as slots and domains as dictionary words of matching length. Present a brute-force backtracking solution, then optimize with constraint propagation (forward checking, arc consistency) and heuristics like MRV and least-constraining value. Analyze worst-case complexity as exponential in the number of slots, but discuss how pruning and indexing reduce practical runtime.

Pro tip: Emphasize the trade-off between precomputation (e.g., indexing words by length and letter patterns) and runtime search efficiency, and mention that real crossword solvers often use additional heuristics like frequency-based word ordering to find solutions faster.

1. Clarify requirements and constraints

Ask about board size, dictionary size, whether all slots must be filled, and if multiple solutions are acceptable. Confirm that slots are fixed and words must fit exactly.

2. Model as a CSP and design brute-force backtracking

Define variables (slots), domains (words of correct length), and constraints (intersecting letters must match). Describe a recursive backtracking algorithm that assigns words to slots one by one, checking consistency with already assigned intersecting slots.

3. Optimize with constraint propagation and heuristics

Introduce forward checking: after assigning a word, prune domains of intersecting slots. Use MRV (minimum remaining values) to choose the next slot, and least-constraining value to order word choices. Optionally, apply arc consistency (AC-3) for stronger pruning.

4. Analyze complexity and discuss trade-offs

Worst-case time is O(d^s * s * L) where d is dictionary size, s is number of slots, and L is average word length, but pruning reduces it. Space is O(s * d) for domains. Discuss indexing (e.g., by length and letter positions) to speed up domain filtering.

5. Summarize and test with examples

Walk through a small example to illustrate the algorithm. Mention edge cases: unsolvable puzzles, slots with no matching words, and performance on large boards. Conclude with when to use brute-force vs optimized.

Key Points to Mention

Constraint Satisfaction Problem (CSP) formulation: variables, domains, constraints
Backtracking search with forward checking and arc consistency
Heuristics: Minimum Remaining Values (MRV) and Least Constraining Value (LCV)
Worst-case exponential complexity and how pruning improves practical performance
Data structures: trie or hash map for dictionary lookup, indexing by length and letter patterns
Trade-offs between precomputation, memory usage, and runtime efficiency

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.