Katkat
Back

Design a distributed crossword fill solver

OpenAISoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenSystem Design

Last updated

This problem tests your ability to design a scalable, distributed architecture capable of solving large-scale constraint satisfaction problems (crossword filling) across a vast vocabulary.

Problem Statement

Design a distributed system that takes a grid of size N x N (with some cells pre-filled) and a large dictionary of words, and finds a valid configuration that completes the crossword. The system must handle high-latency dictionary lookups and massive search space exploration.

Functional Requirements

  • The system must accept a grid layout and a dictionary (set of valid words).
  • It must return a valid completion or indicate that no solution exists.
  • The system should parallelize the search process across multiple nodes.

Non-Functional Requirements

  • Fault tolerance: If a worker node dies during a search branch, that branch should be rescheduled.
  • Scalability: The system should be able to handle grids up to 20x20 and dictionaries with over 500,000 words.
  • Performance: Minimize time-to-solution, especially when the search space is highly constrained.

Key Considerations

  • Describe the API for submitting a puzzle and retrieving results.
  • Explain how you partition the search space (e.g., pruning, work-stealing, or back-tracking strategies).
  • Define how the grid state is shared or synchronized among distributed workers.
  • Address how the dictionary should be stored and queried (e.g., Trie, distributed cache, or bloom filters).

Hints

Hint 1

Consider modeling the crossword as a constraint satisfaction problem where each slot is a variable and words are potential values.

Hint 2

Think about using a centralized coordination service (like a task queue or message broker) to prevent redundant work between workers.

Hint 3

How can you implement an 'early pruning' strategy to stop searching dead-end branches before they propagate through the entire distributed cluster?

Follow-up questions

  • How would you handle the 'hot word' problem if thousands of branches frequently request the same common words from the dictionary?
  • What strategies would you use to ensure that the system does not spend excessive time on a grid that is mathematically impossible to solve?
  • If the dictionary is too large to fit in the RAM of a single node, how would you distribute the dictionary storage?