Elevator System Design | Grokking the Object Oriented System Design Interview Question

字幕表動画を再生する

hello friends welcome to my channel in today's video we are going to discuss the design of
elevator system if you haven't seen my previous video on designing parking lot system then you
should check the video you can find the video here you can either watch it first or watch
it after this video there are many things that i have already discussed in my previous video
and i'm not going to discuss here however just to recall there are few points that i
discussed in greater detail in that video and i'm going to discuss those very briefly here
so you need to understand that elevator system design is also an object-oriented system design
interview question just like parking lot system design the very first thing is
when the interviewer asks you this question he's looking for your requirement collection expertise
he's looking for whether you can clearly list all the possible requirements
and also can you scope down the the system into something which you can solve in 30 to 45 minutes
another thing that the interviewer is looking for is your design skills especially your object
oriented design skills he is looking for how well you can design the system in terms of
components and classes how well versed are you in object oriented design concepts like abstraction
encapsulation in inheritance and polymorphism the interview is also looking for whether you
can you can identify different object oriented design patterns or other programming patterns
while designing the elevator system in case there are two or more elevators in the system
the interview is looking for how well you can tackle the concurrency in your system
again as i have mentioned in my previous video on designing parking lot system
this type of question is not a distributed system design question and so you should not try to solve
it as a distributed system design question if you try to do that then the interviewer can
interpret it as that you don't have sufficient experience to scope down the problem correctly
and he would think that instead of simplifying the problem you are actually over complicating it
in my opinion this is one of the best interviews to gauge the candidate's graph of the fundamentals
of the computer science in addition this can be extended into many different directions
making it an ideal problem to see how the candidate thinks it is easy to make it an
object-oriented design problem it can be used to discuss different data structures that can be used
in implementing the system if needed it can be made even more complicated by introducing two or
more elevator cars in the building where a request button summons the most appropriate elevator this
is another nice optimization problem but the core single elevator problem is often good enough to
judge the ability of a candidate to see different trade-offs inherent in any design now let's
discuss different requirements of the system so the very first requirement is that if you haven't
saw my course then please do check my course on system design w preparation the link is in the
description below at least go to the website which is still there and go through the free
preview chapters and see whether you like them or not okay joker parts the very first requirement is
that the alibaba car have three states whether it can go up down or idle so there are three states
it can go up it can go down or it could be idle we will represent these states of an elevator car
using enumeration so now i have a question for you in my past video in designing parking lot system
i said not to use animation for designing parking lot type however here i am saying that we can use
enumeration for these you can pause the video and think about it why i'm preferring animation
types here and why i'm not perfecting in the machine type in my previous video on designing
parking lot system what do you think please let me know in the comments below and don't
worry if you cannot guess right now i'm going to discuss this in this video later
the second requirement is the elevator can transfer passengers from one floor to another
transfer passengers
from one floor to another the third requirement is the elevator can only open its door
when it is idle
so open door
when idle at a floor
now let's discuss the number of floors that a building can have
the tallest building in the world is bhuj khalifa in dubai it has more than 160 floors
and more than 57 elevator cars so right now we can simply assume that in our system
we have 200 elevator floors so 200 elevator flows so since buja khalifa
has 57 elevator cars i'm assuming that okay right now we have 50 elevator cars
50 elevator cars now there are some requirements related to specification of each elevator car
specs of elevator car
and for example the number of passengers
number of
passengers that the elevator car can can actually carry or the maximum load
maximum load that the elevator car can carry
similarly the maximum speed with which the elevator car can move so the maximum speed
with which the elevator car can move up or down now the next requirement is what is we would like
to minimize in this whole system do we want to minimize the overall wait time of a passenger so
minimize
wait time or do we want to minimize the wait time of individual passenger wait time of system
or wait time of individual
passenger the other things that we would like to actually discuss in the requirement would
be like what about the throughput do we want to increase the support like the number of passengers
using the elevators to go from one floor to another do we want to increase it
so throughput another requirement could be that do we would like to minimize the
power usage by the the whole elevator system
so power usage minimization for the whole elevator system the reason is that as the elevators are
moving up and down they are using electricity and they are used they are consuming power
which means there is some cost associated with every movement of an elevator car
and then it also require maintenance now the more the elevator car is moving
it means there will be more maintenance it will be requiring periodically so that's the
question do we would like to minimize power usage and in this way they minimize the cost
during requirement collection you should also discuss with the interview whether he would
like to have different operational zones or sectors while designing the elevator system
a zone is a set of flows which is covered by a set of elevator cars for example in our system we are
we are assuming that there are 200 floors we can actually divide those 200 floors into let's say
four or five different operational zones if we divide them into four operational zones
then we can say okay the first 50 floors are one operational zone or sector the next 50 floors are
the second operational zone or sector and then and so on and so on and so we can say that only
from our elevators or 100 elevators that we have let's say 25 elevators will only serve the first
50 floors the next 25 elevator cars will only serve the next 50 floors and so on another example
is suppose in this system we have one two three four five six floors and we have two elevator cars
either we can consider this as a complete one operational zone where these two elevator cars
serve all these flows or we can also divide this into two different operational zones and
we could say that okay this elevator car will only serve the first three
floors while the other elevator car will only serve then the top three floors
another way of zoning is that we can say that this first elevator car will only serve
the even number of flows and this elevator car will only serve the odd number of flows
so why do we need zoning sometimes if the number of flows and the number of elevator cars are large
enough then it's very hard to actually come up with an efficient algorithm that could actually
serve all our requirements that is it can increase the support of passengers using the
elevator and minimize the cost and minimize the waiting time overall waiting time of the
system i think everyone knows about this divide and conquer strategy so in that case when the
problem becomes uh that complex it's better to actually divide it into smaller problems
and that's what we do by dividing the elevator system into multiple operational zones because now
those operational zones can can be considered as independent elevator systems and their operation
will be totally independent from the operation of other operational zones in that elevator system
now the question is how should we decide what are the different types of official zones should be
should we divide this whole elevator system into operational zones like first three and the top c
or even odd etcetera etcetera it all depends on our requirements whatever the requirements
we discuss with the interview or whatever the requirements we have for designing the system
dictates how we are going to divide the elevator system into multiple operational zones
apart from these requirements there are some extended requirements as well
for example triggering emergency alarm or brakes so emergency alarms brakes etc apart from the
normal elevator cars there could be some vip or utility elevators as well in the system so vip uh
utility elevator cars system apart from that there could be a monitoring system as well
so the monitoring system which is monitoring the status of the elevator cars and the doors the
button panels etc and there can be other external requirement as well let me know in the comments
below if i have missed any requirement that you think is important to discuss here now let's
discuss different objects and actors in our system so that we can come up with the different classes
and objects you know for the alpha elevator system design so the first actor is passenger
so passenger is some person
who actually would like to go from one floor to another floor the second object is elevator car
so like these are the elevator cars then of course we have floors
so we have different floors now in a building we also have doors
so elevator doors we also have button panels
button panels and there are actually two types of button panels
there are button panels which are outside the elevator on each floor
where you have two buttons up and down so there are two buttons only one for
going up and other for going down so these are the button panels in each floor and then we have
other button panels within the elevator which contains a list of all the floors which you can
press to actually tell the elevator system about your destination flow now as far as these button
panels are concerned each floor will have these but as far as the topmost uh flow is concerned it
will only have the only have one button which is the which is the direction downwards similarly the
lowest flow or the lobby in our case for example will have only one button which is going up apart
from that in our system we have the scheduler or dispatch system so i would say dispatcher
this component is responsible for selecting the
the most appropriate elevator to send to a passenger when a passenger calls
an eliminator car then of course we have the whole elevator system this is one big object
and this will be a singleton object in our system
apart from that we could also have monitoring system or monitoring object
and there can be other objects in the elevator system like alarms
and other like mechanical objects as well that are responsible for moving the elevator cars up
or down now before we go further i have a question for you do you think we need a passenger class
while implementing the elevator system pause the video here and think about it the correct
answer is we do not need a passenger class in the implementation of the elevator system
a passenger is an actor in our system which calls an elevator car and rides it to go from one floor
to another but in the implementation of the elevator system we really don't
need the passenger class itself and please note we are not designing an elevator simulation system
we are designing an elevator control system right now maybe a passenger class might be needed in the
implementation of elevator simulation system where we would like to simulate passengers but in actual
elevator system we don't need a passenger glass and that is the same reasoning why we don't need
a vehicle class in the design of parking lot system in my previous video many of you guys
asked that why we are not using a vehicle class in our implementation and the answer is it's the same
reasoning that the reason why we are not using a passenger class here in the design of elevator
system it's the same reason why we are not using the vehicle class in the design of parking lot
system now after discussing different objects and actors in our system we will now discuss
the different use cases this is mostly important for tpm or product manager interviews for sde
interviews the interval can ask the candidate to discuss them briefly because they can be used to
actually discuss the different implementation of those use cases so let me give you some examples
of different use cases in the elevator system design the first use case is calling the elevator
so of course what it means that when a passenger wants to go from one floor to another floor
he will press a button which will actually go to the scheduler or the dispatcher system the
dispatcher system will then figure out which elevator car is the most appropriate car that
it should schedule to send to the to that floor so this is what the calling the elevator use case is
then the second use case is move or stop the elevator so move or stop
elevator so an elevator can move up or move down or it can stop
if it's moving the third use case is open or close the doors so
open or close elevator doors the fourth use case is indicating the elevator direction
so when an elevator is going up or down usually we show this direction inside the elevator as well
as we also show it outside whenever i come on the floor we actually notify the the passengers there
who are waiting for the elevator that this elevator is going up or down
the another use case is indicating the elevator position or the num of the floor
so inside the elevator there is a panel where it shows the floor where the elevator is present
right now and it actually indicates the passengers if they need to hop off from the elevator at that
slow that okay this is your destination flow now another use case is triggering emergency
brakes similarly we have another use case which is making emergency call so emergency calls
and there can be other use cases as well let me know in the comments below if you if you think
there are other use cases as well which i have missed here now let's discuss different classes
and interfaces in our system so the very first example that i'm going to discuss right now is
basically the button interface it has passed down and is best uh methods and there are two types
of classes that actually implement that button interface we have elevator buttons and we have
all buttons so the whole buttons are the buttons which are outside the elevator at each floor which
is which has only two buttons up and down and then the elevator buttons are basically the buttons
which are inside the elevator and represent a number of floors the question is why we need
two different types of button class because the implementation is totally different the press down
of the whole button does totally different thing than what the press down of elevator button does
similarly we have a dual class and it has open function close function and is open to check
whether the door is open or not and we will have as many instances of this class as the number of
flows times the number of elevators similarly we can have an elevator motion interface
which has a move function which takes a destination flow and it could also have
a stop function as well similarly we will have interfaces and classes for the flows
in the system we will have interfaces for the dispatcher system as well for the monitoring
system as well and by the way for the monitoring system i actually discussed
the interface in the design of the parking lot system so you should check that video as well
and we can have other interfaces i'm not going to discuss those classes and objects right now
because see there are other online resources which you can find which are actually filled with all
those information and you can actually you can go through them and also if you would like to
know my opinion about the different classes and interfaces and their functions then let me know
what classes interfaces you can come up with in the comments below and i will then check them
and i will let you know whether you are right or wrong or if you have missed anything or not
now i would like to discuss the most important part here of the elevator system design which is
the scheduling algorithm as i said before the elevator system design is a unique interview
which can be tailored into discussing this many different things so it can be turned
into an object-oriented design question where the interviewer can ask you to come up with the
design of different classes interface etc it can also be turned into an interview question where
the interviewer will try to evaluate your problem solving skills in that case he might ask you to
actually come up with an appropriate algorithm that can be used to schedule the elevator cars
that's why you need to know at least these four algorithms that i'm going to discuss here
so the very first and the simplest algorithm to implement is first come first serve in this case
how we implement this first come first of request is that all these
hall buttons they are connected to the scheduler
and whenever and and whenever a passenger press a button there's a request that request goes
to the dispatcher and the dispatchers to it in a queue so all the request will go in a queue
so let's say there was a passenger here on let's say this these are the floors two three four five
and he wants to go down okay so that request will go in the queue here first so at three direction
is down there could be another passenger who is here and who wants to go up so
he pressed the button after this passenger so that request will go again here and it will be
one and up now let's just assume for the time being that we only have one elevator in the system
in that case what will happen is that the elevator first will go here
to this passenger so what the dispatcher will do it will take the first item and check and
then it will actually call the elevator to move to this destin this floor an elevator will go there
the passenger will hop on to the elevator car and then it will go to his destination and once
the elevator become empty at that time again the scheduler will come here and take the next
entry or the next request from the from the queue so you can see in the first come first of approach
that as a passenger is requesting the elevator car we are putting this request into a queue
and then we always process those requests in first come first serve manner
now in that in a case where we don't have one elevator but but two elevators what we would do
in that case the scheduler can actually decide to always send the nearest elevator to the passenger
and in order to serve the passenger request so now let's suppose if we have two elevator cars state
of one in that case what will happen that the dispatcher will always select the nearest elevator
to go and take the passenger which is requesting the elevator for example now in that case
first when the dispatcher will process this request it will it will then check
between these two elevators this elevator is near to this guy so he will actually send
this one here and of course then it will once after this it will go and look at this entry
and process this entry and for that this elevator will go to this passenger also there's one more
thing that we need to understand when there are two or more elevators that the elevators
could be in either four of these states so the first state the elevator can be is it's idle
so the elevator is not moving it's stopped at some flow the second state the elevator
can be is that the limiter can be moving in the same direction towards the passenger
and also the same direction where the passenger wants to go so moving same direction
towards
passenger and direction passenger wants to go
so for example let's just for example let's say this
passenger wants to go down and this also moving down which is this case
the third state this elevator car can be is that it is moving same direction
it is moving in the direction towards the passenger
but oppose it to direction passenger wants to go
example let's say this passenger wants to go up and this elevator is now going down it's
going towards the passenger but it's going in the opposite direction where the passenger wants to go
and then the fourth state is the the elevator car is going away from the passenger
going away from the passenger
so let me repeat again very quickly there are four different states
where we which in which we can find the elevator car the first state is the idle state where the
elevator cars is idle at stopped at a floor the second state is the elevator car is moving
towards the passenger and the same direction where the passenger wants to go for example
we take the example that this passenger wants to go down and then this elevator also going down
so it's going towards the passenger and also in the same direction where the passenger wants to go
the third is the third state is that the elevator is going towards the passenger but in the opposite
direction so the elevator is going down but this passenger wants to go up for example and then
the fourth one is that the elevator car is going away from the passenger so for example this this
passenger wants to go down and this elevator is going up so these are the four different states
so we can clearly see there that the dispatcher will actually ignore those elevators which are
in these two states that is they are either moving away from the passenger are moving
in a direction towards the passenger but away from the direction where the passenger wants to go
so now the dispatcher will always try to find an elevator between these two
states in order to serve the passenger request and so that it will check between these two types of
elevator cars and see which elevator car is then nearest to the passenger floor now clearly this
algorithm has some flaws there is a possibility where some requests could have been served
while some other requests were being served for example consider the case where we have a large
number of floors and we have a large number of uh basically a large number of elevators and
now there's uh one passenger who's going from the ground floor all the way up to fifth floor
and there's another passenger here who is here at the third floor going towards fifth floor
so in the first come first of mana what would happen is that this elevator first will go all
the way up to five and it will first completely serve the first passenger and then it will go to
the third one although ideally what it should have done is that it should have gone to this
passenger also and pick it up as well so we can see clearly see there's a flaw in this
in this algorithm this algorithm also results in extra up and down motions of elevator just
give you a simple example let's suppose we have only one elevator so this passenger
comes wants to go up then this passenger comes wants to go maybe up as well but we will first
the elevator car will first come here it will actually pick this passenger up go all the way
up drop the passenger and then it will go and check the next request in the dispatcher queue
and then serve it so it means there will be some extra up or down movements of the
elevator car which we could have avoided but this algorithm does not tackle those
those things the second algorithm is shortest seek time first this algorithm tries to favor
minimum movement of the elevator car as compared to the first one where we saw that there could
be extra movement of elevator car this is an improvement over the first come first serve basis
now there are two approaches to implement this one approach is using the priority queue or min heap
and in that case what you do you actually put the all the request entries in a priority queue
or the main hitman heap based on the distance of the requesting flow from the elevator flow
and then we pick the the top most request to be served but of course this min heap will
change as the position of the elevator changes it also changes so other approach is basically use
like an array and that array would be basically like something like this
equal to number of flows and so on and let's say if the elevator is here starting from that index
it will start scanning in this array to see which floor like which request is the minimum request
so this algorithm also has some flaws for example there is a possibility of starvation like for
example if there is one passenger which is here and then most of the passengers are at this point
so what will happen now the elevator will just keep serving these passengers that are coming here
and it will totally ignore the passenger which is a bit further away from the elevator car
and also similar to first come first of all approach this algorithm also does not support
serving multiple requests in parallel now the third algorithm is called scan
and it is also popularly known as elevator algorithm as well
now lets see how it is implemented in the scan algorithm there will be an array a boolean area
there will be actually two boolean arrays one for the up direction one for the down direction and
each elevator car it will be just scanning this whole building moving up and down so this elevator
car will go all the way up and only at it at this point it will change its direction it will go down
all the way down and then only at the bottom most uh floor it will then change its direction
and while each elevator car is moving at every floor they check the entry there so if this
elevator car is moving up at every floor that it reaches it checks the corresponding entry here
whether the entry is set or not and if it is set uh that is it is true then the
elevator car will stop there open the door and also reset this entry to false and also
not apart from this elevator each elevator car also has two priority queues min heap and max
heap for going up and down and they also check the entries there as well whether the when when
it's going up it's checking the min heap and see and checking whether the the entry the flow entry
there in the mean hip at the top is the current uh flow or not and if it's the current flow they stop
there and they also take out the entry from the uh from the priority queue from the min heap as well
so this algorithm has clearly advantages over the above two algorithms because now it can actually
serve multiple requests in parallel however it has its own slots as well the first flaw that it has
is that the elevator cars are continuously moving which means there is increased cost
now associated with it and of course then we need to do all the maintenance and everything
the second issue is that in this approach is that the elevator car will only change its direction
when it reaches one end so let's suppose if this elevator car is going up it will keep going up
until it reaches the end and then only then it will change its direction and this actually wastes
a lot of time as well and to overcome this we have the fourth algorithm that overcome this problem
and that algorithm is called look why we why we call it look because in this algorithm the
elevator actually look ahead to see at each floor it look ahead to see whether there are requests
or not for example if this elevator is going up it will actually try to look ahead for other request
in the up direction and if there are no requests in the abstraction
it will just stop there and it will not move at all so the look algorithm is similar to the
scan gotham but on the only thing is that in the scan algorithm the elevators they are keep moving
and they only change direction when they reach the top while here in the look algorithm the elevators
will stop as soon as there is no more request in front of them and that is the point where they can
change direction as well based on the request if the for example if this elevator was going
up and at this point it drops the passengers and it look ahead and see there's no other request in
the top floors then this elevator will stop here and then it will not move now it can only move
based on the request when the weather request is coming from a passenger in some floor which is
uh down the floor where the elevator is or it's up the floor where the elevator is now in the
local gotham let's suppose this passenger it wants to actually go up and there are two
elevators one of the elevators stopped here and the other elevator is going up in this direction
now when the passenger press the elevator car request button now the dispatcher has to decide
between these two elevators that which one it should actually dispatch to pick up the passenger
and now there are different approaches that the algorithm can use the first approach is that some
can use always the shortest seat time first so in this in this approach the algorithm will actually
suggest this elevator to go down and pick the pick the passenger although we know that there's
another elevator which is going up in reality the algorithm used by the elevator systems
is a combination of the look algorithm along with some modifications in it
the modifications are based on heuristics which are applied in the algorithm
the heuristics could include for example if it's an office building then of course
in the morning we would like the liberals to always be present at the lobby so that they can
take more passengers which are going towards their offices up or in the afternoon maybe for example
a late evening since everyone wants to go down maybe then what we would do if we have let's say
10 floors and three elevators maybe we can move those elevators automatically towards
towards floors like three six and nine so that they're spread over the whole building
in a way to actually cover most of the request when needed also one final thing is that in
the implementation of a scan we use the arrays but in the implementation of look algorithm we
can either use hashmap or tree map or like even a binary search tree because it would be way easier
to actually look ahead in that case like if an elevator is going up and it's reaches this
point in a binary search tree it will be way easier to see if there's any entry
greater than three in the binary search tree or not so let me know in the comments below
how will you implement these algorithms if you have to now in the beginning of the video
i discussed that we can actually use animation to represent the different states of the
elevator car while actually i discourage using the enumerations for the
for designing during the design of the parking lot system we need to understand that i was not
discussing the use of innovation actually i was using i was i was actually discouraging
the use of information for that scenario in case of the state of the elevator car
we know there are only three states either the elevator is going down or going up or its idle
there is no fourth state possible and since we already know in advance all the different types of
states that are possible that's why we can use animation there but in case of parking lot system
at the beginning we didn't know which type of parking lot we would like to actually use in
our parking lot it could be extend like a we had a parking lot category or type of like a compact car
and a large car but we can also always introduce different other types of parking lot
and that is why we cannot use innovation there because using animation will then violate the open
closed principle that we have and what the open close principle dictates the open close principle
dictates that whatever the code you are writing it should be able you should be able to extend it
without modifying the existing code if you are using animation for the parking lot
type and then you are introducing new parking lot types then in that case what will happen if you
are using enumeration that you will actually violate this open you have to go and modify
i think all the places where you have your if else or switch case statements
for the parking lot type you have to go and modify all that code
which will violate the open closed principle of object-oriented design now just for the sake of
completion i would also like to discuss one more algorithm which is nowadays being used
in in some very new buildings it is called a destination dispatch algorithm so it is
destination
dispatch and what it does actually is that in in some buildings what you will
find that instead of this up and down buttons there will be a separate panel
a screen there where the passenger can enter the destination flow and that panel will then
calculate the appropriate elevator for it and it will tell you okay to which door number or
elevator car number it should go to actually go to his to the destination flow so in that case
the dispatch algorithm try to load the passengers going to a same destination flow
in the same elevator in order to minimize uh the the wait time and also in order to minimize the
the moving time as well because now if all the passengers are going to the same flow and they
will not be stopping in between then it will of course increase the throughput of the system
so let me know in the comments below what do you think how the elevator system find the
most appropriate elevators in that case if they are using this destination dispatch algorithm a
hint is maybe k-nearing neighbors please note elevator system design discussed in this video
is just one way to design the elevator system however for your case the interviewer can to go
in totally different direction depending on what the interviewer is looking in the candidate and so
there could be totally different requirements that could be discussed in an interview also
there could be different requirements for which the implementation would be totally different
for example the requirement would be that you are actually designing a related system for
residential building so the requirements there would be totally different from the requirements
for an elevator system for the hotel or for an office building or from an airport building etc
also as far as the dispatching algorithms are concerned we use a strategy pattern for
implementing these algorithms so there could be multiple dispatch request strategy classes
in the system and when a system gets installed in a building then a set of dispatch request strategy
classes can be chosen depending on the scenarios and certain criterias like the time of day or the
day of week etc so i'm going to stop the video here please let me know in the comments below
uh do you find this video useful or not and also please like the video as well and
if you haven't subscribed to this channel please subscribe to this channel and click the bell icon
and by the way again if you haven't checked my course on stream design dev preparation
then please do check the course the link is in the description below thank you and take care