Low Level Design Questions

Parking Lot

Requirements

parking lot has multiple entrances and exits
collect ticket / spot is assigned at entrance
parking spot assigned should be near to the entrance vehicles enter from
capacity of parking lot is limited (e.g. 30k)
parking spot can be of different types - handicapped, compact, large, electric, two-wheeler
similarly, a vehicle can be of different types - car, bus, truck, bike, etc
parking fees should be based on duration, paid at exit
can pay using cash / credit card / debit card
ensure that the same parking spot is not assigned to multiple vehicles - this can happen when for e.g. two vehicles come from different entrances

Design

enums violate the open-closed principle, as it might require modifying the switch cases etc in our code
so, we use the factory pattern instead for parking spots
ParkingSpot - make it abstract so that it cannot be instantiated directly
it can have subclasses like HandicappedParkingSpot, CompactParkingSpot, etc
Terminal
- EntryTerminal - getTicket(Vehicle)
- ExitTerminal - payTicket(ParkingTicket)
ParkingAssignmentStrategy
- getParkingSpot(Vehicle)
e.g. for implementing the NearestToEntranceParkingStrategy, we can use min heaps
so, maybe we can have one min heap for each entrance
similarly, we can use the strategy design pattern for the payment processing, like credit card, cash, etc
FeeCalculatorStrategy - we can use the strategy design pattern here as well. we can for e.g. have an hourly fee, a parking lot booked for a specific event, charge more based on the peak hours, etc
use the singleton design pattern for the whole parking lot system
we need to maintain for each parking spot whether it is occupied or not

for this, the parking spot has an occupied AtomicBoolean variable

private AtomicBoolean occupied = new AtomicBoolean(false);
...
public boolean tryOccupying() {
  return occupied.compareAndSet(false, true);
}

why not synchronized - assume we use the synchronized keyword on the main method. now, assume that a car came before a bike. the bike would have to wait till the car is parked, even if their parking spot types are different
additional - read on payment system lld separately, and use it as a template for all such questions

Elevator

Requirements

we can have multiple elevators
“hall calls” - users request for an elevator using up / down buttons
the system determines which elevator to send
system should be able to handle concurrent requests

Design

we can take different strategies -
- minimize the power consumption
- minimize the wait time of passengers
- etc
Passenger
Request
- ExternalRequest
  - direction: ExternalRequestDirection(UP DOWN)
  - originFloor
- InternalRequest
  - destinationFloor
ElevatorController - singleton pattern
- elevators: Elevator[]
- requestElevator(ExternalRequest)
Elevator
- floor: int
- direction: ElevatorDirection(UP DOWN IDLE)
- requests: Request[]
logic for ElevatorController#requestElevator
- find the best elevator
- add to requests list of that elevator
the elevator can be in four different states -
- idle
- moving towards the passenger, and in the direction the passenger wants to go
- moving towards the passenger, but in a direction opposite to the direction the passenger wants to go
- moving away from the passenger
the controller needs to ignore the elevator states 3 and 4, and it can first prioritize 2 then 1
e.g. for 2nd case, we can return true as follows -
- if elevator direction is same as external request direction
- if external request direction is up and request origin floor > elevator floor
- if external request direction is down and request origin floor < elevator floor
finally, once we collect all the elevators satisfying this 2nd case, we need to find the closest elevator
to simulate time, we can use “ticks” / “steps” - in one tick, either the elevator stops to pick up / drop off passengers, or it moves one floor up / down
the elevator controller calls step on each of the elevators (looks like iterator design pattern) -
1 2 3 step(): for elevator in elevators: elevator.step()
now, we discuss the different “scheduling algorithms” for the elevator, which tells us the order in which the elevator would serve the requests
first come first serve -
- add requests to a queue
- the elevator would serve the requests one by one
- first go to the source floor of the first passenger, then take the passenger to its destination
- then, go to the second passenger and serve their request, and so on
- flaw in this approach - if request from passenger on 5th floor comes before the request from passenger on the 3rd floor, it ignores the request from the passenger on the third floor even if they are on the way
shortest seek time first -
- keep going to the passenger close to the elevator
- flaw in this approach - starvation of passengers say on the top floor, since the elevator keeps serving the passengers in the middle floors
scan algorithm -
- the elevator will go all the way up and then all the way down
- on each floor, it checks - if there is a request it can serve, it would stop and onboard the passengers
- disadvantage - it will consume a lot of power. it goes all the way to the top / bottom even if there are no pending requests there
look ahead scan -
- overcomes the shortcoming of scan algorithm by looking ahead
- if there are no requests, it would just stop and not move at all

so, the step algorithm of the elevator can look like this -

step():
  if requests is empty:
    direction = IDLE
    return

  # e.g. strategy, e.g. nearest floor:
  else if direction == IDLE
    nextFloor = getNextFloorFromRequests()
    direction = floor > nextFloor ? DOWN : UP

  # the elevator needs to stop
  else if requests contains a request for floor:
    if requests contains InternalRequest(floor):
      requests.remove(InternalRequest(floor))

    if direction == UP and requests contains ExternalRequest(floor, UP):
      requests.remove(ExternalRequest(floor, UP))
 
    if direction == DOWN and requests contains ExternalRequest(floor, DOWN):
      requests.remove(ExternalRequest(floor, DOWN))

  # reverse the direction
  else if direction == UP and no requests.floor > floor:
    direction = DOWN
  else if direction == DOWN and no requests.floor < floor:
    direction = UP

  else if direction == UP:
    floor += 1
  else if direction == DOWN:
    floor -= 1

how to handle concurrency? some scenarios -
- one user presses on floor 4, another user on floor 9. both get the idle elevator on floor 6
- we are updating the requests list of an elevator from different threads
we can use synchronized keyword, or try using some more fine grained locking mechanisms, e.g. each elevator can have its own lock

Amazon Locker Service

Requirements

customers can find the nearby locker based on zipcode
when searching for the list of lockers, only “eligible lockers” are shown
e.g. if a locker is not available for that time, or say a locker does not have a slot that can accommodate a package of that size, etc, it should not be shown
once a customer selects a locker, the locker (a slot in that locker) is reserved and a delivery agent is also assigned
then, the delivery agent comes to the locker with the package
the barcode of the package is scanned, and that opens the assigned slot
after this, an otp / qr code is sent to the customer
the customer needs to go to the locker and enter this otp / scan the qr code to open the assigned slot
then, the customer can pick up their package
packages can expire if not picked up in say 7 days, at which point the staff can come and pick them back up

Design

to me, this feels very similar to the parking lot design question, but with some extra stuff
in parking lot, we had a single parking lot with multiple parking spots
here, we have, multiple lockers distributed at different locations, and each locker has multiple slots
just like vehicle and spot in parking lot, the size of slot and package here helps decide the slot to assign
again just like in parking lot, we use strategy design pattern for the assignment of a slot in a locker to a package
however, here we need additional strategies for the search feature, delivery agent assignment feature, etc
Package
- size: PackageSize(SMALL MEDIUM LARGE)
- customer: Customer
- deliveryAgent: DeliveryAgent
Locker
- slots: Slot[]
Slot
- size: SlotSize(SMALL MEDIUM LARGE)
- available: AtomicBoolean
- package: Package
User, Customer extends User, DeliveryAgent extends User
LockerSearchService - strategy design pattern
- getLockersByZipAndPackageSize(zipcode: String, Package)
LockerService -
- reserveLocker(Locker, Package)
it should generate the OTP, and then also assign a slot and a delivery agent
SlotService - we use the strategy design pattern to assign a slot - e.g. assign a small package to a large slot if no small slot is available, etc
- assignSlot(Locker, Package)
AgentService - strategy design pattern to assign a delivery agent - e.g. assign the nearest delivery agent, assign the delivery agent with least number of deliveries, etc
- assignDeliveryAgent(Locker, Package)
OTP
- code: String
- expiration: DateTime
PickupService - verify the OTP, mark the slot as empty
add a scheduled service to release the expired packages

Uber

Requirements

ask clarifying questions always
do we need to support different kinds of cabs? - no for now

Design

Rider - email, phone number, etc
Driver -
- cab: Cab
- currentLocation: Location # to find the nearby drivers
- available: AtomicBoolean
Rider will create a Trip instance
Trip
- source: Location
- destination: Location
- rider: Rider
- driver: Driver null
- status: TripStatus(REQUESTED IN_PROGRESS COMPLETED CANCELLED)
- rating: double
- price: double
we can use state design pattern to manage the different states of the trip
PricingStrategy - use strategy pattern - based on distance, surge, premium customer, etc
- calculateEstimate(Trip) - show the estimate price to the rider before they confirm the trip
- calculatePrice(Trip) - calculate the final price based on distance traveled, time taken, wait time, etc
RideMatchingStrategy - use strategy pattern - near to the rider, have not fulfilled a lot of trips, etc
- selectDriver(Trip)
for the notifying of nearby drivers, we can point out “observer pattern”
RiderManager - singleton class for managing riders (aggregation, as riders can exist without the manager)
DriverManager - singleton class for managing drivers (aggregation, as drivers can exist without the manager)
we can think of these classes like repository classes as well

ATM

Requirements

what operations to support for the atm - only withdrawal for now
support different kind of notes - 2000, 500, 100

Design

why use the state design pattern - assume we track the states using an enum etc. it violates the open closed principle, as we would have to modify the switch cases etc in our code if we add a new state. also, it violates the single responsibility principle, as the same class would handle all kinds of states and functions
ATMState - note to self - this is one example of modelling the states, maybe try to clarify this with the interviewer
- IdleState - insertCard(card)
- CardInsertedState - enterPin(pin)
- PinEnteredState - selectTransaction()
- TransactionSelectedState - dispenseCash()
- CashDispensedState - ejectCard()
note to self - remember the basic structure of state design pattern -
- the context class (ATM) would have a reference to the current state
- all states would have a reference to the context class (ATM)
- the context class would delegate the function calls to the current state
- the context class can also be used to hold the “intermediate data” which can be shared between the different state objects, e.g. the current card needs to be accessed during pin verification, to verify if the amount the user tries to withdraw can be dispensed, etc
ATM
- currentState: ATMState
- insertCard(), enterPin(), selectTransaction(), dispenseCash(), ejectCard()
- map (denomination -> count)
- currentCard
Card
- cardNumber
- pin - maybe show use hashing etc when verifying the pin
- account: Account
Account
- accountNumber
- balance
for dispensing the cash, we can use a greedy algorithm - this uses “chain of responsibility” design pattern
again, why chain of responsibility - if we were to handle everything inside the dispenseCash method, we would not be able to add new denominations without modifying the existing functionality

Logger

Requirements

logs can have different “levels” (like importance) - info -> warn -> error
“appenders” (where to output the log) - console, file, etc
it can follow a certain format - timestamp [log level] message
the format of the log should be configurable - json, plain text, etc
it should be thread safe - e.g. if thread 1 logs “hello” and thread 2 logs “world”, the output should not be “hweolrllod” or something gibberish. it can be “helloworld” or “worldhello”, but not overlapped

Design

Log
- level: Level(INFO WARN ERROR)
- message
- timestamp
LogFormatter - strategy design pattern - JsonLogFormatter, PlainTextLogFormatter, etc
- format(log: Log)
LogLevelHandler - we use chain of responsibility design pattern. otherwise, we would have had if else / switch code blocks
if the level is error, invoke the error log level handler, else call the next handler in line. if the level is warn, invoke the warn log level handler, else call the next handler in line, and so on
LogAppender - strategy design pattern - ConsoleLogAppender, FileLogAppender, etc
- synchronized append(log: Log)
the appenders are configured using the formatter
making the append method synchronized ensures that the log messages are not interleaved when multiple threads are logging concurrently
we can have multiple appenders for the same log level - e.g. we can log to console and file for error level, but only to console for info level
so, we use the observer design pattern - the appenders are “observers”, while the level handlers are “subjects”
singleton design pattern is used for the logger - the same logger object is used globally

Chess

Requirements

board is 8*8
each cell is a combination of a letter and a number, e.g. a1, e5, etc
should support undo / redo
should we support special moves like castling - yes

Design

Player
- HumanPlayer - decideMove() gets the move from the user
- ComputerPlayer - decideMove() is determined by an algorithm run by the computer
Piece - each piece has a list of moves it can make
- color: Color(WHITE BLACK)
- moveStrategies: MoveStrategy[]
mention factory design pattern for creating pieces, as we have a dedicated subclass for each piece
we can use strategy design pattern for the MoveStrategy, and each piece can move in several ways, each implemented using the MoveStrategy
MoveStrategy
- abstract canMove(from: Cell, to: Cell, board: Board, piece: Piece): boolean
- isValid - check if same color piece is not present in destination cell etc
the abstract base class of the MoveStrategy can check if the move is valid - the piece should not try capturing another piece of its own color, it should not move outside the board, etc. meanwhile, the different strategies can implement the specific logic for how the piece should move, e.g. we can have a DiagonalMoveStrategy, HorizontalMoveStrategy, VerticalMoveStrategy, etc
this allows for extensibility - for adding additional moves, we just need to add additional implementations of this MoveStrategy
Cell
- row: char
- column: int
- color: Color(WHITE BLACK)
- piece: Piece null
Board
- Cell[][] cells
one Game class, which is like the controller responsible for managing the game, switching turns, checking for check / checkmate, etc
we can use memento design pattern to implement the undo / redo functionality
we store a stack of Move class
Move
- from: Cell
- to: Cell
- pieceMoved: Piece
- pieceKilled: Piece null
- undo()
undoing a move would mean -
- popping the last move from the stack
- moving the piece from the “to” cell back to the “from” cell
- if a piece was killed, we need to put it back on the “to” cell
note - one move in chess is special - castling move. it involves moving of two pieces and not just move. this might mean changes in different parts of the code. e.g. in case of undo, we might need to move two pieces back. so, instead of storing multiple moves, we can use “adapter pattern” here, and create a new class called CastlingMove which extends the Move class. i delegated the undo to the Move class so that it can determine how to undo the move, as for special moves like castling, it is not possible to have a generic undo logic

BookMyShow

Requirements

can use this for flight booking system, hotel booking system, etc as well
extensible for different types of seat
support different kinds of payment methods
add theatres, screens, movies, shows, seats into the system
support searching of movies
handle concurrency - only one out of multiple users should be able to book a seat
handle timeout of seats after some time duration

Design

Theatre
- name: String
- screens: Screen[]
- location: Location
Screen
- name: String
- seats: Seat[]
Seat - extended by ReclinerSeat, RegularSeat, etc
- seatNumber: String
- price: double
- show: Show
Movie
- title: String
- duration: int
Show
- movie: Movie
- screen: Screen
- startTime: DateTime
- theatre: Theatre
BookingService
- lockProvider: LockProvider (aggregation pattern)
- createBooking(booking: Booking)
- confirmBooking(booking: Booking)
LockProvider - strategy design pattern - RedisLockProvider, InMemoryLockProvider, etc
- tryLock(key: String, duration: int): boolean
- releaseLock(key: String): void
- isLockExpired(key: String): boolean
PaymentStrategy - implemented via upi strategy, card strategy, etc
- pay(booking: Booking)
Booking
- show: Show
- seat: Seat[]
- status: BookingStatus(CREATED PENDING CONFIRMED CANCELLED TIMED_OUT)

Rate Limiter

Requirements

rate limit users based on tier (free vs premium)
support different algorithms - token bucket, fixed window, sliding window log, sliding window counter, etc
thread safe / support concurrency

Design

User
- id
- tier - FREE PREMIUM
RateLimiter
- allowRequest(user: User): boolean
- config: RateLimiterConfig
this can use strategy design pattern - SlidingWindowRateLimiter, TokenBucketRateLimiter, etc
also, whenever using strategy design pattern, remember to combine it with factory design pattern so that we can create the appropriate strategy based on the configuration we provide
RateLimiterConfig
- timeWindow: int
- maxRequests: int - the number of requests allowed in the time window
while handling concurrency, we can use the synchronized keyword. disadvantage - it would be slow. we only need to synchronize the requests from the same user, not across different users

token bucket algorithm. notice things like the concurrent hash map, how we use .compute() to update the tokens in a thread safe manner for a concurrent environment, etc

private final Map<String, Integer> tokens = new ConcurrentHashMap<>();
private final Map<String, Long> lastRefillTime = new ConcurrentHashMap<>();

...

@Override
public boolean allowRequest(User user) {

  AtomicBoolean allowed = new AtomicBoolean(false);

  tokens.compute(user.getId(), (id, availableTokens) -> {

    long now = System.currentTimeMillis();

    int currentTokens = refillTokens(user, now);

    if (currentTokens > 0) {
      allowed.set(true);
      currentTokens -= 1;
    }

    return currentTokens;
  });

  return allowed.get();
}

private int refillTokens(User user, long now) {
  ... some basic logic
  return tokens;
}

sliding window log algorithm -

private final Map<String, Queue<Long>> requestLog = new ConcurrentHashMap<>();

...

@Override
public boolean allowRequest(String userId) {

  AtomicBoolean allowed = new AtomicBoolean(false);

  long now = System.currentTimeMillis() / 1000;

  requestLog.compute(userId, (id, log) -> {

    if (log == null) {
      log = new ArrayDeque<>();
    }

    while (!log.isEmpty() && (now - log.peekFirst()) >= config.getWindowInSeconds()) {
      log.removeFirst();
    }

    if (log.size() < config.getMaxRequests()) {
        log.add(now);
        allowed.set(true);
    }

    return log;
  });

  return allowed.get();
}

finally, for fixed counter / sliding counter, not going through the whole logic, but one point is that to get the window id, we can do something like this -
1 2 long currentTime = System.currentTimeMillis(); long windowId = (currentTime / 1000) / config.getWindowInSeconds();

Splitwise LLD

Requirements

expenses can be “direct” or create inside a “group”
for a group expense, first a group is created and members are added to it
for example, assume we create a group for goa, with the following expenses -
- flight tickets - person a owes person b 60$
- cycling - person a and person b owe person c 6$ each
“simplify debts” - a feature in split wise to reduce the number of transactions, e.g. above, person b would pay 54$ to person a and 12$ to person c to settle the debts. note that simplify debts feature is only present for group expenses, not for direct expenses
users should be able to view “balance sheet” for each group -
- total amount paid - 60$
- total expense - 23.33$
- balance -
  - person a - 23.33$
  - person b - 13.33$

Design

Group
- id
- name
- members: User[]
- expenses: Expense[]
- balanceSheets: map(User -> BalanceSheet)
BalanceSheet
- totalPaid: double
- totalExpense: double
- balances: map(User -> double) - positive means the user is owed money, negative means the user owes money
Expense
- splits: Split[]
- SplitType - EQUAL PERCENTAGE EXACT
- paidBy: User
- amount: double
- description: String
Split
- user: User
- amount: double
strategy design pattern for calculating the splits - EqualSplitStrategy, PercentageSplitStrategy, ExactSplitStrategy, etc, and again, we can use the factory design pattern for instantiating these different strategy services
so maybe the RequestDTO for the different strategies would be different. they too can use the factory design pattern, e.g. a base request dto class, with implementations like EqualSplitRequestDTO, PercentageSplitRequestDTO, ExactSplitRequestDTO, etc
“simplify debts” - we can use strategy design pattern for this as well
one way to do this can be greedy
we can find the net credit / debit for all users. now, does not matter who the user pays at the end of the day, the idea is that all the debts should be settled
so, for minimizing the transactions, we can use a greedy approach - find the person with the maximum credit and maximum debt, and then settle the minimum of the two. continue this process till the end. we can use heaps for doing this efficiently
i do not think greedy is accurate, but maybe i can point out that is why using a strategy pattern helps here. otherwise, we can try for all permutations, which would have complexity of the order of factorial

Low Level Design Questions

Parking Lot

Requirements

Design

Elevator

Requirements

Design

Amazon Locker Service

Requirements

Design

Uber

Requirements

Design

ATM

Requirements

Design

Logger

Requirements

Design

Chess

Requirements

Design

BookMyShow

Requirements

Design

Rate Limiter

Requirements

Design

Splitwise LLD

Requirements

Design

Further Reading

Go

Behavioral

Interview Experiences Revisions