Bird
Raised Fist0

State Pattern - Modeling Finite State Machines in ATM, Elevator, Vending Machine

LLDeasyInterview freq: medium
Choose your preparation mode4 modes available
ArchitectureTraceChallenge
🎯
State Pattern - Modeling Finite State Machines in ATM, Elevator, Vending Machine
40 min · medium
medium

Design a system that models a finite state machine (FSM) for an ATM, Elevator, or Vending Machine using the State pattern in Java. The system must support multiple states with distinct behaviors and allow safe concurrent state transitions.

Given Info
  • The system has 5 distinct states representing different operational modes.
  • State transitions depend on user actions or internal events.
  • Each state encapsulates its own behavior and can trigger transitions.
  • The context class maintains a reference to the current state and delegates behavior.
  • State transitions must be thread-safe to prevent inconsistent state.
  • The design should allow adding new states without modifying existing code (Open-Closed Principle).
📋
Guided Steps
1/5
Step 1
Define the State interface and Context class
Design a State interface that declares state-specific behaviors and a Context class that holds a reference to the current State. How do you ensure the Context delegates behavior correctly?
💡 Hint
Use a Java interface for State to declare behavior methods. Context holds a volatile State reference to ensure visibility across threads.
Key Decision
State as a Java interface with behavior methods; Context holds volatile State currentState to guarantee visibility of state changes across threads.
Interviewer Expectation
Mid: Names State pattern and interface usage. Senior: Explains volatile ensures happens-before relationship so threads see latest state reference.
⚠️Common Wrong Answer
Using a concrete class for State with mutable fields leads to shared mutable state bugs; not using volatile in Context causes stale reads of currentState in multithreaded scenarios.
Step 2
Implement concrete State classes encapsulating behavior
Implement concrete State classes for each FSM state. How do you encapsulate state-specific behavior and transitions?
💡 Hint
Use classes implementing State interface. Each class holds no mutable shared state and calls Context.setState() to transition.
Key Decision
Concrete State classes implement State interface; no instance fields holding mutable shared state; transitions invoke Context.setState() synchronized method.
Interviewer Expectation
Mid: Recognizes State pattern encapsulates behavior. Senior: Explains why concrete states avoid mutable shared fields to prevent concurrency bugs.
⚠️Common Wrong Answer
Storing mutable shared fields in State classes causes race conditions; transitions done without synchronization cause lost updates.
Step 3
Ensure thread-safe state transitions in Context
How do you implement thread-safe state transitions in the Context class to avoid race conditions when multiple threads trigger transitions?
💡 Hint
Use synchronized method setState(State newState) to atomically update currentState and ensure visibility.
Key Decision
Context.setState(State newState) declared synchronized to atomically update volatile currentState, preventing race conditions during transitions.
Interviewer Expectation
Mid: Names synchronized for atomicity. Senior: Traces thread interleaving where without synchronized, two threads read same state and both transition causing inconsistent state.
⚠️Common Wrong Answer
Not synchronizing setState leads to race conditions where multiple threads overwrite currentState causing invalid FSM behavior.
Step 4
Design extensibility for adding new states
How does your design allow adding new states without modifying existing classes, adhering to the Open-Closed Principle?
💡 Hint
Use interface State and Context referencing State interface; new states implement State without changing Context code.
Key Decision
State interface abstraction enables adding new concrete State classes without modifying Context, enforcing Open-Closed Principle in Java.
Interviewer Expectation
Mid: Identifies Open-Closed Principle. Senior: Explains how interface polymorphism in Java enables extension without modification.
⚠️Common Wrong Answer
Using enum with switch-case in Context for states forces modification of Context for new states, violating Open-Closed Principle.
Step 5
Handle state-specific data safely
If states need to hold state-specific data, how do you design to avoid concurrency issues?
💡 Hint
Use immutable fields or synchronize access within State classes; avoid sharing mutable state across threads.
Key Decision
Concrete State classes hold immutable final fields or synchronize mutable data access; no shared mutable static fields to prevent race conditions.
Interviewer Expectation
Mid: Recognizes need for thread safety in state data. Senior: Explains how final fields guarantee safe publication; synchronized blocks protect mutable data.
⚠️Common Wrong Answer
Mutable shared fields in State classes without synchronization cause data races and inconsistent behavior.
🔌
API Design Challenge
Design the API for the Context and State interfaces to support extensible, thread-safe state transitions and behavior delegation in Java.
Hints
  • Define a State interface with behavior methods representing actions in each state.
  • Context class should hold a volatile State reference and provide synchronized methods for state transitions.
  • Ensure the API allows adding new State implementations without modifying existing Context code.
📊
Scoring Rubric
▼ Show
Must Have - 60%
  • State interface with behavior methods, no instance fields
  • Context holds volatile State currentState for visibility
  • synchronized setState(State newState) for atomic transitions
  • Concrete State classes implement State interface
  • Design supports Open-Closed Principle via interface polymorphism
Good to Have - 30%
  • Immutable fields in State classes for thread safety
  • Avoid enum with switch-case for states
  • Context delegates behavior to State instances
  • Explicit state transition methods in Context
  • Explanation of Java memory model guarantees with volatile and synchronized
Bonus - 10%
  • Use of java.util.concurrent.atomic.AtomicReference for state
  • Demonstration of thread interleaving scenarios causing race conditions
  • Unit tests verifying thread-safe transitions
  • Use of abstract class for shared State behavior if needed
Anti-patterns to Avoid
Using enum with switch-case in Context for states → forces modifying Context for new states, violating Open-Closed Principle.
Not declaring currentState volatile → threads may see stale state causing inconsistent behavior.
Not synchronizing setState → race conditions where multiple threads overwrite state causing invalid FSM behavior.
Mutable shared fields in State classes without synchronization → data races and inconsistent state.
Using concrete State classes with mutable static fields → leads to shared mutable state bugs and concurrency issues.
✅
Model Answer
▼ Reveal

This design models a finite state machine using the State pattern in Java, ensuring thread-safe state transitions and extensibility. The Context class holds a volatile reference to the current State, delegating behavior to it. Concrete State classes implement the State interface, encapsulating state-specific behavior and triggering transitions via synchronized methods in Context. The design adheres to the Open-Closed Principle by allowing new states to be added without modifying existing code.

Key Decisions
  • Use of Java interface for State to enable polymorphism and extensibility.
  • Context holds volatile State currentState to ensure visibility of state changes across threads.
  • Context.setState(State newState) is synchronized to atomically update currentState and prevent race conditions.
  • Concrete State classes avoid mutable shared fields to prevent concurrency bugs.
  • Design follows Open-Closed Principle by allowing new State implementations without modifying Context.
  • Avoid enum with switch-case in Context to prevent violating Open-Closed Principle.
  • Use of volatile and synchronized ensures happens-before relationships and atomicity in Java concurrency.
  • State interface declares behavior methods; interface cannot hold instance state in Java, enabling polymorphism.
  • Context class holds volatile State currentState to ensure visibility of state changes across threads.
  • Context.setState(State newState) is synchronized to atomically update currentState and prevent race conditions.
  • Concrete State classes implement State interface, encapsulating behavior and triggering transitions via Context.
  • Avoid mutable shared state in State classes; use immutable fields or synchronize access to mutable data.
  • Design follows Open-Closed Principle by allowing new State implementations without modifying Context.
  • Use of volatile and synchronized ensures happens-before relationships and atomicity in Java concurrency.
  • No use of enum with switch-case for states to avoid violating Open-Closed Principle.
  • Context delegates all behavior to current State instance, adhering to Single Responsibility Principle.
  • State transitions are explicit method calls on Context, avoiding hidden side effects.

Practice

(1/5)
1. In the Workflow Engine, if the Executor class's executeStep() method is not synchronized, which exact thread interleaving causes two threads to execute the same step concurrently, leading to inconsistent state?
medium
A. Thread 1 finishes executeStep() before Thread 2 starts, so no concurrency issue occurs.
B. Thread 1 and Thread 2 both call executeStep() simultaneously and both complete without interference.
C. Thread 1 checks if step is not running -> true, context switch; Thread 2 checks same -> true; both proceed to execute concurrently.
D. Thread 1 locks the step, but Thread 2 waits indefinitely causing deadlock.

Solution

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

    Without synchronization, Thread 1 checks step status as free, then context switches before marking running.

  2. Step 2: Thread 2 repeats check before Thread 1 marks running

    Thread 2 also sees step free and proceeds, causing both to execute concurrently.

  3. Final Answer:

    Option C -> Option C

  4. Quick Check:

    Unsynchronized check-then-act -> double execution race [check]
Hint: Check-then-act without sync -> race condition [check]
Common Mistakes:
2. In the auction system, the placeBid() method checks if the auction is still open before accepting a bid. Without synchronizing placeBid(), which exact thread interleaving causes two threads to accept bids after the auction closes, resulting in inconsistent state?
medium
A. Thread 1 reads auction open -> false; Thread 2 reads auction open -> true; both reject bids.
B. Thread 1 and Thread 2 both wait on a lock; no bids accepted until lock released.
C. Thread 1 writes bid; Thread 2 reads bid; no race condition occurs because writes are atomic.
D. Thread 1 reads auction open -> true; context switch before bid recorded; Thread 2 reads auction open -> true; both record bids after auction closed.

Solution

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

    Without synchronization, Thread 1 reads auction open as true but is preempted before recording the bid.

  2. Step 2: Thread 2 reads auction open as true and proceeds to record bid as well, both bypassing the closed state check.

  3. Final Answer:

    Option D -> Option D

  4. Quick Check:

    Unsynchronized check-then-act -> double acceptance after close [check]
Hint: Check-then-act without sync -> race condition double accept [check]
Common Mistakes:
3. The system needs to support ElectricCar and ChargingSpot without modifying existing classes. What is the minimum change to the current Java design to add these features while preserving extensibility?
hard
A. Add ELECTRIC_CAR to VehicleType enum, CHARGING to SpotType enum, create ElectricCar subclass, and update SpotCompatibility.COMPATIBILITY_MAP accordingly.
B. Modify Vehicle class to include a boolean isElectric field and add charging logic inside existing ParkingSpot class.
C. Create a new ElectricCarChargingManager class that extends BookingManager and handles charging spots separately.
D. Add a new interface Chargeable and modify all Vehicle subclasses to implement it, including ElectricCar.

Solution

  1. Step 1: Identify extensibility without modifying existing classes

    Adding new enums or modifying compatibility maps changes existing classes, violating OCP.

  2. Step 2: Use composition by adding an isElectric field and charging logic in ParkingSpot to handle charging without class explosion.

    This approach extends functionality with minimal changes and avoids class explosion or god classes.

  3. Final Answer:

    Option B -> Option B

  4. Quick Check:

    Use fields and composition, avoid modifying enums or compatibility maps [check]
Hint: Add fields and logic, avoid modifying enums or compatibility maps [check]
Common Mistakes:
4. ElectricCar requires ChargingSpots in the Amazon Locker Service design. What is the minimum change 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 map externally.
B. Modify Vehicle and Spot classes to add electric-specific fields and methods for charging compatibility.
C. Create a new ElectricCarChargingManager class that extends LockerManager and handles charging spots separately.
D. Add a boolean isElectric field to Vehicle and Spot classes and update existing logic to handle charging.

Solution

  1. Step 1: Identify extensibility without modifying existing classes

    Enums VehicleType and SpotType can be extended with new constants without changing existing class logic. Creating ElectricCar subclass extends Vehicle cleanly.

  2. Step 2: Update SpotCompatibility map externally

    Maintaining compatibility mapping outside existing classes avoids modifying them, preserving OCP and avoiding class explosion.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Extend enums + subclass + external compatibility map -> minimal change [check]
Hint: Extend enums + subclass + external map -> no existing class change [check]
Common Mistakes:
5. ElectricCar requires ChargingSpots in the parking lot system. What is the minimum change to support this without modifying existing classes?
hard
A. Add charging logic inside existing Spot class with conditional checks for electric vehicles.
B. Modify Vehicle class to include a boolean isElectric field and add charging logic inside existing methods.
C. Add ELECTRIC_CAR to VehicleType enum, CHARGING to SpotType enum, create ElectricCar subclass, and update SpotCompatibility map.
D. Create a new ChargingSpot class extending Spot and modify ParkingLot to handle it explicitly.

Solution

  1. Step 1: Identify extensibility requirements

    Supporting ElectricCar and ChargingSpots requires new types without changing existing class logic to respect OCP.

  2. Step 2: Apply minimal change approach

    Adding new enum values and subclass ElectricCar allows extension without modifying existing classes. Updating SpotCompatibility map centralizes compatibility logic.

  3. Step 3: Eliminate options violating OCP

    Options B, C, and D modify existing classes or add conditional logic, violating OCP and risking class explosion or god classes.

  4. Final Answer:

    Option C -> Option C

  5. Quick Check:

    New enums + subclass + compatibility map update -> minimal, OCP-compliant [check]
Hint: Add enums + subclass + compatibility map, no existing class changes [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