Katkat
Back

Design a Distributed Crossword Solver

OpenAISoftware Engineer · Onsite
HardSoftware EngineerOnsiteSystem Design

Last updated

This problem tests your ability to design a distributed system capable of solving large-scale constraint satisfaction problems (crossword puzzles) by partitioning search spaces and managing state across workers.

System Design: Distributed Crossword Solver

Design a system that takes a grid (with blocked and open cells) and a set of words, and produces a valid filled crossword puzzle. The system must handle grids up to 100x100 and word dictionaries containing over 500,000 entries.

Functional Requirements

  1. Accept a grid layout and a lexicon of words.
  2. Return a completed, valid crossword puzzle if one exists.
  3. Scale the search process across a cluster of nodes.

Non-Functional Requirements

  1. High throughput for solving complex grids.
  2. Fault tolerance: If a node dies, its work must be resumed by another.
  3. Search progress monitoring: Be able to report how much of the state space has been explored.

Constraints

  • The word list is static and can be pre-indexed.
  • The search space is exponential, requiring efficient pruning (e.g., maintaining word constraints).

Please provide:

  1. A high-level architecture diagram (text-based).
  2. A strategy for partitioning the search tree across multiple workers without excessive communication overhead.
  3. A mechanism for load balancing and handling worker failure.
  4. API definitions for the task submission and worker interaction.

Hints

Hint 1

Consider representing the crossword grid as a constraint graph where each word slot is a node and intersections are constraints.

Hint 2

Think about how to use a master-worker pattern with a global work queue versus a distributed hash table for state management.

Hint 3

Address the issue of 'dead-end' branches in a DFS search by implementing a mechanism for workers to report back or request new sub-problems when their branch is exhausted.

Follow-up questions

  • How would you optimize the system if the dictionary is too large to fit in the memory of a single worker node?
  • What specific heuristic would you implement to choose the next word to place in order to maximize pruning efficiency?
  • How would you handle the case where the problem has multiple valid solutions and you need the one with the highest 'lexical complexity' score?