Katkat
Back

Design a crossword puzzle solver system

OpenAISoftware Engineer · Technical Screen
HardSoftware EngineerTechnical ScreenSystem Design

Last updated

This problem tests the ability to design an efficient search and constraint-solving system for crossword puzzles, requiring optimized data structures for prefix lookups and a backtracking strategy to handle search space pruning.

Problem Statement

Design a crossword puzzle solver system that can fill a grid given a set of clues and a dictionary of words. The grid contains empty cells (represented by '.') and blacked-out cells (represented by '#').

Functional Requirements

  1. Given a partially filled grid and a list of word-clue pairs, fill the grid such that all words intersect correctly and conform to the grid structure.
  2. The system must support an API to receive a grid layout and a list of allowed words, returning a completed grid or an indication that no solution exists.

Non-Functional Requirements

  1. The system must handle dictionaries with up to 500,000 words.
  2. The search process should be highly optimized to prune branches early, as crossword puzzles are computationally expensive (NP-complete variations).
  3. Consider the latency constraints for a web-based user interface.

Technical Deliverables

  • Define the core data structures needed to store the dictionary (e.g., Trie, DAWG).
  • Propose an algorithmic approach (e.g., Backtracking with MRV heuristic).
  • Detail the API design and explain how you would cache or partition the data if scaling to millions of user-submitted puzzles.

Examples

Input Grid:

#.#
...
#.#

Allowed Words: ["CAT", "DOG", "TEA", "ACT"]

Expected Output: A filled grid where row/column intersections match valid words from the dictionary.

Hints

Hint 1

Consider using a Trie or a Directed Acyclic Word Graph (DAWG) to allow for prefix-based lookups during the word insertion process.

Hint 2

Implement a backtracking algorithm that uses the Minimum Remaining Values (MRV) heuristic to choose which word or cell to fill next.

Hint 3

Pre-process the grid into a list of 'slots' (sequences of empty cells bounded by black squares or grid edges) to simplify the constraint satisfaction problem.

Follow-up questions

  • How would you modify your design if the dictionary could contain phrases with spaces or hyphens?
  • If the solver takes too long on a very large grid, how would you introduce an approximation strategy or a timeout mechanism?
  • How would you handle a scenario where multiple valid solutions exist and the user wants to be able to toggle between them?