Bird
Raised Fist0

Jigsaw Puzzle System

LLDhardInterview freq: medium
Choose your preparation mode4 modes available
ArchitectureTraceChallenge
🎯
Design a Jigsaw Puzzle System
40 min · medium
medium

Design a system to represent jigsaw puzzle pieces and a puzzle board. The system must support checking if pieces fit together and provide a solver interface to solve the puzzle automatically.

Given Info
  • PuzzlePiece has shape and connectors that determine fit with neighbors.
  • PuzzleBoard holds a grid of placed PuzzlePieces with fixed dimensions.
  • FitChecker interface defines the contract to check if two pieces fit together.
  • PuzzleSolver interface defines a method to solve the puzzle given a board and pieces.
  • BacktrackingSolver implements PuzzleSolver using backtracking algorithm.
  • Concurrency must be handled when multiple threads attempt to place pieces on the board.
📋
Guided Steps
1/5
Step 1
Define PuzzlePiece with shape and connectors
Design the PuzzlePiece class to represent a single puzzle piece with connectors on each side. How do you represent the connectors and piece shape?
💡 Hint
Use enums to represent connector types and piece orientation. Use final fields for immutable state.
Key Decision
Use enum ConnectorType { MALE, FEMALE, FLAT } for connectors - enums provide compile-time safety and exhaustive switch support in Java.
Interviewer Expectation
Mid: Recognizes enum usage for connector types. Senior: Explains why enum is preferred over String to avoid runtime bugs and enable exhaustive switch.
⚠️Common Wrong Answer
Using String for connector types leads to typo bugs and no compile-time checking, causing runtime failures.
Step 2
Design PuzzleBoard to hold pieces with thread-safe placement
How do you design PuzzleBoard to hold placed pieces and allow thread-safe placement of pieces?
💡 Hint
Use a 2D array or map for piece positions. Use synchronized methods or locks to ensure atomic placement.
Key Decision
public synchronized boolean placePiece(int x, int y, PuzzlePiece piece) - synchronized ensures atomic check-and-set to prevent race conditions when multiple threads place pieces.
Interviewer Expectation
Mid: Uses synchronized method for thread safety. Senior: Explains exact thread interleaving where without synchronized, two threads can place different pieces at same position causing data corruption.
⚠️Common Wrong Answer
No synchronization leads to race conditions where multiple threads overwrite the same board position causing inconsistent puzzle state.
Step 3
Implement FitChecker interface for piece compatibility
Define the FitChecker interface and implement a class that checks if two pieces fit together based on their connectors.
💡 Hint
FitChecker should be an interface because different fit strategies may exist. Implement a class that compares connectors using enums.
Key Decision
FitChecker as interface with boolean fits(PuzzlePiece p1, PuzzlePiece p2, Direction dir) - interface used because no instance state needed; allows multiple implementations.
Interviewer Expectation
Mid: Defines interface for strategy pattern. Senior: Explains interface cannot hold state in Java, so fit logic is stateless and interchangeable.
⚠️Common Wrong Answer
Using abstract class for FitChecker unnecessarily forces inheritance and state management, reducing flexibility.
Step 4
Design PuzzleSolver interface and BacktrackingSolver implementation
How do you design the PuzzleSolver interface and implement BacktrackingSolver using the template method pattern?
💡 Hint
PuzzleSolver interface defines solve method. BacktrackingSolver extends abstract class with template method solve() calling abstract backtrack().
Key Decision
abstract class AbstractPuzzleSolver implements PuzzleSolver with final solve() method and abstract backtrack() - template method pattern uses abstract class to hold shared state and algorithm skeleton.
Interviewer Expectation
Mid: Recognizes template method pattern usage. Senior: Explains abstract class holds shared instance state (e.g. board, pieces) which interface cannot hold in Java.
⚠️Common Wrong Answer
Using interface default methods for solve() leads to duplicated state management and violates DRY principle.
Step 5
Handle concurrency in PuzzleSolver when placing pieces
How do you ensure thread safety when the solver places pieces on the board concurrently?
💡 Hint
Use synchronized methods or locks on PuzzleBoard placement. Consider volatile or AtomicBoolean flags for piece availability.
Key Decision
Use synchronized boolean placePiece(...) in PuzzleBoard and volatile boolean[] pieceUsed flags in solver - volatile ensures visibility of piece usage across threads.
Interviewer Expectation
Mid: Uses synchronized placement. Senior: Explains volatile prevents stale reads of pieceUsed flags causing duplicate piece placement in concurrent threads.
⚠️Common Wrong Answer
No volatile on pieceUsed flags causes threads to see stale values, leading to multiple placements of the same piece.
🔌
API Design Challenge
Design the API for placing pieces on the PuzzleBoard and checking if two pieces fit together, considering concurrency and extensibility.
Hints
  • Use synchronized methods or locks to ensure thread-safe placement of pieces.
  • Define FitChecker as an interface to allow multiple fit checking strategies.
  • Use enums for connector types to ensure type safety and exhaustive switch statements.
📊
Scoring Rubric
▼ Show
Must Have - 60%
  • Use enum ConnectorType for connectors to ensure compile-time safety
  • PuzzleBoard.placePiece() declared synchronized for atomic check-and-set
  • FitChecker defined as interface due to stateless behavior
  • AbstractPuzzleSolver uses abstract class for template method pattern with shared state
  • volatile boolean[] pieceUsed flags in solver to ensure visibility across threads
Good to Have - 30%
  • Immutable PuzzlePiece with final fields
  • BacktrackingSolver implements backtracking algorithm extending AbstractPuzzleSolver
  • Composition relationship between PuzzleBoard and PuzzlePiece
  • Aggregation relationship between PuzzleSolver and PuzzleBoard
  • Use of exhaustive switch on enums in fit checking
Bonus - 10%
  • Explain exact thread interleaving causing race conditions without synchronization
  • Use of AtomicBoolean instead of volatile for piece usage flags
  • Support for multiple FitChecker implementations via strategy pattern
  • Use of final methods in abstract class to enforce algorithm skeleton
Anti-patterns to Avoid
Using String for connector types leads to runtime typo bugs and no compile-time checking, causing runtime failures.
No synchronization on board placement causes race conditions and inconsistent puzzle state, corrupting puzzle integrity.
Using abstract class for FitChecker reduces flexibility and forces unnecessary inheritance, limiting strategy extensibility.
Using interface default methods for solve() duplicates state management violating DRY principle and complicates concurrency.
No volatile on pieceUsed flags causes stale reads and duplicate piece placement in concurrency, breaking puzzle correctness.
✅
Model Answer
▼ Reveal

This design models a jigsaw puzzle system with immutable PuzzlePieces using enums for connector types, a thread-safe PuzzleBoard with synchronized piece placement, a stateless FitChecker interface for flexible fit strategies, and a PuzzleSolver interface with an abstract class implementing the template method pattern for backtracking. Concurrency is handled via synchronized methods and volatile flags to ensure visibility and prevent race conditions.

Key Decisions
  • Use enum ConnectorType { MALE, FEMALE, FLAT } for connectors to ensure compile-time safety and exhaustive switch support.
  • Declare PuzzleBoard.placePiece() as synchronized to ensure atomic check-and-set operations preventing race conditions.
  • Define FitChecker as an interface to allow multiple stateless fit checking strategies and avoid forced inheritance.
  • Implement PuzzleSolver as an interface and AbstractPuzzleSolver as an abstract class with final solve() method and abstract backtrack() method to apply template method pattern and hold shared state.
  • Use volatile boolean[] pieceUsed flags in solver to ensure visibility of piece usage across threads and prevent duplicate placements.
  • PuzzlePiece uses enum ConnectorType for connectors to ensure type safety and exhaustive switch.
  • PuzzleBoard holds pieces in a 2D array with synchronized placePiece() method for atomic placement.
  • FitChecker is an interface to allow multiple fit checking strategies without state.
  • AbstractPuzzleSolver uses template method pattern with abstract backtrack() and final solve() method.
  • BacktrackingSolver extends AbstractPuzzleSolver implementing backtrack() with backtracking algorithm.
  • Use volatile boolean[] pieceUsed in solver to track piece usage visibility across threads.
  • Synchronized placePiece() prevents race conditions when multiple threads place pieces concurrently.
  • Composition relationship: PuzzleBoard composes PuzzlePieces; PuzzleSolver aggregates PuzzleBoard and pieces.
  • PuzzlePiece is immutable with final fields to prevent state corruption in concurrent environment.
  • Enums prevent runtime bugs from invalid connector types and improve IDE support.

Practice

(1/5)
1. In a parking system, should Vehicle be an abstract class or an interface if it needs to hold state like licensePlate and provide default behavior for getSize()? Why?
easy
A. Abstract class, because it can hold instance variables and provide default method implementations.
B. Abstract class, but only if it has no state to avoid violating interface segregation.
C. Interface, because state should always be in separate classes to keep interfaces clean.
D. Interface, because it allows multiple inheritance and default methods can hold state.

Solution

  1. Step 1: Analyze state and behavior requirements

    Vehicle needs to hold licensePlate (state) and provide default getSize() behavior, which interfaces cannot hold as instance variables.

  2. Step 2: Choose correct OOP construct

    Abstract classes can hold state and provide default implementations, interfaces cannot hold instance state (only constants).

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    State + default behavior -> abstract class, not interface [check]
Hint: State needs abstract class; interfaces can't hold instance variables [check]
Common Mistakes:
2. Given a Vehicle abstraction that requires both state (e.g., speed) and behavior (e.g., accelerate()), should Vehicle be an abstract class or an interface in Java, and why?
easy
A. Interface, because it allows multiple inheritance and can hold state variables.
B. Interface, because abstract classes cannot define method signatures without implementation.
C. Abstract class, because it can hold shared state and provide default behavior implementations.
D. Abstract class, because interfaces cannot have any methods related to behavior.

Solution

  1. Step 1: Analyze state and behavior requirements

    Since Vehicle needs to hold state like speed and provide default behavior like accelerate(), it requires fields and method implementations.

  2. Step 2: Choose between abstract class and interface

    Java interfaces cannot hold instance state (fields) prior to Java 8 default methods, and even then, no instance variables. Abstract classes can hold state and provide default method implementations, making them suitable here.

  3. Final Answer:

    Option C -> Option C

  4. Quick Check:

    State + default behavior -> abstract class, not interface [check]
Hint: State needs fields -> abstract class; interfaces lack instance variables [check]
Common Mistakes:
3. You want to add a WeekendFeeStrategy to calculate parking fees on weekends without modifying existing classes. Which SOLID principle guides this design and what is the minimum change?
medium
A. Add WeekendFeeStrategy implementing FeeStrategy and inject it, preserving OCP and DIP
B. Create a new subclass WeekendParkingLot duplicating most logic, violating DRY
C. Add a boolean flag in Vehicle to indicate weekend parking, violating SRP
D. Modify ParkingLot to add weekend logic directly, violating OCP but simpler

Solution

  1. Step 1: Identify applicable SOLID principles

    Open/Closed Principle (OCP) requires extending behavior without modifying existing code; Dependency Inversion Principle (DIP) requires depending on abstractions like FeeStrategy.

  2. Step 2: Apply minimal change preserving OCP and DIP

    Implement WeekendFeeStrategy as a new class implementing FeeStrategy and inject it where needed, avoiding changes to existing classes.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    New strategy class + injection -> OCP and DIP preserved [check]
Hint: New strategy class + inject -> OCP and DIP preserved [check]
Common Mistakes:
4. Facebook wants to add ElectricCar users who require ChargingSpot support in the Vehicle and ParkingSpot hierarchy. What is the minimum change to the current design to support this without modifying existing classes?
hard
A. Create a new ElectricVehicleManager class that handles electric cars separately from existing classes.
B. Modify Vehicle and ParkingSpot classes to add electric-specific fields and logic.
C. Add ELECTRIC_CAR to VehicleType enum, CHARGING to SpotType, create ElectricCar subclass, and update compatibility map externally.
D. Add boolean isElectric flag to Vehicle and ParkingSpot and handle logic with conditionals.

Solution

  1. Step 1: Identify extensibility without modifying existing classes

    Adding new enum values and subclasses extends functionality without changing existing code.

  2. Step 2: Use external compatibility map update

    Updating the compatibility map externally avoids modifying existing class logic, preserving OCP.

  3. Final Answer:

    Option C -> Option C

  4. Quick Check:

    New enums + subclass + external map update -> minimal change [check]
Hint: Add enums + subclass + external map, no existing class change [check]
Common Mistakes:
5. To add support for ElectricCar needing ChargingSpot in the current parking lot design, what is the minimum change that respects extensibility and avoids modifying existing classes?
hard
A. Modify Vehicle base class to include charging logic and add ChargingSpot as a subclass of ParkingSpot.
B. Add charging logic inside ParkingLot class and create a new ChargingSpot type without changing enums.
C. Create a new ElectricVehicle interface and modify existing classes to implement it.
D. Add ELECTRIC_CAR to VehicleType enum, CHARGING to SpotType enum, create ElectricCar subclass, and update SpotCompatibility.COMPATIBILITY_MAP accordingly.

Solution

  1. Step 1: Identify extensibility without modifying existing classes

    Enums are extended with new constants; new subclass ElectricCar is created without changing existing classes.

  2. Step 2: Update compatibility map to include new vehicle and spot types

    SpotCompatibility.COMPATIBILITY_MAP is updated to reflect which spots fit ElectricCar, preserving OCP.

  3. Final Answer:

    Option D -> Option D

  4. Quick Check:

    Extend enums + new subclass + update compatibility map -> no existing class modified [check]
Hint: Extend enums + new subclass + update map -> no existing class changed [check]
Common Mistakes:
Recommended

Ready to prove it?

Pass the test and this pattern moves unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard