Bird
Raised Fist0

Jigsaw Puzzle System

LLDhardInterview freq: medium
Choose your preparation mode4 modes available
ArchitectureTraceChallenge
🏗️
Jigsaw Puzzle System
Design a modular, extensible jigsaw puzzle system with piece fitting and solver interface
hardAdvanced LLD ChallengesFreq: medium
Prerequisites:OOP FundamentalsJava ConcurrencyDesign PatternsSOLID Principles
⚙️
Functional Requirements
  • Represent puzzle pieces with shape and edge connectors
  • Maintain a board state with placed pieces and empty slots
  • Check if a piece fits correctly adjacent to existing pieces
  • Allow extensible solver implementations via interface
  • Support piece rotation and flipping
  • Ensure thread-safe piece placement and removal
  • Validate puzzle completion status
👤
Use Cases
  • User places a piece on the board
  • System checks if a piece fits adjacent to placed pieces
  • Solver attempts to solve the puzzle automatically
  • User removes a piece from the board
  • System validates puzzle completion
  • Admin configures puzzle parameters
🧑‍💻
Actors
  • User
  • PuzzleSolver
  • SystemAdmin
❓
Clarifying Questions to Ask
  • How many concurrent users or threads can place/remove pieces simultaneously?
  • Should the system support partial puzzle states or only fully empty/filled boards?
  • Is there a pricing or licensing model for puzzle solvers or pieces?
  • How to handle edge cases like overlapping pieces or invalid piece IDs?
  • Are pieces uniquely identifiable or can duplicates exist?
  • Should the solver interface support asynchronous solving or callbacks?
Out of Scope
✗ Graphical user interface
✗ Puzzle image rendering
✗ Networked multiplayer puzzle solving
🔢
Enumerations
enum EdgeType
FLAT | TAB | SLOT
Defines the shape of each puzzle piece edge. Using enum prevents typo bugs and enables exhaustive switch statements for fit logic.
enum PieceOrientation
UP | RIGHT | DOWN | LEFT
Represents the rotation state of a piece. Enum ensures type safety and clear orientation handling.
enum FitResult
FIT | NO_FIT | PARTIAL_FIT
Encapsulates the result of a fit check. Using enum avoids ambiguous boolean returns and supports extensibility.
enum SolverStatus
IDLE | RUNNING | COMPLETED | FAILED
Tracks solver lifecycle states. Enum enables clear state transitions and thread-safe status checks.
📦
PuzzlePiece
3 fields
private final int idprivate final EdgeType[] edges // length 4, order: UP, RIGHT, DOWN, LEFTprivate volatile PieceOrientation orientation
Represents a single puzzle piece with fixed edges and mutable orientation. Provides methods to rotate and query edges according to orientation.
Key Methods
public int getId()Returns the unique identifier of the piece.
public EdgeType getEdge(PieceOrientation side)Returns the edge type on the given side considering current orientation.
public synchronized void rotateClockwise()Rotates the piece orientation 90 degrees clockwise atomically.
public synchronized void setOrientation(PieceOrientation orientation)Sets the piece orientation atomically.
public PieceOrientation getOrientation()Returns the current orientation.
📦
PuzzleBoard
4 fields
private final int rowsprivate final int colsprivate final PuzzlePiece[][] gridprivate final Object lock = new Object()
Maintains the 2D grid of placed pieces. Supports thread-safe placement, removal, and retrieval of pieces.
Key Methods
public synchronized boolean placePiece(int row, int col, PuzzlePiece piece)Atomically places a piece at specified position if empty and returns success.
public synchronized PuzzlePiece removePiece(int row, int col)Atomically removes and returns the piece at position or null if empty.
public PuzzlePiece getPiece(int row, int col)Returns the piece at position without locking (immutable reference).
public boolean isPositionValid(int row, int col)Checks if the given position is within board bounds.
📦
FitChecker
0 fields
Provides logic to check if a piece fits adjacent to existing pieces on the board considering edges and orientation.
Key Methods
public FitResult checkFit(PuzzleBoard board, int row, int col, PuzzlePiece piece)Checks if the piece fits at the given position on the board.
📦
PuzzleSolver
1 fields
private volatile SolverStatus status
Defines the interface for puzzle solvers that attempt to solve the puzzle automatically.
Key Methods
public abstract void solve(PuzzleBoard board)Starts solving the puzzle on the given board.
public SolverStatus getStatus()Returns the current solver status.
📦
BacktrackingSolver
1 fields
private volatile SolverStatus status
Concrete solver implementing backtracking algorithm to solve the puzzle.
Key Methods
public synchronized void solve(PuzzleBoard board)Performs backtracking to solve the puzzle, updates status accordingly.
public SolverStatus getStatus()Returns current solver status.
🔗
Relationships
PuzzleBoard◆──►PuzzlePiece[1..*]
compositionPuzzleBoard owns PuzzlePieces placed on it; pieces can exist independently before placement
FitChecker──►PuzzleBoard[1]
associationFitChecker uses PuzzleBoard reference temporarily; no ownership
BacktrackingSolver──►PuzzleSolver[1]
inheritanceBacktrackingSolver is a subtype of PuzzleSolver
PuzzleSolver──►PuzzleBoard[1]
associationPuzzleSolver operates on PuzzleBoard passed in solve method; no ownership

Practice

(1/5)
1. A class provides a createIterator() method that returns an object allowing traversal over its elements without exposing its internal data structure. Which design pattern is being applied and why is this the correct choice?
easy
A. Factory Method pattern, because it encapsulates object creation logic.
B. Decorator pattern, because it adds traversal behavior dynamically.
C. Iterator pattern, because it separates traversal logic from the collection's internal structure.
D. Composite pattern, because it treats individual and composite objects uniformly.

Solution

  1. Step 1: Identify the role of createIterator()

    This method returns an object that allows clients to traverse elements without exposing the collection's internal representation, which is the core intent of the Iterator pattern.

  2. Step 2: Eliminate other patterns

    Factory Method focuses on object creation, Decorator adds responsibilities dynamically, and Composite manages tree structures. None focus on traversal abstraction.

  3. Final Answer:

    Option C -> Option C

  4. Quick Check:

    Iterator separates traversal from collection internals [check]
Hint: Iterator hides structure, exposes traversal [check]
Common Mistakes:
2. In a parking lot system, if parkVehicle() is not synchronized, which exact sequence of Thread 1 and Thread 2 causes double-booking of the same spot?
medium
A. Thread 1 parks vehicle, Thread 2 parks vehicle immediately after without checking availability
B. Thread 1 checks spot availability -> true, context switch; Thread 2 checks availability -> true; both park simultaneously
C. Thread 1 parks vehicle, Thread 2 waits for Thread 1 to finish, then parks another vehicle
D. Thread 1 and Thread 2 both fail to acquire lock and retry indefinitely

Solution

  1. Step 1: Identify the check-then-act race condition

    Without synchronization, Thread 1 reads spot as available, then context switches before marking it occupied.

  2. Step 2: Thread 2 also reads spot as available and proceeds to park, causing double-booking

    Both threads believe the spot is free and park concurrently, violating mutual exclusion.

  3. Final Answer:

    Option B -> Option B

  4. Quick Check:

    Check-then-act gap without synchronization -> double-booking [check]
Hint: Check availability -> context switch -> both park -> double-booking [check]
Common Mistakes:
3. The ATM system needs to support ElectricCar vehicles requiring ChargingSpot types. What is the minimum change to the current design to support this without modifying existing classes?
hard
A. Add ELECTRIC_CAR to VehicleType enum, CHARGING to SpotType enum, create ElectricCar subclass, and update SpotCompatibility.COMPATIBILITY_MAP externally.
B. Modify VehicleType and SpotType enums and add compatibility logic inside existing Vehicle and Spot classes.
C. Create new ElectricCar and ChargingSpot classes and modify existing ParkingLot to handle them explicitly.
D. Add flags in Vehicle and Spot classes to indicate electric compatibility, modifying existing classes.

Solution

  1. Step 1: Identify extensibility requirements

    New vehicle and spot types must be added without modifying existing classes to respect OCP.

  2. Step 2: Apply minimal change

    Add new enum constants ELECTRIC_CAR and CHARGING. Create ElectricCar subclass. Update compatibility map externally to include new types. No existing classes modified.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    New enums + subclass + external map update -> no existing class changes [check]
Hint: Add enums + subclass + external map update -> no existing class changes [check]
Common Mistakes:
4. To add support for ElectricCar objects requiring ChargingSpots in the existing LRU Cache design (which models Vehicle and Spot types), what is the minimum change that respects extensibility and avoids modifying existing classes?
hard
A. Modify Vehicle base class to include a boolean isElectric field and add logic in Spot class to check this field.
B. Add ELECTRIC_CAR to VehicleType enum, CHARGING to SpotType enum, create ElectricCar subclass, and update SpotCompatibility map; no existing classes modified.
C. Create a new ElectricCar class and a new ChargingSpot class, then modify the Cache class to handle these new types explicitly.
D. Add a new method in Vehicle interface for charging compatibility and implement it in ElectricCar; modify Spot class accordingly.

Solution

  1. Step 1: Identify extensibility requirements

    We want to add ElectricCar and ChargingSpot without modifying existing classes to respect OCP.

  2. Step 2: Evaluate options

    Modify Vehicle base class to include a boolean isElectric field and add logic in Spot class to check this field. modifies existing Vehicle class, violating OCP. Add ELECTRIC_CAR to VehicleType enum, CHARGING to SpotType enum, create ElectricCar subclass, and update SpotCompatibility map; no existing classes modified. adds enum values and compatibility map without changing existing classes, preserving extensibility.

  3. Step 3: Confirm minimal change

    Add ELECTRIC_CAR to VehicleType enum, CHARGING to SpotType enum, create ElectricCar subclass, and update SpotCompatibility map; no existing classes modified. adds new enum constants and new subclass, updating compatibility map externally, no existing class code changed.

  4. Final Answer:

    Option A -> Option A

  5. Quick Check:

    New enums and subclass added, existing classes untouched [check]
Hint: Add enums and subclass, avoid modifying existing classes [check]
Common Mistakes:
5. To add ElectricCar needing ChargingSpot without modifying existing classes, what is the minimum change to the current design using enums VehicleType and SpotType and a compatibility map?
hard
A. Modify Vehicle base class to include charging capability and add logic in existing spot classes
B. Create a new ElectricVehicleFactory that overrides existing factory methods and modifies compatibility map
C. Add ELECTRIC_CAR to VehicleType, CHARGING to SpotType, create ElectricCar subclass, and update compatibility map; no existing classes modified
D. Add ElectricCar as a flag inside Vehicle and modify parkVehicle() to check for charging spots

Solution

  1. Step 1: Understand current enum and compatibility map design

    VehicleType and SpotType enums define types; compatibility map links them. Adding new types requires updating enums and map.

  2. Step 2: Analyze minimal change without modifying existing classes

    Add ELECTRIC_CAR to VehicleType, CHARGING to SpotType, create ElectricCar subclass, and update compatibility map; no existing classes modified adds new enum values and classes without modifying existing classes, respecting OCP. Modify Vehicle base class to include charging capability and add logic in existing spot classes modifies base Vehicle class, violating OCP but minimal code change.

  3. Step 3: Choose minimal change that avoids modifying existing classes

    Add ELECTRIC_CAR to VehicleType, CHARGING to SpotType, create ElectricCar subclass, and update compatibility map; no existing classes modified is minimal and respects OCP; Modify Vehicle base class to include charging capability and add logic in existing spot classes modifies existing classes, violating requirement.

  4. Final Answer:

    Option A -> Option A

  5. Quick Check:

    New enums + subclass + compatibility map update -> minimal change without existing class modification [check]
Hint: Add enums + subclass + map update; no existing class edits [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