Design a Car Rental System

Problem Statement
Flow and Requirement Classification
1. Vehicle, VehicleStatus and VehicleType
2. VehicleInventoryManager
3. Reservation
4. ReservationManager
5. Bill
6. Payment
7. Store
Class Diagram
Implementation

Resources

9. LLD of Car Rental System (Hindi) | ZoomCar Low Level Design |

System Design Interview Question
Code Repo → src/main/java/com/conceptcoding/interviewquestio
ns/carrental · main · shrayansh jain / LLD-LowLevelDesign · GitLab

Problem Statement
Design a detailed low-level model for a Car Rental System, including all relevant classes and
design patterns covered earlier.

Flow and Requirement Classification

User comes to care rental system.
Select a particular Store based on its Location.
Search for Vehicles based on vehicle type( like "Four Vehicle", "Two Wheeler" etc.) and its
availability.
Reserve the selected vehicle.
a. Should handle concurrency, as 2 users try to reserve the same vehicle for same time.

Start the trip.

Submit the vehicle.
Bill is generated against the reservation.
a. We can have multiple bill strategies for generating the bill, like daily Bill strategy or hourly
bill strategy etc.
 Payment is made against the Bill.
a. We can have multiple payment strategies for processing the payment like UPI, Card etc.

Based on above understanding, we identified the below major objects involved in this
design:
Vehicle
Store
Reservation
User
Bill
Payment

Lets start creating the UML:

1. Vehicle , VehicleStatus and VehicleType

Vehicle class represents the basic building block of the Car Rental System.
It comprises all the necessary details about the vehicle that is available for renting out, like
vehicle number, type, model, odometer readings, date of manufacture and its rental charge.
VehicleStatus and VehicleType help track and store more details about the
Vehicle in use.
Vehicle object is not intelligent, its just a POJO. We need some other intelligent object, which
can manage Vehicle inventory, like:
Maintain overall vehicles list.
Maintain booked vehicles list.
Add vehicle
Remove vehicle
Check for vehicle availability
etc.
That’s where VehicleInventoryManager comes into the picture.
Note:
each store has their own VehicleInventoryManager, so it is not a singleton class

2. VehicleInventoryManager

We will enhance the capability of this VehicleInventoryManager later when Reservation

capability will get added.

3. Reservation
Reservation, does not need full Vehicle and User details, so we can keep their ids itself in it.
Now, Reservation is not smart enough to handle capabilities like:
Maintaining the List of Reservations.
Fetch particular reservation details.
Creation of reservation, changing the reservation status.
Cancellation of reservation, changing the reservation status.
Remove the reservation
Etc.
That’s where ReservationManager comes into the picture.
Note:
each store has their own ReservationManager, so it is not a singleton class

4. ReservationManager
Need to handle:
Create Reservation should only be successful, when vehicle is available on that particular date.
Whats the right place to hold the vehicle booking information. Its "VehicleInventoryManager"
Note:
I created a ReservationRepository to break the circular dependency between
ReservationManager and VehicleInventoryManager.

Another thing which need to be handle is: Concurrency

2 important things to consider while handling the concurrency:
1st: Collections like List of vehicles, List of Booked vehicles should be able to handle
concurrency. So that our underlying data structure should be consistent when multiple threads
try to read or write in it.

2nd: Need capability, to put lock per Vehicle, this is needed for achieve atomicity.

For example: assume both thread1 and thread2 running concurrently, below scenario will cause
an issue:
Thread1:
Check for vehicle availability, touches the List of vehicles
Select a particular vehicle : V1
Try to reserve this particular vehicle (V1), change the status of vehicle
Update the List of Booked vehicles

Thread2:
Check for vehicle availability, touches the List of vehicles
Select a particular vehicle: V1
Try to reserve this particular vehicle (V1), change the status of vehicle
Update the List of Booked vehicles

Now, even though our collections are concurrent (only 1 thread can touch it at a time), still above
scenario will cause an issue and both the
thread will be able to book the same vehicle for same slot.
To handle it, we need to bring lock per vehicle:

Thread1:
Check for vehicle availability, touches the List of vehicles
Select a particular vehicle : V1
Put a lock on V1
Check for availability again
Try to reserve this particular vehicle(V1), change the status of vehicle
Update the List of Booked vehicles
Release lock
Thread2:
Check for vehicle availability, touches the List of vehicles
Select a particular vehicle: V1
Put a lock on V1
Check for availability again
Try to reserve this particular vehicle, change the status of vehicle
Update the List of Booked vehicles
Release lock

Now, one thread say Thread2 will wait for the lock to release on V1.
When Thread1, release the lock, then Thread2 will proceed and check for availability again, but
this time it will not be able to reserve as its not available.

5. Bill

Bill hold info like Reservation id like this bill is associated with which reservation. We don't
need full object.
Also, Bill is just a POJO class which is not smart enough. So we need:
BillManager, which handles all the bills and their lifecycle.
 Store, use this BillManager to generateBill for the given reservation.

6. Payment
Payment hold info like Bill id like this payment is associated with which bill. We don't need full
bill object.
Also, Payment is just a POJO class which is not smart enough. So we need:
PaymentManager, which handles all the payments and their lifecycle.
Store, use this PaymentManager to make payment for the given bill.
7. Store

Class Diagram
Implementation
Refer Code Repository for Executable Code → src/main/java/com/conceptcoding/interviewqu
estions/carrental · main · shrayansh jain / LLD-LowLevelDesign · GitLab
Design Movie Ticket Booking App

Reference: Concept&&Coding-By Shrayansh

LLD of BookMyShow (English) | Design MovieTicketBooking

Lets Understand the flow:

UML:

1. Seat

1 public class Seat {

2
3 private final int seatId;
4 private final SeatCategory category;
5
6 public Seat(int seatId, SeatCategory category) {
7 [Link] = seatId;
 8 [Link] = category;
9 }
10
11 public int getSeatId() {
12 return seatId;
13 }
14 }

1 public enum SeatCategory {

2 SILVER,
3 GOLD,
4 PLATINUM
5 }

2. Screen

1 public class Screen {

2
3 private final int screenId;
4 private final List<Seat> seats;
5 private final Map<LocalDate, List<Show>> showsByDate = new
HashMap<>();
6
7 public Screen(int screenId, List<Seat> seats) {
8 [Link] = screenId;
9 [Link] = seats;
10 }
11
12 public List<Seat> getSeats() {
13 return seats;
14 }
15
16 public void addShow(Show show) {
17 showsByDate
18 .computeIfAbsent([Link](), d -> new
ArrayList<>())
19 .add(show);
20 }
21
22 public List<Show> getShows(LocalDate date) {
23 return [Link](date, [Link]());
24 }
25 }

3. Theatre
 1 public class Theatre {
2
3 private final String name;
4 private final City city;
5 private final List<Screen> screens;
6 //address info etc.
7
8 public Theatre(String name, City city, List<Screen> screens) {
9 [Link] = name;
10 [Link] = city;
11 [Link] = screens;
12 }
13
14 public City getCity() {
15 return city;
16 }
17
18 public String getName() {
19 return name;
20 }
21
22 public List<Screen> getScreens() {
23 return screens;
24 }
25 }

1 public enum City {

2 BANGALORE,
3 DELHI
4 }

4. Theatre Controller

TheatreController:
1 public class TheatreController {
2
3 private final TheatreService theatreService;
4
 5 public TheatreController() {
6 [Link] = new TheatreService();
7 }
8
9 public void addTheatre(Theatre theatre) {
10 [Link](theatre);
11 }
12
13 public Set<Movie> getMovies(City city, LocalDate date) {
14 return [Link](city, date);
15 }
16
17 public List<Theatre> getTheatres(City city, Movie movie, LocalDate
date) {
18 return [Link](city, movie, date);
19 }
20
21 public List<Show> getShows(Movie movie, LocalDate date, Theatre
theatre) {
22 return [Link](movie, date, theatre);
23 }
24 }

TheatreService:
1 public class TheatreService {
2
3 private final Map<City, List<Theatre>> cityTheatres = new
HashMap<>();
4
5 public void addTheatre(Theatre theatre) {
6 cityTheatres
7 .computeIfAbsent([Link](), c -> new
ArrayList<>())
8 .add(theatre);
9 }
10
11 public Set<Movie> getMovies(City city, LocalDate date) {
12 Set<Movie> movies = new HashSet<>();
13 List<Theatre> theatres = [Link](city,
[Link]());
14
15 for (Theatre theatre : theatres) {
16 for (Screen screen : [Link]()) {
17 for (Show show : [Link](date)) {
18 [Link]([Link]());
19 }
20 }
21 }
22 return movies;
23 }
24
25 public List<Theatre> getTheatres(City city, Movie movie, LocalDate
date) {
26 List<Theatre> theatres = [Link](city,
[Link]());
27
28 return [Link]()
29 .filter(t -> [Link]().stream()
30 .anyMatch(s -> [Link](date).stream()
31 .anyMatch(show ->
[Link]().equals(movie))))
32 .toList();
33 }
34
35 public List<Show> getShows(Movie movie, LocalDate date, Theatre
theatre) {
36 List<Show> result = new ArrayList<>();
 37
38 for (Screen screen : [Link]()) {
39 for (Show show : [Link](date)) {
40 if ([Link]().equals(movie)) {
41 [Link](show);
42 }
43 }
44 }
45 return result;
46 }
47 }
48

5. Show

1 public class Show {

2
3 private final Movie movie;
4 private final LocalDate showDate;
5 private final LocalTime startTime;
6
7 private final Map<Integer, SeatStatus> seatStatusMap = new
HashMap<>();
8 private final Map<Integer, ReentrantLock> seatLocks = new
HashMap<>();
9
10 public Show(Movie movie, Screen screen, LocalDate date, LocalTime
time) {
11 [Link] = movie;
12 [Link] = date;
13 [Link] = time;
14
15 for (Seat seat : [Link]()) {
16 [Link]([Link](), [Link]);
17 [Link]([Link](), new ReentrantLock());
18 }
19 }
20
21 public Movie getMovie() {
22 return movie;
23 }
24
25 public LocalDate getShowDate() {
26 return showDate;
27 }
28
29 public LocalTime getStartTime() {
30 return startTime;
31 }
32
 33 public boolean lockSeats(List<Integer> seatIds) {
34 List<Integer> sorted = new ArrayList<>(seatIds);
35
36 //sorting i am doing to avoid deadlock scenario
37 [Link](sorted);
38
39 List<ReentrantLock> acquiredLocks = new ArrayList<>();
40
41 try {
42 // Phase 1: acquire all locks
43 for (int seatId : sorted) {
44 ReentrantLock lock = [Link](seatId);
45 [Link]();
46 [Link](lock);
47 }
48
49 // Phase 2: validate availability
50 for (int seatId : sorted) {
51 if ([Link](seatId) != [Link])
{
52 return false;
53 }
54 }
55
56 // Phase 3: mark LOCKED
57 for (int seatId : sorted) {
58 [Link](seatId, [Link]);
59 }
60
61 return true;
62
63 } finally {
64 // Phase 4: release locks
65 for (ReentrantLock lock : acquiredLocks) {
66 [Link]();
67 }
68 }
69 }
70
71 public void confirmSeats(List<Integer> seatIds) {
72 for (int seatId : seatIds) {
73 [Link](seatId, [Link]);
74 }
75 }
76
77 public void releaseSeats(List<Integer> seatIds) {
78 for (int seatId : seatIds) {
79 [Link](seatId, [Link]);
80 }
81 }
82 }

1 public enum SeatStatus {

2 AVAILABLE, LOCKED, BOOKED
3 }

Movie:
1 public class Movie {
2
3 private final String name;
4 //duration
5
6 public Movie(String name) {
7 [Link] = name;
8 }
 9
10 public String getName() {
11 return name;
12 }
13 }

6. Booking

1 public class Booking {

2
3 private final UUID bookingId;
4 private final User user;
5 private final Show show;
6 private final List<Integer> seats;
7 private final Payment payment;
8
9
10 public Booking(User user, Show show, List<Integer> seats, Payment
payment) {
11 [Link] = [Link]();
12 [Link] = user;
13 [Link] = show;
14 [Link] = seats;
15 [Link] = payment;
16 }
17
18 public UUID getBookingId() {
19 return bookingId;
20 }
21
22 public User getUser() {
23 return user;
24 }
25
26 public Payment getPayment() {
27 return payment;
28 }
29 }

User:
1 public class User {
2
3 private final String userId;
4 private final String name;
 5
6 public User(String userId, String name) {
7 [Link] = userId;
8 [Link] = name;
9 }
10 }
11

if Interviewer says, we need to manage the User lifecycle too like add, remove ,delete. Then we can have its own
controller like UserController. But here in booking functionality, we are not creating or managing user, so I am
skipping exposing the endpoints for managing the lifecycle of User.

Similarly, I am not creating PaymentController, PaymentService layer for now, but if interviewer want we can add
that too.

7. Booking Controller

BookingController:
1 public class BookingController {
2
3 private final BookingService bookingService;
4
5 public BookingController() {
6 [Link] = new BookingService();
7 }
8
9 public Booking createBooking(User user, Show show, List<Integer>
seats) {
10 Booking booking = [Link](user, show, seats);
11 return booking;
12 }
13
14 public Booking getBooking(UUID bookingId) {
15 return [Link](bookingId);
16 }
17
18 public List<Booking> getBookingsForUser(User user) {
19 return [Link](user);
20 }
21 }
22
BookingService:
1 public class BookingService {
2
3 private final Map<UUID, Booking> bookings = new HashMap<>();
4
5
6 public Booking book(User user, Show show, List<Integer> seats) {
7
8 if () {
9 throw new RuntimeException("Seat unavailable");
10 }
11
12 //simulated payment flow here, we can invoke Pay method of
Payment Controller
13 Payment payment = new Payment([Link]);
14
15 if ([Link]() == [Link]) {
16 [Link](seats);
17 Booking booking = new Booking(user, show, seats,
payment);
18 [Link]([Link](), booking);
19 return booking;
20 } else {
21 [Link](seats);
22 throw new RuntimeException("Payment failed");
23 }
24 }
25
26 public Booking getBooking(UUID bookingId) {
27 return [Link](bookingId);
28 }
29
30 public List<Booking> getBookingsForUser(User user) {
31 return [Link]()
32 .stream()
33 .filter(b -> [Link]().equals(user))
34 .toList();
35 }
36 }

Now lets talk about concurrency, 2 users should not book same seat.

So, what's the right place to put the lock:

1. Show?

It will work, but what if 2 users are booking totally different seats?
U1: S1, S2
U2: S4,S5
If we are putting the lock at Show level, then even users are booking the different seats, need to wait for the lock
release.

2. Show Seat level?

This give us higher level of concurrency. But every important point is, we need to avoid deadlock scenario:
U1: S1, S5
U2: S5, S1
Now,:
U1 has acquired the lock on S1
U2 has acquired the lock on S5

Now both are waiting for each other to release the lock on S5 and S1 respectively. Hence a deadlock scenario.
So, we can easily solve this issue through sorting of the Seat list.
U1: S1, S5 -> Sorted -> S1, S5
U2: S5, S1 -> Sorted -> S1, S5
Now, deadlock is not possible.

Client(BookMyShowApp):
1 public class BookMyShowApp {
2
3 private TheatreController theatreController;
4 private BookingController bookingController;
5
6 public static void main(String[] args) {
7 BookMyShowApp app = new BookMyShowApp();
8 [Link]();
9 [Link]();
10 }
11
12
13 private void initialize() {
14 theatreController = new TheatreController();
15 bookingController = new BookingController();
16
17
18 /*
19 * 1. Create Movies
20 */
21 Movie baahubali = new Movie("BAAHUBALI");
22 Movie avengers = new Movie("AVENGERS");
23
24
25 /*
26 * 2. Create Theatre -> Screen -> Seats
27 */
28 Screen inoxScreen1 = new Screen(1, createSeats());
29 Theatre inoxTheatreBangalore = new Theatre(
30 "INOX",
31 [Link],
32 [Link](inoxScreen1)
33 );
34
35 Screen pvrScreen1 = new Screen(1, createSeats());
36 Theatre pvrTheatreDelhi = new Theatre(
37 "PVR",
38 [Link],
39 [Link](pvrScreen1)
40 );
41
42 [Link](inoxTheatreBangalore);
43 [Link](pvrTheatreDelhi);
44
45
46 /*
47 * 3. Create Shows
48 */
49 Show inoxMorningShowToday = new Show(
50 baahubali,
51 inoxScreen1,
52 [Link](),
53 [Link](8, 0)
54 );
55
56 Show inoxAfternoonShowToday = new Show(
57 baahubali,
58 inoxScreen1,
59 [Link](),
60 [Link](15, 0)
61 );
62
63 Show inoxEveningShowToday = new Show(
64 avengers,
65 inoxScreen1,
66 [Link](),
67 [Link](18, 0)
68 );
69
70
71 Show pvrMorningShowTomorrow = new Show(
72 baahubali,
73 pvrScreen1,
74 [Link]().plusDays(1),
75 [Link](9, 0)
76 );
77
78
79 // Attach shows to screens
80 [Link](inoxMorningShowToday);
81 [Link](inoxAfternoonShowToday);
82 [Link](inoxEveningShowToday);
83 [Link](pvrMorningShowTomorrow);
84 }
85
86 /*
87 * USER FLOW (END TO END)
88 */
89 private void userFlow() {
90
91 // User enters system
92 User user = new User("U1", "Shrayansh");
93
94 [Link]("User logged in: Shrayansh");
95
 96 // 1. User selects city
97 City selectedCity = [Link];
98 [Link]("Selected City: " + selectedCity);
99
100 // 2. for specific date, Show movies running in city
101 LocalDate selectedDate = [Link]();
102 [Link]("Selected Date: " + selectedDate);
103
104 Set<Movie> movies = [Link](selectedCity,
selectedDate);
105 [Link]("Movies available:");
106 [Link](m -> [Link](" - " + [Link]()));
107
108 // 3. User selects movie
109 Movie selectedMovie = [Link]().next(); //selecting
first movie
110 [Link]("Selected Movie: " +
[Link]());
111
112
113 // 4. Show theatres and show times in city
114 List<Theatre> theatres =
[Link](selectedCity, selectedMovie,
selectedDate);
115 [Link]("Theatres available:");
116 [Link](t -> [Link](" - " +
[Link]()));
117
118 // 6. User selects theatre
119 Theatre selectedTheatre = [Link](0);
120 [Link]("Selected Theatre: " +
[Link]());
121
122 // 7. Show running shows for movie + date + theatre
123 List<Show> shows =
124 [Link](
125 selectedMovie,
126 selectedDate,
127 selectedTheatre
128 );
129
130 [Link]("Shows available:");
131 [Link](s ->
132 [Link](" - " + [Link]())
133 );
134
135 // 8. User selects show
136 Show selectedShow = [Link](0);
137 [Link]("Selected Show Time: " +
[Link]());
138
139 // 9. User selects seats
140 List<Integer> selectedSeats = [Link](1, 2, 3);
141 [Link]("Selected Seats: " + selectedSeats);
142
143 // 10. Booking + Payment
144 Booking booking =
145 [Link](
146 user,
147 selectedShow,
148 selectedSeats
149 );
150
151 [Link]("BOOKING SUCCESSFUL");
152 [Link]("Booking ID: " + [Link]());
153 }
154
155 private List<Seat> createSeats() {
156 List<Seat> seats = new ArrayList<>();
157 for (int i = 1; i <= 20; i++) {
158 [Link](new Seat(i, [Link]));
159 }
160 return seats;
161 }
162 }
Design Parking Lot
Reference:
Video: Design Parking Lot with Complete Implementation (English)
Git link: src/main/java/com/conceptcoding/interviewquestions/parking_lot · main · shrayansh j
ain / LLD-LowLevelDesign · GitLab

Lets understand the flow first:

Vehicle arrives at an Entry gate .

We can have multiple entry gate

Based on Vehicle Type, particular parking spot is looked for.

Interviewer can ask for flexibility in choosing the parking spot like random, or any specific
parking strategy
Also interviewer can say, parking lot can have multiple levels.
Concurrency should be handled properly, for example:
Same parking spot can not be reserved by two different vehicles.
for 1 vehicle say two wheeler we should not block the whole parking lot itself

If Parking spot is available, Ticket is generated for particular vehicle

a. Ticket can have: vehicle no, parking level no, parking spot no and Entry time.

At Exit gate, cost computation should have happened, Interviewer can ask for different
strategies for cost computation like:
a. Fixed price
b. Hourly based computation etc.

Payment will be made against the ticket at Exit gate and Parking spot is free again.

Based on above understanding, we identified the below major objects involved in this design:
 Vehicle
Parking spot
Parking level
Entry gate
Exit Gate
Ticket
Payment

Lets start creating the UML:

1. Vehicle

2. ParkingSpot

ParkingSpot object is not intelligent, its just a POJO.

Also we can have multiple Parking spot (like : 2Wheeler, 4Wheeler, Truck, EV etc.)
We need some other intelligent object,
That’s where ParkingSpotManager comes into the picture.

[Link]
Its an intelligent object, which help in managing Parking Spots like add, remove, park, unPark,
search free spot etc.

Intention:
We will have different manager to manage different type of parking.

Reasons:
Each manager has dedicated task to manage their parking spots only.
They will search for free space only in their set itself.
If they need to put lock during park() and unPark() operation, they can only block their set
of spots only.

Each manager can use different Parking Spot look-up strategy.

For ex: 2Wheeler manager is using Random strategy, where as 4Wheeler manager is using
NearestToEntraceGate Strategy.

[Link]
In case of Multi-level parking each level:

manages their parking independently.

Each level could support different type of parking, for ex: Level-1 support only 2wheelers,
Level-2 supports both 2wheeler and 4Wheelers likewise.
 Also we don’t have to lock the whole building parking spots itself, only specific Level and
specific Manager (2Wheeler, 4Wheeler etc.) need to be locked during parking and unParking
operation.

[Link] and EntranceGate

[Link] Gate
3 things happened at Exit gate:

Based on ticket, Cost computation

Payment
On payment success, release of the reserved spot
Reference:
Video: Design Parking Lot with Complete Implementation (English)

Git link: src/main/java/com/conceptcoding/interviewquestions/parking_lot · main · shrayansh j

ain / LLD-LowLevelDesign · GitLab
Design Elevator System
Functionality Requirements:
Object Identification:
Before moving ahead with UML, lets first understand:
Elevator Selection Strategy:
Elevator car moving behavior (i.e requests should be ordered by direction):
SCAN Algorithm:
LOOK Algorithm:
UML:
Implementation

Resources

8. Elevator System, Low Level Design (Hindi) | SDE LLD interview q

uestion | Design Elevator System
Code Repo → src/main/java/com/conceptcoding/interviewquestio
ns/elevator · main · shrayansh jain / LLD-LowLevelDesign · GitLab

Functionality Requirements:
A building has multiple elevators and multiple floors.
A user can request an elevator externally using Up / Down buttons at each floor.
These Up/ Down direction button is used to choose the best Elevator to server the request.
One Elevator is chosen, the floor is added in that particular elevator bucket list.
A user inside an elevator can also press an internal button to select destination floor.
Request generated from elevator Internal button, should always server by the same elevator only.
Elevators should remain idle (sleep) when no requests exist, and wake when new request arrives.
Requests should be ordered by direction:
Going up → visit floors in ascending order
Going down → visit floors in descending order

Object Identification:
Building
Floor
Elevator - just a POJO
Elevator Controller - each elevator is controlled by its controller, which manages its requests.
External Button - Each floor has the External Button
Internal Button - Each Elevator car has 1 Internal Button
Elevator Scheduler - Maintains the List of Elevator Controllers + also has Elevator Selection Strategy to choose the
best Elevator to serve the request
External Dispatcher -> bridge between External Buttons and Elevator Controller
 Internal Dispatcher -> Internal buttons can directly call their Elevator Controller, but sometimes we need to put
logging and validation, so its better to have one proxy. Also its follows the same path as external, so its clear too.

Before moving ahead with UML, lets first understand:

1. Elevator Selection Strategy?
and
2. Elevator moving behavior (i.e requests should be ordered by direction), what does that mean?
Going up → visit floors in ascending order
Going down → visit floors in descending order

Elevator Selection Strategy:

When External Button is pressed, info which we have is:
Floor: floor at which user is waiting for the lift
Direction: whether user wants to go up or down.
Now when there are more than 1 elevator, then we need to select the Elevator based on some strategy like:
Nearest Elevator : the elevator which is nearest to the user, should handle the request.
Least Busy Elevator: the elevator which has least number of request, should handle the request
etc.
So, Selection strategy uses :
Floor info, from where the request has come.
Direction info, where the user wants to go
Elevators info like:
its request bucket
Elevator direction
Elevator current floor
And based on the algorithm, it picks one elevator to serve the request.

Elevator car moving behavior (i.e requests should be ordered by direction):

SCAN Algorithm:
Head moves in one direction first, servicing the requests along the way.
Once it reached till the end, it reverses the direction. So it moves End to end.
EX:
Elevator going till top floor even if there is no request.

LOOK Algorithm:
Same as SCAN, but with one change that, it Don't go till end, stop when there is no request.

We can implement this LOOK Algorithm using 2 priority queues:

Min Priority Queue: Used when elevator is going UP, as it need to serve the request in ascending order.
Max Priority Queue: Used when elevator is going DOWN, as it need to serve the request in descending order.
Example:
UML:
1. Elevator Car: An object, which moves to particular destination when asked to.

1 package [Link];
2
3 import
[Link];
4
5 public class ElevatorCar {
6
7 int id;
8 int currentFloor;
 9 int nextFloorStoppage;
10 ElevatorDirection movingDirection;
11 Door door;
12
13 public ElevatorCar(int id) {
14 [Link] = id;
15 currentFloor = 0;
16 movingDirection = [Link];
17 door = new Door();
18 }
19
20 public void showDisplay() {
21 [Link]("elevator:" + id + " Current floor: " +
currentFloor + " going: " + movingDirection);
22 }
23
24 public void moveElevator(int destinationFloor) {
25 //this is dump object, so if command has come, to go
particular direction and particular floor, it just move
26 //no matter what its current state and floor.
27
28 [Link] = destinationFloor;
29 if ([Link] == nextFloorStoppage) {
30 [Link](id);
31 return;
32 }
33
34 int startFloor = [Link];
35 [Link](id);
36 if(nextFloorStoppage >=currentFloor) {
37 movingDirection = [Link];
38 showDisplay();
39 //+1 i am doing bcoz, floor start from 0,1,2.... so if
anyone goes from 1st floor to 2nd, so only 1 floor
40 //lift has to move, not 2.
41 for (int i = startFloor+1; i<= nextFloorStoppage; i++) {
42 try {
43 [Link](5);
44 }catch (Exception e) {
45
46 }
47 setCurrentFloor(i);
48 showDisplay();
49 }
50 }
51 else {
52 movingDirection = [Link];
53
54 showDisplay();
55 for (int i = startFloor-1; i>= nextFloorStoppage; i--) {
56 try {
57 [Link](5);
58 }catch (Exception e) {
59
60 }
61 setCurrentFloor(i);
62 showDisplay();
63 }
64 }
65 [Link](id);
66 }
67
68 public void setCurrentFloor(int currentFloor) {
69 [Link] = currentFloor;
70 }
71 }
72
73

1 public enum ElevatorDirection {

2 UP,
 3 DOWN,
4 IDLE;
5 }

1 public class Door {

2 private DoorState doorState;
3
4 Door() {
5 doorState = DoorState.DOOR_CLOSED;
6 }
7
8 public void openDoor(int id) {
9 doorState = DoorState.DOOR_OPEN;
10 [Link]("Opening the Elevator door of elevator:" +
id);
11 }
12
13 public void closeDoor(int id) {
14 doorState = DoorState.DOOR_CLOSED;
15 [Link]("Closing the Elevator door of elevator:" +
id);
16 }
17
18 }

1 public enum DoorState {

2 DOOR_OPEN,
3 DOOR_CLOSED
4 }

2. Elevator Controller

1 package [Link];
2
3 import
[Link];
4
5 import [Link];
6
7 public class ElevatorController implements Runnable {
8
9 PriorityBlockingQueue<Integer> upMinPQ;
10 PriorityBlockingQueue<Integer> downMaxPQ;
11
12 ElevatorCar elevatorCar;
13
14 private final Object monitor = new Object();
15
16 ElevatorController(ElevatorCar elevatorCar) {
17
18 [Link] = elevatorCar;
19 upMinPQ = new PriorityBlockingQueue<>();
20 downMaxPQ = new PriorityBlockingQueue<>(10, (a, b) -> b - a);
21 }
22
23 public void submitRequest(int destinationFloor) {
24 enqueueRequest(destinationFloor);
25 }
26
27 private void enqueueRequest(int destinationFloor) {
28 [Link]("Request details-> destinationFloor: " +
destinationFloor + " accepted by elevator:" + [Link]);
29
30 if (destinationFloor == [Link]){
31 return;
32 }
33 if (destinationFloor >= [Link]) {
34 if () {
35 [Link](destinationFloor);
36 }
37 } else {
38 if () {
39 [Link](destinationFloor);
40 }
41 }
42
43 synchronized (monitor) {
44 [Link](); // wake elevator thread
45 }
46 }
47
48 @Override
49 public void run() {
50 controlElevator();
51 }
52
53 public void controlElevator() {
54
55 while (true) {
56
57 //no request, go to sleep
58 synchronized (monitor) {
59 while ([Link]() && [Link]()) {
60 try {
61 [Link]("elevator:" +
[Link] + " is IDLE");
62 [Link] =
[Link];
63 [Link](); // sleep until request arrives
64 } catch (InterruptedException e) {
65 [Link]().interrupt();
66 }
67 }
68 }
69
70
71 while (![Link]()) {
72 int floor = [Link]();
73 [Link]("Serving floor: " + floor + " by
elevator:" + [Link] + " currentFloor: " +
[Link]);
74 [Link](floor);
75 }
76
77
78 while (![Link]()) {
79 int floor = [Link]();
80 [Link]("Serving floor: " + floor + " by
elevator:" + [Link] + " currentFloor: " +
[Link]);
81 [Link](floor);
82 }
83 }
84 }
85 }
86
87
3. Elevator Scheduler:

1 public class ElevatorScheduler {

2
3 private final List<ElevatorController> controllers;
4 private ElevatorSelectionStrategy strategy;
5
6 public ElevatorScheduler(List<ElevatorController> controllers,
7 ElevatorSelectionStrategy strategy) {
8 [Link] = controllers;
9 [Link] = strategy;
10 }
11
12 public void setStrategy(ElevatorSelectionStrategy strategy) {
13 [Link] = strategy;
14 }
15
16 public ElevatorController assignElevator(int floor,
ElevatorDirection direction) {
17 return [Link](controllers, floor, direction);
18 }
19 }

1 public interface ElevatorSelectionStrategy {

2
3 ElevatorController selectElevator(List<ElevatorController>
controllers,
4 int requestFloor,
5 ElevatorDirection direction);
6 }

1 package [Link];
2
3 import
[Link];
4
5 import [Link];
6
7 public class NearestElevatorStrategy implements
ElevatorSelectionStrategy {
8
9 @Override
10 public ElevatorController selectElevator(List<ElevatorController>
controllers,
11 int requestFloor,
12 ElevatorDirection
direction) {
13
14 ElevatorController best = null;
15 int minDistance = Integer.MAX_VALUE;
16
17 //1. Pick the one which is going in same direction and minimum
distance from the destination
18 for (ElevatorController controller : controllers) {
19 int nextFloorStoppage =
[Link];
20
21 // Good candidate if moving same direction & not passed
requested floor
22 boolean isSameDirectionCandidate =
23 [Link] ==
direction &&
24 ((direction == [Link] &&
nextFloorStoppage <= requestFloor) ||
25 (direction ==
[Link] && nextFloorStoppage >= requestFloor));
26
27 int dist = [Link](nextFloorStoppage - requestFloor);
28
29 if (isSameDirectionCandidate && dist < minDistance) {
30 minDistance = dist;
31 best = controller;
32 }
33 }
34
35 // fallback: if not able to choose, pick the idle one
36 if (best == null) {
37 for (ElevatorController controller : controllers) {
38 if([Link] ==
[Link]) {
39 best = controller;
40 break;
41 }
42 }
43
44 //reached here means, no list is going in same direction
and no lift is IDLE too, then pick any lift
45 if(best == null) {
46 best = [Link](0);
47 }
48 }
49 return best;
50 }
51 }
52

1 package [Link];
2
3 import
[Link];
4
5 import [Link];
6
7 public class LeastBusyStrategy implements ElevatorSelectionStrategy {
8
9 @Override
10 public ElevatorController selectElevator(List<ElevatorController>
controllers,
11 int requestFloor,
12 ElevatorDirection
direction) {
13
14 ElevatorController best = null;
15 int minLoad = Integer.MAX_VALUE;
16
17 for (ElevatorController controller : controllers) {
18 int load = [Link]() +
19 [Link]();
20
21 if (load < minLoad) {
22 minLoad = load;
23 best = controller;
24 }
25 }
 26 return best;
27 }
28 }
29

4. Button and dispatchers:

1 package [Link];
2
3 import
[Link];
4
5 public class ExternalButton {
6
7 private final ExternalDispatcher dispatcher;
8
9 public ExternalButton(ExternalDispatcher dispatcher) {
10 [Link] = dispatcher;
11 }
12
13 // this direction of external button is only helpful in selecting
the correct elevator
14 public void pressButton(int floor, ElevatorDirection direction) {
15 [Link](floor, direction);
16 }
17 }
18
19

1 package [Link];
2
3 import
[Link];
4
5 import [Link];
6
7 public class ExternalDispatcher {
8
9 ElevatorScheduler scheduler;
10
11 public ExternalDispatcher(ElevatorScheduler scheduler) {
12 [Link] = scheduler;
13 }
14
15 public void submitExternalRequest(int floor, ElevatorDirection
direction) {
16
17 ElevatorController controller =
18 [Link](floor, direction);
 19 [Link](floor);
20 }
21
22 }
23

1 package [Link];
2
3
4 public class InternalButton {
5
6 private final ElevatorController controller;
7
8 public InternalButton(ElevatorController controller) {
9 [Link] = controller;
10 }
11
12 public void pressButton(int destinationFloor) {
13 //we can also remove teh Internal dispatcher from mid, but
generally say for validation, controller and
14 //similar code flow like external button, its good have
15
16 [Link]()
17 .submitInternalRequest(destinationFloor, controller);
18 }
19 }

1 package [Link];
2
3 public class InternalDispatcher {
4
5 private static InternalDispatcher INSTANCE = new
InternalDispatcher();
6
7 private InternalDispatcher() {}
8
9 public static InternalDispatcher getInstance() {
10 return INSTANCE;
11 }
12
13 // elevatorController is known based on button press origin
14 public void submitInternalRequest(int destinationFloor,
ElevatorController controller) {
15 [Link](destinationFloor);
16 }
17 }

4. Floors and Building:

 1 package [Link];
2
3 import
[Link];
4
5 public class Floor {
6
7 int floorNumber;
8 ExternalButton upButton;
9 ExternalButton downButton;
10
11 public Floor(int floorNumber, ExternalDispatcher dispatcher) {
12 [Link] = floorNumber;
13 [Link] = new ExternalButton(dispatcher);
14 [Link] = new ExternalButton(dispatcher);
15 }
16
17 public void pressUpButton() {
18 [Link](floorNumber, [Link]);
19 }
20
21 public void pressDownButton() {
22 [Link](floorNumber, [Link]);
23 }
24 }

1 package [Link];
2
3 import [Link];
4 import [Link];
5
6 public class Building {
7
8 List<Floor> floors = new ArrayList<>();
9
10 public Building(int totalFloors, ExternalDispatcher dispatcher) {
11 for (int i = 1; i <= totalFloors; i++) {
12 [Link](new Floor(i, dispatcher));
13 }
14 }
15
16 public Floor getFloor(int floor) {
17 return [Link](floor-1);
18 }
19 }
20
Implementation
Refer Code Repository for executable code → src/main/java/com/conceptcoding/interviewquestions/elevator · main
· shrayansh jain / LLD-LowLevelDesign · GitLab
Design Snake and Ladder Game
Problem Statement
Overview
Requirement Classification
Components
1. Player
2. Board
3. Dice
4. Jump - Snake and Ladder
5. Cell
6. Game
Class Diagram
Implementation

Resources

11. LLD of Snake and Ladder game (Hindi) | SDE system design int
erview question, Java implementation
Code Repo → src/main/java/com/conceptcoding/interviewquestio
ns/snakeNladder · main · shrayansh jain / LLD-LowLevelDesign · GitL
ab

Problem Statement
Design a detailed low-level-design of Snake and Ladder Game including all object-oriented-
design patterns and principles discussed earlier.

Overview
A Snake and Ladder Game is a 2-player game(can be extended to have more players by
incorporating different winning startergies) where each player takes turns in moving their
placement on the grid typically of size 10x10(i.e. 100 cells numbered from [0-99]) by rolling the
dice starting from position one(i.e. cell 0).
This game consists of 3 main components:
Dice → Yields a random number between [1-6] which tells the player to move “x” number of
cells in forward direction.
Ladders → Helps the player jump to a higher position.
Snakes → Steps down the player to a lower position.
Requirement Classification
Snake and Ladder Game Board grid Size? → Fixed 10x10 i.e. 100 cells
How many dice? → 1, but it should be scalable. A dice roll function should yield a random
number between [1-6].
Number of Snakes & Ladders → We should be able to dynamically define it.
Number of Players? → 2 players but configurable.
Winning Strategy → 2 Player Game, if anyone finishes first(reaches the last position i.e. cell
100 on the grid), the person is the winner and the game is over.
Game → Acts as a central controller of all the above components.

Components
1. Player

The Player component encapsulates information about the person who choses to play
the game.
Holds variables to save the Name and track the movement during the game.

2. Board

The Board class is composed of cells, a 2D matrix.

Has methods to initialise, fetch and hold game boards logic.
3. Dice

A Dice class holds the max and min value of an inclusive range of numbers that a dice roll
can yeild.
This class is used to simulate the dice roll action using random number generation logic.

4. Jump - Snake and Ladder

The Jump class represents the board cell behaviour and holds value of its cell positions.
A few specific board cells is composed of Jump object that simulate Snake and Ladder
behaviour when the player acquires that cell upon a dice roll.
Snake behaviour is implemented using a higher cell position value as start and lower cell
position value as end indicating teh player to move backward.
Ladder value is implemented using using a lower cell position value as start and higher cell
position value as end indicating the player to move forward.

5. Cell

A Cell component represents what a game Board class is made up of.

Each Cell is composed of a Jump object.
 If the Jump object is not null, it implies that, this specific cell has a Snake’s start or
Ladder’s start position from which the player either moves backward(if a snake) or moves
forward(if a ladder).
If Jump object is null, it means the board cell is not associated with snake or ladder, then
the player occupies the new cell position.

6. Game

The Game class acts a central controller that is composed of all necessary components like
Board , Dice , Players .
It is responsible for orchestrating the entire Snake and Ladder Game by defining behaviours
for various actions that play by the rules established.
It initialises the Game with Board , Dice and Players - the mandatory entities
needed to start a game.
Starts the game, choses player, alternates the turns, rolls dice and moves the current player
forward and checks if its new position is associated with a Jump behaviour and it is moved
further ahead/backward mimicking the Snake/Ladder’s behaviour.
Declares the Player who reaches the last board cell position as winner and ends the
Game .

Class Diagram
We combine all the components discussed above and build a final Class Diagram with all the
neccessary class relationships that works as a blueprint to implement an executable solution.
Implementation
Refer to Code Repo for executable code → src/main/java/com/conceptcoding/interviewquesti
ons/snakeNladder · main · shrayansh jain / LLD-LowLevelDesign · GitLab
Design a Tic-Tac-Toe Game
Problem Statement
Overview
Requirements
Components
1. PieceType
2. PlayingPiece
3. Board
4. Player
5. TicTacToeGame
Class Diagram
Implementation
Output

Resources

7. Design Tic Tac Toe game (Hindi) | Tic-Tac-Toe LLD Java | Low L
evel Design, System Design
Code Repo → src/main/java/com/conceptcoding/interviewquestio
ns/tictactoe · main · shrayansh jain / LLD-LowLevelDesign · GitLab

Problem Statement
Design a comprehensive 2-player tic-tac-toe game of Xs and Os with the executable code
following all design principles, patterns, best practices and guidelines discussed before.

Overview
Tic-tac-toe is a simple two-player paper-and-pencil game. Each player selects a piece before
the game and takes turns placing it on the 3x3 grid. A player wins by placing three pieces in a
row, column, or diagonal. The game ends when a player wins or when all grid cells are filled,
resulting in a draw.
 TicTacToe Winner: PlayerX

Requirements
A 3x3 board should be used to play the game.
2 Players are marked by the piece they choose to play with - PlayerX and PlayerO
The game should end when a player wins.
The game should end when it's a draw(the players are out of free cells to play).
The game should not allow any invalid moves.

Components
1. PieceType

It's a symbol that is used to represent the cell value.

Here we are using X and O. We can also choose different symbols.

2. PlayingPiece
 The base class represents PlayingPiece, used to represent the symbol used.
Holds a reference to PieceType used to represent a piece.
The concrete classes PlayingPieceX and PlayingPieceO denote specific PlayingPiece s
associated with the corresponding PieceType .

3. Board

Board is a concrete class that contains a 3x3 matrix of PlayingPiece used for
playing the game and marking the positions where players place their pieces.
We can create a grid of any size we want and define corresponding rules to extend the game
in future.
Includes methods to play the game, such as placing a piece, updating the cell value, checking
for free cells, and detecting a winning move or game end.

4. Player

Player is a concrete class that represents a Player in the game.

It is composed of a PlayingPiece type, a symbol that a Player chooses to
represent at the beginning of the game.
5. TicTacToeGame

This concrete class contains core Game control logic.

This class handles alternating turns between players, validating their moves, checking for a
winning move, displaying the board after each step, and declaring the game winner or a draw
before ending the game.
Hence, it is composed of Players and a game Board reference for orchestrating the
Game flow.
Once the Game is over, the appropriate GameStatus value is returned.

Class Diagram
We combine the components above to produce a final solution to the TicTacToe Game Design
problem.

Implementation
Refer Code Repository for Executable Code → src/main/java/com/conceptcoding/interviewqu
estions/tictactoe · main · shrayansh jain / LLD-LowLevelDesign · GitLab
Output