Summary of "Elevator System Design | Grokking the Object Oriented System Design Interview Question"
Summary of "Elevator System Design | Grokking the Object Oriented System Design Interview Question"
Main Ideas and Concepts
- Elevator System Design as an Interview Question:
- Similar to parking lot system design, Elevator System Design is a common object-oriented system design interview question.
- Interviewers assess:
- Requirement gathering and scoping skills.
- Object-oriented design skills (abstraction, encapsulation, inheritance, polymorphism).
- Identification and use of design patterns.
- Handling concurrency when multiple elevators are involved.
- It is not a distributed system design question; overcomplicating it can be seen negatively.
- Requirements Gathering:
- Elevator car states: Up, Down, Idle (represented using enums).
- Elevator functions:
- Transfer passengers between floors.
- Doors open only when elevator is idle.
- System scale assumptions:
- Up to 200 floors.
- Around 50 elevator cars.
- Elevator specs:
- Max passengers.
- Max load.
- Max speed.
- Optimization goals could include:
- Minimizing overall or individual passenger wait times.
- Maximizing throughput (passenger capacity).
- Minimizing power consumption and maintenance costs.
- Operational zoning:
- Dividing floors into zones served by subsets of elevators (e.g., floors 1-50 served by certain elevators).
- Zoning can be by floor ranges or odd/even floors.
- Helps simplify complex scheduling and improves efficiency.
- Extended Requirements:
- Emergency alarms and brakes.
- VIP or utility elevators.
- Monitoring systems for elevator status, doors, buttons, etc.
- Actors and Objects in the System:
- Actors: Passengers (do not need a Passenger class in implementation since system controls elevators, not passengers).
- Objects/Classes:
- ElevatorCar
- Floor
- Door
- ButtonPanel (two types: floor panels with Up/Down buttons, elevator panels with floor numbers)
- Dispatcher/Scheduler (assigns elevators to requests)
- ElevatorSystem (singleton)
- Monitoring system
- Mechanical components (motors, brakes)
- Use Cases:
- Calling the elevator.
- Moving or stopping the elevator.
- Opening/closing doors.
- Indicating elevator direction.
- Displaying current floor.
- Triggering emergency brakes and emergency calls.
- Class and Interface Design:
- Button interface implemented by:
- HallButtons (outside elevator, two buttons: Up and Down)
- ElevatorButtons (inside elevator, multiple floor buttons)
- Door class with open, close, and state-check methods.
- ElevatorMotion interface with move(destinationFloor) and stop().
- Interfaces for Dispatcher, monitoring, floors, etc.
- Encouragement to think about additional classes/interfaces and share ideas.
- Button interface implemented by:
- Scheduling Algorithms:
- 1. First Come First Serve (FCFS):
- Requests queued in order received.
- Elevator serves requests in queue order.
- Works well for single elevator.
- With multiple elevators, Dispatcher assigns nearest elevator.
- Flaws: Inefficient movements, no parallel request handling.
- 2. Shortest Seek Time First (SSTF):
- Elevator picks the closest request next.
- Uses priority queue or scanning an array of floors.
- Flaws: Possible starvation of distant requests, no parallel request handling.
- 3. SCAN (Elevator Algorithm):
- Elevator moves continuously in one direction serving requests until end floor.
- Then reverses direction.
- Uses boolean arrays for up/down requests and priority queues.
- Supports serving multiple requests in parallel.
- Flaws: Continuous movement increases power and maintenance; direction changes only at building ends causing delays.
- 4. LOOK Algorithm:
- Similar to SCAN but elevator only moves as far as the last request in the current direction.
- Stops early if no further requests ahead.
- More efficient than SCAN.
- Uses data structures like hash maps or trees for efficient look-ahead.
- Dispatcher chooses elevator based on heuristics (e.g., shortest seek time, building usage patterns).
- Real-world implementations combine LOOK with heuristics, e.g., positioning elevators at lobby during morning rush.
- Destination Dispatch Algorithm:
- Passengers input destination floor on a panel outside elevator.
- System assigns elevator that groups passengers going to similar floors.
- Optimizes throughput and reduces stops.
- Possibly uses k-nearest neighbors or other clustering algorithms.
- 1. First Come First Serve (FCFS):
- Design Principles:
- Use of enumeration for elevator states is acceptable because states are fixed and known.
- Avoid enums for parking lot types to adhere to Open-Closed Principle (extensibility without modifying existing code).
- Strategy pattern can be used to
Category
Educational
Share this summary
Is the summary off?
If you think the summary is inaccurate, you can reprocess it with the latest model.
Preparing reprocess...