04QuestionsCrossword puzzle solver

04 · Worked prompt

Crossword puzzle solver

Design a distributed constraint solver with bounded search, indexed candidates, parallel tasks, checkpoint recovery, and exactly one terminal result.

45 minInterview blueprint

INTERVIEW RUBRIC

What a passing answer must show

100 points · 45 minutes

20pts
Scope the problem
0–5 min
Prioritize the core flows, state the scale, and name the non-goals.
15pts
Define contracts
5–10 min
Identify durable entities, APIs, idempotency, and the source of truth.
30pts
Complete the diagram
10–25 min
Trace one write path and one read path. Label the commit boundary and async work.
20pts
Lead one deep dive
25–38 min
Choose the highest-risk trade-off and explain the mechanism, alternative, and cost.
15pts
Prove reliability
38–45 min
Walk a failure, recovery, metric, bottleneck, and evolution path.

DRAW THIS FIRST

One complete box-and-arrow design

Design a distributed constraint solver with bounded search, indexed candidates, parallel tasks, checkpoint recovery, and exactly one terminal result.

Crossword puzzle solver system architecture. Persist one bounded solve job, explore unique search branches in parallel, and atomically accept the first valid result. Request path: Solve client to Solve API to Scheduler to Metadata DB. Asynchronous path: Priority task queue to Solver worker fleet. Read path: Job/result API to Checkpoint/result blobs. External dependency: Dictionary index. — Crossword puzzle solver · system architecture

DEFEND THE DIAGRAM

Explain every boundary before adding more boxes.

Persist one bounded solve job, explore unique search branches in parallel, and atomically accept the first valid result.

INTERVIEW CONTRACT

Design a distributed constraint solver with bounded search, indexed candidates, parallel tasks, checkpoint recovery, and exactly one terminal result.

CAPACITY QUESTIONS TO QUANTIFY

50×50 grid · about 100 slots · 1M-word dictionary · p95 under 5 minutes · hard cap 10 minutes. State average and peak load, stored bytes, bandwidth or open connections, and the growth horizon before choosing a partitioning strategy.

End-to-end walkthrough

Trace the architecture in this order.

01
Enter and classify the request
Solve client → Solve API
Template, dictionary, deadline enters over HTTPS / RPC. Solve API handles identity, admission, routing, and request context; it deliberately does not own domain truth.
02
Validate, then cross the commit boundary
Solve API → Scheduler → Metadata DB
Scheduler receives the CreateSolveJob, checks invariants and retry identity, then uses job + root task txn to update Metadata DB. The user-visible mutation is accepted only after this boundary succeeds.
03
Move replayable work off the request path
Scheduler → Priority task queue → Solver worker fleet → Checkpoint/result blobs
Scheduler emits enqueue task_id; Solver worker fleet uses lease task and checkpoint / result to build Checkpoint/result blobs. Consumers must tolerate duplicate delivery and stale retries because this path is asynchronous.
04
Serve reads from the right authority
Solve API → Job/result API → Checkpoint/result blobs / Metadata DB
Job/result API uses status / result for the common, read-optimized path and job state when correctness or repair requires authoritative state. The API must state the freshness promise instead of hiding it.
05
Contain the dependency boundary
Solver worker fleet → Dictionary index
candidate bitset AND crosses into Dictionary index. Treat timeouts as ambiguous, use a deadline and idempotent retry or reconciliation, and keep the core state recoverable when the dependency is unavailable.

Ownership ledger

Why each box exists—and what it must defend.

Component	Owns	Why it exists	Interviewer probe
Solve APIAuth + idempotency	Identity, admission, routing	Protects the system edge and attaches trusted context before domain work begins.	Timeout budgets, quotas, regional routing
SchedulerCreate root + split tasks	Write invariants and retry identity	Serializes or conditionally applies state changes before acknowledging success.	Concurrent writes, deduplication, hot ownership
Metadata DBJobs, tasks, leases, result	Authoritative durable state	Provides the one record used to resolve disputes, recover, and rebuild projections.	Partition key, replication, consistency
Priority task queueSearch branch task IDs	Durable asynchronous handoff	Absorbs bursts and lets slow or optional work retry independently of the request.	Ordering key, lag, retention, dead letters
Solver worker fleetMRV DFS + checkpoints	Replayable processing	Runs expensive, fan-out, or side-effecting work with leases and bounded retries.	Idempotency, poison work, autoscaling
Checkpoint/result blobsFrontier + assignment payload	Rebuildable query state	Shapes data for the dominant reads without weakening the write-side invariant.	Freshness, versioning, rebuild time
Job/result APIStatus + terminal payload	Read composition and freshness policy	Chooses authoritative or derived state and returns a stable client contract.	Fan-out, cache policy, partial results
Dictionary indexLength/position bitsets	External capability, not local truth	Keeps a specialized or third-party concern behind a replaceable contract.	Ambiguous timeout, circuit breaking, fallback

Physical design

Name the database, shard key, indexes, and guarantees.

Database + storage: PostgreSQL stores jobs, tasks, leases, job-scoped seen-state hashes, and the one terminal result; S3 stores puzzle/checkpoint/result blobs; an in-memory dictionary service stores positional bitsets.
Partitioning / sharding: Hash jobs and task metadata by job_id; partition the task queue by priority/resource class. State dedup uses (job_id, state_key), so identical branches in different jobs do not collide.
Indexes: Unique idempotency_key, unique (job_id, state_key), due leases by (status, lease_until), tasks by job/status, and exactly one Result row keyed by job_id.
Replication + consistency: Job/task/result transitions synchronously replicate across zones. Workers execute at least once; a conditional Result insert gives one accepted solution and fences late attempts.
Cache, queue + recovery: Queue task IDs, not the only state copy. Checkpoint assignments/frontiers to blobs, lease with fencing tokens, and query candidates via bitset intersections.
Capacity math: Assume a 50×50 grid, roughly 100 slots, and a one-million-word dictionary; estimate expansions/sec, bitset memory, task split threshold, checkpoint rate, p95 five minutes, and hard cap ten minutes.
Alternative rejected: A single DFS process or repeated word-list scans are acceptable prototypes, but they cannot bound tail latency, use a fleet productively, or resume after failure.

Deep-dive candidates

Pick one risk and explain the mechanism, alternative, and cost.

Bounded solve time

Pre-index (length, letter position, letter) to bitsets, choose the minimum-remaining-values slot, propagate constraints after every assignment, and check the absolute deadline every bounded number of expansions

Scanning length buckets or checking the deadline only in the scheduler leaves the hottest loop and long-running branches unbounded

Productive parallelism

Hash each canonical partial assignment into a job-scoped state key, register it conditionally, and split only when the next slot has enough candidates to justify another task

Local seen sets cannot stop two workers from exploring the same branch; fixed-depth splitting creates stragglers

Checkpoint recovery

Persist the partial assignment, next slot, candidate cursor, and optional constraint cache every time/expansion interval; requeue after the fenced lease expires

Checkpoint too often and storage dominates; checkpoint too rarely and a crash discards minutes of search

Failure pressure test

Show detection, containment, recovery, and evidence.

Worker lease expires

Fence the old attempt, requeue the task, and resume from the latest checkpoint

lease expiry count, recovered checkpoint age, and duplicate active attempts

Two workers find a solution

Insert Result(job_id) conditionally and make that row the terminal authority before cancelling remaining work

conditional-commit conflicts and cancellation propagation p99

Dictionary index unavailable

Stop admitting new tasks, retry bounded lookups, and preserve checkpoints until the index recovers

candidate lookup p99, index error rate, and paused task count

Deadline reached

Workers stop within a bounded expansion interval and one coordinator commits TIMEOUT if no result won

deadline overshoot and CPU after deadline

Before you finish, explicitly cover

Functional requirements and non-goals
Peak traffic, storage, bandwidth, and growth
Entities, APIs, idempotency, and pagination
Source of truth and consistency promise
Partition key, replicas, caches, and hot spots
Retries, backpressure, failover, and reconciliation
Latency, saturation, correctness, and recovery metrics
Security, migration, cost, and multi-region evolution

SAY THIS WHILE YOU DRAW

A four-part talk track

Scope
“I’ll prioritize find one slot-to-word assignment whose lengths and intersections are valid and return a distinct no-solution or timed-out terminal outcome.”
Scale
“The design changes around 50×50 grid · about 100 slots · 1m-word dictionary · p95 under 5 minutes · hard cap 10 minutes.”
Decision
“Use most-constrained-first DFS with positional bitset indexes, then split only high-branching states into leased tasks.”
Risk
“The first failure I want to pressure-test is: Duplicate state exploration, unbounded search, or a crashed worker can waste the entire solve budget.”

Reference details

Open these only after you can explain the diagram above without reading.

01Requirements and state lifecycle5 requirements

Find one slot-to-word assignment whose lengths and intersections are valid
Return a distinct no-solution or timed-out terminal outcome
Keep p95 completion under five minutes with a ten-minute hard cap
Keep duplicate state exploration below five percent and candidate lookup p95 below ten milliseconds
Finish or recover at least 99.9% of accepted jobs

Crossword puzzle solver · state lifecycle

state lifecycle

Each transition must be durable, observable, and safe to retry.

queued

running

succeeded

no solution

timed out

failed or cancelled

02Data model and APIs4 entities · 4 interfaces

Core entities

Puzzlepuzzle_id, grid_size, slots_ref, intersections_ref, created_atOwner: Puzzle store

SolveJobjob_id, puzzle_id, dictionary_id, deadline_at, idempotency_key, statusOwner: Metadata DB

SearchTasktask_id, job_id, state_key, state_blob_ref, status, lease_until, worker_idOwner: Metadata DB

SolveResultjob_id, outcome, assignment_blob_ref, created_atOwner: Metadata DB

External interfaces

POST /v1/solve-jobs

Create one idempotent solve job from a puzzle template, dictionary ID, and hard deadline

GET /v1/solve-jobs/{job_id}

Read queued, running, or terminal status and timestamps

GET /v1/solve-jobs/{job_id}/result

Return the assignment only after the terminal result record is readable

POST /v1/solve-jobs/{job_id}/cancel

Fence later task/result commits and release remaining work

03Deep dives and trade-offsChoose one

Bounded solve time

Scanning length buckets or checking the deadline only in the scheduler leaves the hottest loop and long-running branches unbounded

Productive parallelism

Hash each canonical partial assignment into a job-scoped state key, register it conditionally, and split only when the next slot has enough candidates to justify another task

Local seen sets cannot stop two workers from exploring the same branch; fixed-depth splitting creates stragglers

Checkpoint recovery

Persist the partial assignment, next slot, candidate cursor, and optional constraint cache every time/expansion interval; requeue after the fenced lease expires

Checkpoint too often and storage dominates; checkpoint too rarely and a crash discards minutes of search

04Failures, recovery, and evidence4 scenarios

Worker lease expires

Fence the old attempt, requeue the task, and resume from the latest checkpoint

lease expiry count, recovered checkpoint age, and duplicate active attempts

Two workers find a solution

Insert Result(job_id) conditionally and make that row the terminal authority before cancelling remaining work

conditional-commit conflicts and cancellation propagation p99

Dictionary index unavailable

Stop admitting new tasks, retry bounded lookups, and preserve checkpoints until the index recovers

candidate lookup p99, index error rate, and paused task count

Deadline reached

Workers stop within a bounded expansion interval and one coordinator commits TIMEOUT if no result won

deadline overshoot and CPU after deadline

05What makes the answer seniorInterviewer signals

State assumptions aloud: grid size, slot count, dictionary size, solvability, and deadline
The inner-loop data structure matters more than adding workers: bitset intersections beat repeated scans
Exactly one result is a conditional database invariant; execution remains at least once
Distinguish proven unsatisfiable from no solution found before the deadline
Primary trade-off: Use most-constrained-first DFS with positional bitset indexes, then split only high-branching states into leased tasks.

BEFORE THE NEXT QUESTION

Can you redraw it from memory?

Name the source of truth.
Trace the write and read paths.
Defend one trade-off.
Recover from one failure.

Scope the problem

Define contracts

Complete the diagram

Lead one deep dive

Prove reliability

Write

Propagate

Read

Trace the architecture in this order.

Enter and classify the request

Validate, then cross the commit boundary

Move replayable work off the request path

Serve reads from the right authority

Contain the dependency boundary

Why each box exists—and what it must defend.

Name the database, shard key, indexes, and guarantees.

Pick one risk and explain the mechanism, alternative, and cost.

Bounded solve time

Productive parallelism

Checkpoint recovery

Show detection, containment, recovery, and evidence.

Worker lease expires

Two workers find a solution

Dictionary index unavailable

Deadline reached

Reference details

Core entities

External interfaces

Bounded solve time

Productive parallelism

Checkpoint recovery

Worker lease expires

Two workers find a solution

Dictionary index unavailable

Deadline reached

Can you redraw it from memory?