Elevator System Design | Grokking the Object Oriented System Design Interview Question
Vložit
- čas přidán 26. 07. 2024
- Elevator System Design is a commonly asked Object Oriented Design Interview Question in big tech companies like Google, Facebook, Microsoft, Amazon, etc. In this video, I am discussing how to tackle System Design interview questions about designing an elevator system. This video includes the following, however, I would recommend you to watch the video full to avoid missing any important points.
00:00 - Introduction
00:30 - How to tackle Object Oriented System Design Interview Questions
02:45 - Requirements of an Elevator System
11:35 - Actors and Objects in an Elevator System
15:35 - Use cases in Elevator System Design
18:00 - Classes and Interfaces in the Elevator System Design
20:05 - Dispatch Algorithms used in an Elevator System
41:15 - Final Remarks
Distributed System Design Interviews Bible | Best online resource for System Design Interview Preparation is now available. Please visit: www.thinksoftwarelearning.com?
Please follow me on / think.software.community if you like to get notified about new course chapters getting added or when we will start another round of mock interviews and you want to participate in mock interviews or any other updates. I will also take your suggestions there about the course and the channel.
Check out our following articles:
- How to Ace Object-Oriented Design Interviews: / how-to-ace-object-orie...
- Elevator System Design - A tricky technical interview question: / elevator-system-design...
- System Design of URL Shortening Service like TinyURL: / tinyurl-design-from-th...
- File Sharing Service Like Dropbox Or Google Drive - How To Tackle System Design Interview: / how-to-tackle-system-d...
- Design Twitter - Microservices Architecture of Twitter Service: / design-twitter-microse...
- How to Effectively Use Mock Interviews to Prepare for FAANG Software Engineering Interviews: / how-to-effectively-use...
- Robinhood Backend System Design - How to receive realtime stock updates: / robinhood-backend-syst...
- Payment Gateway System Design - How does the Stripe work: / payment-gateway-system...
- Selecting the best database for your service: / selecting-the-best-dat...
#SystemDesign #DistributedSystems #FAANG #Facebook #Google #Amazon #Apple #Microsoft #Uber #Netflix #Oracle #Lyft #Interview #ComputerProgramming
Let me know whether you find the video useful. Also please don't forget to like the video and subscribe to this channel. Thanks :)
Distributed System Design Interviews Bible | Best online resource for System Design Interview Preparation is now online. Please visit: www.thinksoftwarelearning.com?
Please follow me on facebook.com/Think.Software.Community if you like to get notified about new course chapters getting added or any other updates. I will also take your suggestions there about the course and the channel.
I haven't finished the video, because I want to try it myself first.
I had an idea for the following case.
Elevator is @ floor 5,
Before the doors close, floor 10 is requested, as the elevator begins to move floors 7,6 and 9 are requested.
Would it be a good idea to scan the queue and put all requested floors into a min heap to handle requests between the interval [currentFloor - > requestedFloor]?
Thanks for the comment. You should see the video complete. There are multiple algorithms for elevator system
i have worked 27y in the elevator industry from field engineer to R&D hardware developer, software architect , project manager , R&D manager in two EU MNC.....it would be impossible to make an (OO) design of a an elevator controller in 45 minutes and describe all its nuances....and if that 45 minutes are the potential answer to an interview question at Google , it is very very messy.....i am preparing an elevator (mechatronic) design online course on my own but it is a HUGE topic...you have not cover even 0.01% of all potential elevator features/requirements (some of which even varies by region/country/city)
Thanks for the comment. The goal of this video also was not to design completely in 45 min and done with it. But just to provide food for thought and some hints about what are different things to consider 🙂. In interview also, the interviewer is not looking at you to solve the problem end to end but looking at how you tackle the question.
Your videos are really helpful. I have a suggestion if you could go on low level design like creating iterfaces/abstract classes for different actor and how will you club then in the elevator system class. And how these component will interact with each other. That would be better.
No fake accent, no PJ..just knowledge in the best descriptive way..
Excellent video..
Thanks for the comment 🙂
I am new to system design and I cannot explain how much this helped. Thank you very much, Sir!
Thanks for the comment 🙂
I watched many videos on elevator design, but your content and way of explaining is super awesome.
No one will get rejected in an interview if he can explain like this.
Very satisfied. Thankyou very much !!!!!
Thanks for the comment 🙂
I signed into my CZcams account just so I could tell you how useful this video is. Explained so clearly, thank you!
Thanks for the comment 🙂
Your info is really good. This information is very useful for those who have searched for this and you have great knowledge about this. I’m really impressed with this.
Thank you so much.
Thanks for the comment 🙂
High quality content. Better than other videos on CZcams
Thanks for the comment :)
Probably the best resource out there to learn LLD.
Nice video but you could have focused more on OOD as well. Like Button -> (Elevator Button, Hall Button) -> Elevator Button (Event Button, Floor Button) -> Event Button (Alarm Button, Fan Button, Light Button, Door Button). Here floor Button will only deal with floor functionality. Same for Fan, Door, Light etc button also. In this way SRP is not violated. Button interface can Have method like action(SystemInterface): void . Here SystemInterface can be extended by two classes ElevatorSystem and AdminSystem. for action methods under EventButton class we can prefer passing action(ElevatorSystem e): void and for HallButton we do action(AdminSystem a): void, bcz it deals on system to decide which elevator to sent on passenger floor.
great comments!
I think the reason that we used enum to represent the { idle, going up, going down} states is because the state space should be only limited to these 3, whereas in the parking lot example there could be many types of parking spots that can be added even after first version of design is done. In the parking lot example, we designed it to be flexible so that when other types of spots are needed, they don't violate the Open/Close principle, but in this one we want the elevator states to be closed and not modified later.
Correct. Thanks for the comment 🙂
@@ThinkSoftware thanks for this Video. Just a question to understand something: is a car full loaded not a state? or "out of service"? even "door open" is different than idle. If the car is full then it should not takes new Hall call... In case of a car "out of service": the dispatcher should not give hall call and "reload" the previous call to other elevator... So, I would like to know, if those example are not States then how do you advice to introduice it in the program? Thanks
I did not read all of the comments below, so maybe someone already mentioned this, but I believe a fourth elevator car state would be "out of service." Your videos are bringing together a lot of loose ends for me. Thank you.
Yes the video cannot be considered as the complete solution.
What an amazing explanation!!!!! Hats off to you😀
Thanks
I bow to your explanation and clarity. Thanks a ton. Extremely helpful
Thanks for the nice words 😊
At long last I was able to tackle the problem with some confidence. Excellent video. Thanks very much.
Thanks for the comment 🙂
Thanks for this video. I really enjoyed it!
Thanks for the comment 🙂
Thank You for this video.Was waiting for something like this.Its amazing.
Thanks for the comment 🙂
Thank you so much mate. Great Material.
You are welcome 🙂
Excellent , great video !
Thanks for the comment 🙂
Descriptive and clear explanation. Thanks
Thanks for the comment 🙂
Thanks for the informative video. Rally appreciate your effort.
Thanks for the comment 🙂
Learnt a lot from this video! Thank you!
Thanks for the comment 🙂
Thanks a lot for the video. Couple of questions
1. Do we need button class at all? Essentially we are creating InternalRequest and ExternalRequest when press ElevatorButton or HallButton respecitvely
2. For Button class , you drive ElevatorButton class and HallButton class from it. I think we should not have PressDown() in Button class as there is no equivalent in ElevatorButton . In real elevator buttons, there are only floor numbers buttons, help button, door open/close button etc but no up and down
PressDown() is not literally up/down function but a function called when any button is pressed. Recall javascript keydown events.
Great explanation once again!!
Thanks for the comment 🙂
Great video and explanation!
Thanks for the comment 🙂
One of best explanations for eleveator design. It was quite helpful.
Thanks for the comment 🙂
@@ThinkSoftware Bro why didn't you delve a lil deeper in the priority queue approach. Maybe that's the nature of how the interviews are conducted. Still a good job done
Thank you so much for this great content. I learn a lot from it.
Glad it was helpful!
It's a wonderful video, please make more of such videos.
Thanks for the comment 🙂
Nice and very informative video. Please make more videos on object-oriented design.
Thanks for the comment 🙂
Thanks for the efforts, very well explained.
Thanks for the comment 😊
very nice presentation..looking forward to more system design topics like airline ticket reservation or movie theatre
Thanks for the comment 🙂. More videos will be coming soon.
This Rocks! Not the evelator, but the presentation! I've been wondering about this since college. Now I'm in a five floor building, it all makes sense. What if a vip is coming home to your house in a suprise visit.
I don't see how divide and conquer would help in this scenario. Most people would go from floor 1 to the floor where they live and back. Very rarely you would see people going to other floors from floor x != 1. You could have them change elevator cars midway or so, but that is quite an inconvenience (and it would be very annoying if I had to switch 3 or more cars to reach my floor from the bottom). Maybe an adaptive system based on real-time traffic would work, or maybe a division based on functional areas of the building: office floors, living floors, cafeteria/gym floors etc, but that would entail a lot of extra complexity.
This gentleman is clearly an educator and a very good one at that!
Thanks for the comment 🙂
Thanks for this wonderful video! I always have problems finding the proper requirements for the system...
Thanks for the comment :)
i wish there were no elevator in this planet
I think you have not tried stairs going to a 10th+ floor building :)
@@ThinkSoftware😂😂😂 now he wishes there were no such tall buildings exid on this planet
@@ssmcs060 and it'll very soon boil down to "I wish there weren't this much population" or ultimately "I wish I wasn't"
I was expecting something like a UML's breakdown/discovery of classes, based on BEC architecture, Boundary, Entity, Controller objects per use-case. Like for example in your first use-case, 'calling elevator', what are the boundary objects, (buttons), entity objects (direction, destination), then a a controller object to carryout this use-case (which essentially responsible for the complexity of this 'calling elevator' use-case). I think your 'elevator system' object is interesting as well, its the dispatcher, may interact with per use-case controller objects, in this use-case to notify the progression of the elevator as it travels. Any thoughts on BEC driven oo design? Thanks.
Love ur videos. Tis is my reasoning for a person class / Car class.
A class is collection of DATA + FUNCTIONALITIES. Here a person has no direct functionality / data. hence no entity needed.
Thanks for the comment
Really Good Video,
Actually Elevator System Problem is really Complicated problem if we try to dive deep and think.
Thanks for the comment 🙂
Very nicely explained. Keep up the good work! Thanks!
Thanks for the comment 🙂
After a huge break, nice video with in depth explanation..
Thanks sir.
Thanks for the comment :)
Its very informative and helps to think about system and subsystems
Thanks for the comment 🙂
Great video! I love your explanations!
Thanks for the comment 🙂
Nice explanation and very well explained use of enum.
Thanks for the comment 🙂
waoo....!!! this is impressive. :)
Thanks for the comment 🙂
Thanks for the good content. One point here, no matter what others have covered on this topic, if you are creating a video on it, watchers get intrigued about how you would do it.
A complete UML diagram at least would make it a self sufficient tutorial. Also I didn't get why you need ElevatorMotion interface. How does it fit in between 1. dispatcher and Elevator, 2. Internal button and elevator itself.
That's why UML is important to know what is your design approach
Thanks for the comment
Awesome explanation of the algorithms! Thank you so much!
Thanks for the comment 🙂
> big tech companies
This question was asked in client interview which was the last round in wipro recruitment process. I wasn't prepared for that, in fact coming from a tier 4 pvt college i never came across such question. But I did my best, and that was great interview experience. Me and the interviewer both drilled down into elevators for over an hour.
Thanks for the comment
really wipro asked this much are you fresher ?
let say when in an idle state, the dispatcher gets multiple requests, in either direction, first, the requests will be divided into going up or down. the dispatcher will first see max no. of requests, and add them into a min-heap and send the elevator closest to the top person who is there at the heap, and will not be idle until the heap is empty now or if the elevator reached either endpoint.
Thanks for the comment. Which algorithm are you referring to?
Thanks you very much!
Thanks for the comment 🙂
I have seen practically, preallocate the elevators based on floor range and then apply the "Destination Dispatch Algorithm" based on the floor. This ensures Topmost going passenger need to wait due to some low-level floor passenger.
Thanks for the comment
Very informative.. 👌
Thanks for the comment 🙂
Could you please explain what the "Priority queues" are used for in the case of the SCAN algorithm?
Because if I already have in the tru array where the elevator has to stop, I don't understand what's in the queues.
Thanks
I was also wondering the same. May be priority queues (min heap for UP, max heap for DOWN) contain the destination floors which the persons inside the elevator might have pressed. Elevator checks these queues in order to drop the people.
For the last use case for dispatcher algorithm where the elevator is going opposite direction to passenger, how is it different from the state where the elevator is going opposite direction to which the passenger wants to go? Seems like the same state else we are more inclined to say that passenger is on floor 1 and elevator is moving to any floor which is > 1, the last state did not make much sense to me or I got it wrong.. do let me know..
14:30 How will you accurately represent the specifications mentioned at 5:24, such as elevator car load, passenger throughput, passenger waiting time and passenger distribution, if there is no passenger actor involved in the model?
You look like Ashish Nehra. Btw..Very Good Content
thank you for the video,
why you didn't use (or talked) about the state design pattern when implementing the states on the elevator (up, down, idle states) , instead of using Enums ?
is Enum more preferred ?
In this case, we know that we will only ever need 3 states (up, down, idle) and we will NEVER extend this functionality. So enum is sufficient, because we will never extend it.
32:43, very interesting. So just to clarify, the hashmap is to handle request made from inside the elevator car, correct?
Scan all floors from 0 - > N, when a button is pressed on a floor, mark the boolean as true
The elevator will move up and then down, it will change its direction when it reaches the 0th and nth floor
Use 2 boolean arrays for the up and down direction, stopping at floors marked true, then marking the floor true, (request served )
Each elevator car also has a hasmap to keep track of the floors it should stop at, adding floors requested and then removing them when request is served.
Thanks for the comment :)
i love you thank u very very very much !!!!!!
Thanks
Useful
very useful
@Thinksoftware please add some machine learning based system design questions such as ad prediction, search ranking etc. And how to approach these questions and how the requirements change for machine learning problems. Thank you
Thanks for the comment
Thank you Think Software, this was really nice. I've just one question, in SCAN algorithm why we need priority queues when anyway we are using two boolean arrays for going up and down ? As, array indexes are already sorted and we have to look at each index of the array whether its set or not. What is the benefit we are getting by using priority queues?
The boolean array is used only for passengers who want to onboard the elevators. So if it is set for a floor then an elevator will stop at that floor and reset the value. Then the two priority queues or a single hashmap (for each elevator car) is used to store the destination floors that passengers riding the elevator car want to go. The same boolean array cannot be used for this purpose.
@@ThinkSoftware why cant the elevator also use a similar concept and maintain boolean array for destinations? everytime it waits at a floor to drop off pasengers it can be change the array to false and change it back to true when at least one passenger sets that floor as destination. would avoid heapify effort
The first part was good but the algorithm part was confusing. And at no in this video did you mention about state of the elevators controlled by the people who are inside the elevator. There would be a number pad inside the elevator where people press the actual floor button. For example, 10 people get in the elevator on floor 2. One of them wants to go to floor 1 and 9 of them want to go floor 100. Essentially it has two key functions: elevator summon and passanger dispatch. You haven't attempted to make any distinction between the two at any point in this video
Before watching the video I was thinking something similar to LOOK ahead eventhough I never heard about it. I would try to do some combination of look but with timestamps along with booleans to decrease waiting time
Explained in a really simple way and to the Point. I would Like to know If Think Software Team has worked on Witness Horizon Software, as I am working on a Project to Simulate Different Call Strategies for a TWIN Elevator System.
Thanks.
I think even Doors would have hall and elevator implementations as when pressed hall button, the hall door should not open until elevator arrives whereas elevator door can open wherever its dispatched to. Am i right ?
all depends on the requirements and how you define the system
what would be the database choice for elevator system
I have a question regarding elevator system being a singleton, wouldn't we want ti be able to instantiate multiple systems in the case of multiple elevator areas ? which have their own schedulers and carts ?
Yes. And that what I mentioned while discussing zones. However, now implementation can be different. One way would be singleton elevator system has one or more zones and then rest of objects inside each zone.
Are the algorithms inspired from the OS Disk scheduling algorithms?
Yes. Scan algorithm is also popularly known as elevator algorithm.
Great as always. Is is possible make a video on 'how to identify actors', sometimes I get struck and ask "should this entity be an actor?", any help would be helpful.
Thanks for the comment 🙂
Very nicely explained !! A suggested optimization which I see is missing from every algo explained everywhere.
Since we know the max capacity an elevator can carry and if the current capacity is almost full, elevator should not stop to load more passengers :). Maybe assuming an average weight of 50 Kg(consider adults only), elevator should not stop if only 40-45Kg room is left.
thanks for the suggestion :)
While we analyze use case, should we think from user's perspective ? like you said in video, the elevator can open doors and close doors, but I think it is not from user's perspective, that is what elevators can do, not users. I'd like to know more about it.
Thanks for the comment. What would a user do in elevator control system?
How do we make our elevator program run continuosly, to accept requests via buttons. What is the industry standard way to do this?(Just in a way at http server listens for requests, But how do we do this for an elevator)
May be a topic for another video. In short, event driven architecture.
My big question is, how are all of these objects tied together to make it all work together ?
Are there really such questions on interviews out there? Puzzle is nice, but seems to complicated.
whats a great video
enums are used to define limited and fixed number of varieties which are impossible to get modified in future as well. For e.g. Days of week, Months of year In case of parking lot there are possible changes of introducing new Spot type in future which have needed modification of existing classes and that goes against the Open close SOLID principle. In case of Elevator type, the direction is never going to change. It can only be up, down or idle even in future.
thanks for the comment :)
Functional requirement mentioned the need to check for the max weight and number of passengers translates to the max weight.. I did not get what we would not need the passenger class in this design as the above are calculated based on passenger object attributes
Can I use two hash maps indirection and outdirection for Look Algorithm. Indirection stores entries of floors which are in direction of elevator car travel and Outdirection stores entries of floors which are in opposite direction to elevator car travel. Every operation can be done in O(1) time. Please correct me if I am thinking something wrong
It should be only two hash maps - one for up direction and other for down direction
@@ThinkSoftware why use a hashmap, we can 2 hashset to store the floors where elevator is requested. Once a floor is processed, remove it from hashset. At the end when hashset empty, reverse direction.
Which design parameters have you referred for the same, can you please get me name of the reference book with psg
well there is no book but 15+ year of my industry experience behind this :)
If passenger class is not used, how would we track total weight in the elevator as elevator has weight limit?
How passenger class will help to track weight? Weight will only come from weight sensors.
czcams.com/video/siqiJAJWUVg/video.html
For the lookahead in the LOOK algorithm, simply using a bitset is also a good option. 160 floors can fit into 20 bytes. We can test for each byte segment sequentially and from each byte one can access the digits with bit manipulation operations.
thanks for the comment. Such optimization are only need though if we are working on some embedded system with way less memory than the memory that is currently available in current computers.
Sorry but, Elevator are build with embedded system, for reason like: price and ... no risk of Win 10 update while the Lobby is couded :-) Regards.
Make a simple video on selection of motor capacity and loading of car to have energy efficiency
Thanks for the comment. This is out of scope of this channel.
thanks for the video it helped and can you describe the logic of how to find the last number of the floor visited in the case of one elevator car system?? even in code it would be ok in java e.g isPressed(); in details
Thanks for the comment :) there are different ways to achieve this. E.g. one way would be to use a queue for this purpose
This shows that you already know about elevator. Also there is no implementation. I would like to see requirement -> implementation. Refine requirement, refine implementation,
Nice video....So these are basically disk scheduling algorithms
Yes..sort of.
Do you have full course in System design ? Kindly guide me to such material or course you know in addition to your videos
You can check out my course on System Design. Link is in description. The course is not complete and still working on it and that is why if you buy now you will get lifetime access. Once course is complete, I will switch it to yearly subscription for new users.
Let's say if the elevator system is out of order then shoud we add this state in the Enum only.
I dont understand how enumerations in Parking lot would break code reusability. We just have to add a new Enum type to the end of the array and use that enum, rather than change if else clauses isnt it ? Or am i wrong ?
You should read about open close principle.
Can you make video on FPGA based Elevator controller...with small lift demo using motor
FPGA based elevator controller might be off-topic for this CZcams channel.
Now a days elevator system moves horizontal also so we should have class and not enum for the elevator's states, just a suggestion :) But overall video is good. Please make a video on elevator's class diagram also
thanks for the comment
One of the usecases could be ++ weight is more than assigned..automatic door open with voice/beep..
Thanks for the suggestion
If I divide in 4 zones for elevators. How will I go from 3rd to 27th floor.
in that case there will be few common floors between zones.
Without passenger object, how would you determine the available capacity of Elevator ?
You don't need passenger object for that. How will you even know the weight of each individual passenger? You will just keep track of total weight provided to the elevator by weight sensors
Where is the class diagram if this is about OOPS
Come up with classes & method
we need passenger class if we are having maximum load property for elevators.. Each person will have some particular weight that we need to take care of.
How would you know the weight of each person?
How we handle Service Mode of the Elevator Car?
what do you think?
Dont we need to consider the weight of the passenger? The total weight of passengers should be less thn threshold. I feel we need passenger object
There is a whole section about elevator maintenance that you can get into
Thanks for the comment