Parking Lot Design | Grokking The Object Oriented Design Interview Question
Vložit
- čas přidán 9. 07. 2024
- Parking Lot 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 the System Design interview question about designing a parking lot 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
03:15 - Requirements Collection for Parking Lot Design
08:00 - Mistakes to avoid during requirements collection
09:35 - Use Design Patterns for Object-Oriented Design for Parking Lot
10:20 - Top-Down and Bottom-Up design approaches
11:15 - The right way of identifying actors and objects in the system
13:20 - Detailed System Design of Parking Lot
26:35 - Final Remarks
27:28 - Special guest appearance
Distributed System Design Interviews Bible | Best online resource for System Design Interview Preparation is now online. Please visit: www.thinksoftwarelearning.com?
How To Ace Your Object-Oriented Design Interviews: / how-to-ace-object-orie...
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
Please let me know if you find this video useful. 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.
Sir, I had a question...are we only expected to tell these requirements in the interview when they ask us to build parking slot system in oop design interview? Sir, plz make more videos on oop design
Thanks for the comment 🙂. Are there other requirements that I have missed?
@@ThinkSoftware I am third year student and I am going to appear for interviews this year. I am learning how to get prepared for system design interview. So basically I have no idea about it so...
This should be sufficient.
sir make video on elevator design for high rise building
I really liked your approach to the problem. You not only considered the different design patterns(which is very rarely seen in other videos, blogs) into consideration but also specifically mentioned that we do'nt need the vehicle class for the parking lot design. Thanks for such an awesome video. I am hoping for more videos on OOPs in near future.
Thanks for the comment 🙂.
For the 'entry/elevator distance' issue, I think we should keep using the MinHeaps and only change the 'distance' calculation. We can for example take the sum of distances from the parking spot to the entrance and to the elevator.
Thanks for the comment 🙂
This is one of the best approaches compared to other videos. Just focusing on problem and concepts around it (actors, design patterns, etc.). Instead of over-complicating system with 'scalability' bringing in architectural patterns like micro-services unnecessarily. Thank you!
Thanks for the comment 🙂
I think sometimes the interviewer wants the distributed systems approach though
That's really the crux of the problem statement. What's being described here is how to approach a Low level design (LLD problem), which should be carefully differentiated from a System design problem, that's more of a high level architecture design (HLD problem). That being said, the candidate might still be asked to delve into some of the core algorithmic aspects of a specific flow even in a typical system design/HLD interview.
Thank you a lot for referencing what others do in their system design CZcams video's and saying how it could be improved or why it's wrong. I bought your course and that is what really sets it apart. I'd guess it would be very impressive to any interviewer if you were able to argue why what most people do is actually not optimal and present a more optimal solution. Thank you so much!
Thanks for the nice words and for buying my course :) Please do let me know do you find the course useful and if you can also provide a review, I will really appreciate it. Thanks again.
@@ThinkSoftware please provide your course link and purchasing details.
The link is in the description.
Definitely one of the cleanest design videos. Just what's required in an LLD round.
Thanks for the comment
The special guest appearance made me feel guilty about even thinking about leaving without liking! Great content. Thank you
Thanks 🙂
Best approach to a systems design/oop question I have seen so far!
Thanks
That's the best video I've seen for OOD approach. It does make sense to ask question from interviewer on some superficial requirements like fetch no. of vehicles with a particualr color.
It helped in clearing basic fundamentals of ODD. Keep doing the great work .
Thanks for the comment 🙂
Best Design Pattern Video I found on youtube. No nonsense, crisp and clear! Thank you sir
Thanks for the comment 🙂
thank you so much and your daughter just melt my heart after being stressed for an entire month about my amazon interview!! she is so cute!!
Thanks
This video is by far the best system design Video I came across. This video is exactly what one really needs to know.
Great work
Thanks for the comment 🙂
Great Design !, Since PQ doesn't support random access to delete.
In my opinion, We can achieve this efficiently it using 3 data structures.
Map -> stores each terminal's min-heaps.
Map -> to keep track of the elements present in priority queue.
Set -> tells us PS which are reserved currently. amongst all the parking spots. (global)
Algo for Entry :
> get the terminal Id and associated min-heap.
> while(parkingSpot is reserved) {
pop it from Priority Queue as well as the set which keeps track of our PQ.
}
> if PQ is empty -> no parking spots left.
> get min distance PS finally.
Algo for Exit :
> get parking spot.
> release it from the reserved set.
Iterate though the terminal's PQ.
check if PS is not present in the current Terminal's set.
Insert that parking spot. in current terminal's set as well as PQ.
Please correct me if wrong. Thank you.
You are so thorough, clear, and simple at the same time. Great effort. Keep it up
Have watched many parking design LLD videos - none gave me that confidence. Finally found the perfectest video - I can RIP now
Thanks for the comment 😊
Great video sir! Making life simple for many of us. System design is something which was never covered in colleges and yet is an important component of interviews in majority of the companies. Your explanation is amazing. I thoroughly enjoyed the video. Thanks :)
Thanks for the comment 🙂
Agree with everyone else who commented - great and thoughtful content, really knowledgable. I read books, took courses and tried to design stuff by myself Big "thank you" for the most helpful resource online I have found so far!
Thanks for the comment 🙂
In the parking ticket, the vehicle registration number should be recorded as well. That will have following benefits:
- You can't exchange/steal anyone ticket. While exiting, it would make sure that the parking ticket was really assigned to this vehicle.
- At any given time, the parking system would be able to tell if a vehicle is still parked or left and at what time. This would help in tracking abandoned/stolen vehicles.
Thanks for the comment
A very good point
This is the best system design video available. I tried to look multiple videos, but this is the actual informative video covering every bit. Thanks
Thanks for the comment 🙂
@@ThinkSoftware Using 4 min heaps for 4 entrance. Now if a spot is booked at one gate, we need to mark booked in other remaining 3 min heaps, but heaps only support sequential access. Do you think It will be more efficient if we save all parking spots in doubly link list. Then 4 min heaps can be maintained where key will be distance from that entrance and value will be address of that spot in doubly link list.
Thank you for amazing video ! I have one quick question. Initially, we decided that there can be multiple types of parking slots like Handicapped, motorcycle, largeVehicle, SmallVehicle etc. So when we define getParkingSpot method, we have to give terminal and parking spot type as parameters like getParkingSpot(Terminal,ParkingSpotType). We have to define map of entrance and min heap of parkingspot for each entrance as well as parkingspottype. Like Map, Map etc.
Very clear and helpful. Thank you for making this video!
Thanks for the comment 🙂
so impressive guest appearance , her glance was too amazing !!!
thanks for the comment :)
Need more of these! loved it
Thanks for the comment 🙂
Thank you very much for this great video! It helped me prep for my code design C++ interview:)
Best video on the topic so far. The whole vehicle hierarchy thing hits right at home. I was wondering why everyone focused so much on it.
Thanks for the comment 🙂
We all love you and your cute little special guest !
Thanks for the comment 🙂
absolutely precise, the art of bringing design patterns into real practice while solving the problem. Great content and explanation.
Thanks for the comment 🙂
Nice video, very insightfull. To deal with the distance to entrances and elevators i would consider using a scoring function, give each parking spot a score based on distance to current entrance and nearest elevator. You can also use more scoring factors, for example distance to exit or in a multi-story building, give a better score to the lower levels. Such scoring function should work well with your heap-based approach. Great content!
Thanks for the comment 🙂
very well put together.The video is really underrated and underviewed .I can't imagine a better solution and approach for it.Amazing content and Superb Explanation.Would like to see more of these kind of videos.
Thanks for the nice words 😊
Can you please do more questions on Object-Oriented Design? I see there are a ton of resources on system design and DS & algos but there very few resources on Object-Oriented Design questions. And I see that one of the valuable resources is you.
Yes will make more videos on Object oriented design as well in future.
The explanation is quite clear and crisp, please make more videos on Object-Oriented Design...
Thanks for the comment 🙂. Will make more videos on Object oriented system design.
@@ThinkSoftware Please make more videos on Object Oriented System Design. There are enough HLD teachers on YT. You explain LLD really well
Simplified the system to implement easily. Well done
My mentor always used to say, a good code is one which doesn't need to be written
Exactly. BTW thanks for the comment 🙂
Love your especial guest. Awesome teaching video, I learned somethings.
Thanks 🙂
This is the clearest and concise description ever!! Thank you so much. Please do more if you can!
Thanks for the comment 🙂
I loved the way you used the Design Patterns while designing the system.
Thank you for the video.
Thanks for the comment 🙂
I think there is an error in the complexity of the algorithm that reserve the parking spots. The operation of remove the parking spot from the current min_heap is effectively O(log(n)), because we are removing the minimum value of this heap. But this removed parking spot, is not necessarily at the top of the other heaps, so removing it from the other heaps will costs O(n), because you will need to search the element in the entire heap. And this is ignoring operations with the available and reserved sets. Except this, I think you made a great video, thanks a lot!
Thanks for the comment.
For this one, you can just use the available set to check if it is available and remove it from the front it if it is not. Since the total number of nodes is 4n, the amortized time complexity for removal is still O(log(n)).
Four AVLs could also solve this problem.
what we can do is as each parking lot is assigned an id...each heap will be handling a certain range of parking lot rather than all 4 heaps handling all parking lots. and when the vehicle exits according to the id assigned...the free parking space id will be assigned back the heap which is handling it.
Yes, this approach is better since we know every parking spot is nearest to only one entrance. Redundancy is avoided.
love to watch ur designs with creation/structural/behavioural patterns. thank u so much
Thanks for the comment 🙂
Very helpful, thanks for sharing this explantation! I have a better understanding of how to approach object-oriented system design now. Looking forward to learning more
Thanks for the comment 🙂
Very instructive, thank you!
Thanks for the comment 🙂
My two cents:
1. We can also consider the whole parking lot with terminals as part of a graph and by using BFS we can find the closest parking spot from terminal.
2. if elevators are introduces then once solution could be introduce 4 min heap for each entry terminal which will have parking spot distances based upon terminal distance with elevator. Each terminal can have array of size four based on elevatore distance with terminal. pick one elevator from array then check it's respective heap, if all are not available then check another elevator from array and so on.
PS: I really enjoyed your video. Very helpful.
my take: 2. I elevators are added we can keep the original min-heap setup but arrange the min-heap, instead of using spot-terminal distance, use a custom score-based min-heap e.g. (terminal, spot, elevator) score which can be something like abs(dist(terminal, spot) - dist(terminal, elevator)) -- the lower the score the best terminal-elevator range.
Thanks for the comment :)
What if you used the following minimizing/scoring function instead: w1*dist(term,spot)+w2*dist(spot,elev), where w1 and w2 are the weights you assign to the driving distance to the spot from terminal, and the walking distance to the elevator from spot, respectively. The weights you assign can be based on the expected speed, maybe 15 for a car driving to a spot, and 3 for a person walking to an elevator. You can pre-calculate all the scores for all (terminal, elevator, and spot) triples and cache them for quick referencing, since you wouldn’t expect this to change often.
Very helpful. Simple, brief and to the point. Basic oop concepts and design pattern nicely covered on the go. Keep it up. Hope to see more videos on different system design topics.
Thanks for the comment 🙂
Very well explained. Video is extremely well organised and trimmed. Thank you so much.
Thanks for the comment 🙂
best source I have seen so far Thanks a ton
Thanks for the comment 🙂
Simply wow. Excellent explanation. Please continue to make such videos. Thank you for your time.
Thanks for the comment 🙂
This is one of the best videos on system design. Loved it sir. Extremely impressed.
Thanks
When we decide to use min heap, does it mean we have to keep all the data in memory all the time ?? Will this be a concern if data is big..if so what shall be done in such scenarios
Thanks for the comment. How much big the data will be for the biggest parking system in the world?
A very real problem with assigned parking spots is that not everyone will park in their assigned spot, either because of making a mistake or deliberately! This should be a core or essential use case. Thank you for these informative videos.
Yes that could be discussed during requirement collection phase and would change the solution.
she was sooo cute!!! after watching 27 minutes of this video, appearance of her was mind refreshing :). Great content.
Thanks 🙂
Awesome content! Thank you.
You are welcome 🙂
Thank you so much for your video. It helps me a lot with my final project on campus.
You are welcome 🙂
Loved the video. To tackle the elevator part of the question, my understanding is we can continue to use a min-heap here too. Difference is instead of creating a min-head with entrance of the parking lot as reference we create a new min-heap with elevator as reference. The logic here is most people would like to find a parking spot closest to the elevator.
Thanks for the comment
Think Software, please let me know if my line of thinking is correct?
Yes it is correct and also depends on what requirements you set.
Think Software thanks for clarifying.
Crisp and clear system design. Very great work. Keep it up 👍
Thanks for the comment 🙂
You need a hashmap in addition to each heap. At the very last step you mentioned that the selected parking spot should be removed from heaps corresponding to "other" entrances. Heaps don't provide random access in O(log(n)). The algo would be the following then: store all in a hashmap by id per each entrance, get the optimal spot from the current heap, get distances that correspond to each entrance by the spot id from hashmaps, remove the spot from each heap using its distance. There is also a chance to have equal distance for two different spots, they could be handled with linked lists for duplicates.
I may have to make another video to explain this. I replied already to few other comments that in the heap you store pointer to a node that itself comprises of following:
Node {
Node*listOfPointersInEachHeap;
int distance;
ParkingSpotEntry *entry;
} where Node is
ParkingSpotEntry {
ParkingSpotId id;
...
}
So, once you get the NodeWrapper from one heap, you don't need to search for that parking spot in other heaps. You already have pointers to nodes in each heap and so you can directly remove the node from other heaps.
@@ThinkSoftware how would i do that in java?
In order to implement, Nearest Parking spot from Entry and Lift: Probably I still use priority Queue but with comparator , (Lift Distance followed by entry spot distance)
Priority queue is used to implement min and Max heaps based on comparator
Best video seen so far on OOD! Keep Sharing! Thanks!!
Thanks for the comment 🙂
Very helpful. Thank you for detailed information 😌
Thanks for the comment 🙂
Very useful. Thank you
Seriously, one of the best explanation with such simple words.
1. What I liked the most is that you are telling us what design patterns is used while designing those classes.
2. Explanation was crisp and to the point.
However, if you could please share the notes of implementation of these designs (specifically mentioning what component is using which design pattern) that would be really great. Really looking forward to some more videos on OOD design.
Thanks for the comment. Yes there will be more videos coming. Currently busy with my course launch.
This is so genius. Thank you so much for your tutorial. That ending tho 🤣🤣🤣
Thanks for the comment 🙂
I want to leave just a few comments:
- the overall video quality and content are excellent, and the explanations were straightforward and clear. are you a teacher?;
- not even once databases were put into the table, and systems used to have them for obvious reasons, and the proposal seam to handle everything in memory without databases;
- the video discuss top-down and bottom-up approaches and choose the second as the right one, but actually, there are 2 types of system design interviews placed by FAANG companies:
- component design (focused on OOP, SOLID, design patterns, code standards, best practices, maintainability, and usually placed to not-senior positions);
- system architecture design (focused on high-level system design, architectural discussions, scale and distributed system problems, placed for more senior positions);
- the video targeted only one option, assuming that this is what system design interview stands for, but in fact, the hiring team defines which one to apply depending on the seniority of the opening.
- The tips for picking the proper requirements were excellent.
Thanks for the comment 🙂
Great video! Viewers, note that the approach is not sufficient for the given use case. If we have a min-heap for every entrance, we can fetch the nearest parking spot. However, we also have a size constraint. If you have a car, you cannot park it in a spot for a motorcycle.
Thanks for the comment. Yes you need different heaps for different parking types.
Very Well explained, I guess the use of Vehicle class would be that it will store the vehicle no and the contact details of the vehicle owner, Since at a particular time a person will only be associated with only one vehicle, which will be used in many conditions such as searching for a vehicle or contacting the owner of the vehicle.
Great Content! Would Love to see more of this. Thank you Sir.
Thanks for the comment 🙂
Love this video
Thanks for the comment 🙂
Thanks a lot . You are a good teacher.
Thanks for the comment 🙂
amazing video, thank you a lot .
Thanks for the comment :)
Wow man! Just wow
Thanks for the comment 🙂
extremely clear and precise
Thanks for the comment 🙂
Very helpful.Loved the design and reasoning.I wish you do a follow up video that delves to some extent onto the instantiation of objects using factory patterns.
Thanks for the comment :) Will look into this.
The special guest's tips at the end were motivating .. thank you :) 🥰
Thanks for the comment 🙂
Brilliant Explanation! :)
Thanks for the comment 🙂
this is a very well described approach, you need more subscribers for sure. lol the kid at the end ...
Thanks for the comment 🙂
Nicely explained. Further, we can tag the parking spots near elevator(pre-processing, to be assumed) & modify the comparison algo for priority queue(s) to prefer these tagged parking spots over others.
Thanks for the comment
Very good!
It was very good and clear explanation, Thank you
explained very well and so easily
Detailed and well explained! Thanks for sharing
Thanks for the comment 🙂
Hello, thank you for the video! I wanted to ask, why do we model different types of parking spots (e.g. handicap, compact, etc.) if the assignment of cars coming in to a parking spot does not seem to consider the type of car that should match the type of parking spot?
Very good explanation. Thanks for your effort.
Thanks for the comment 🙂
Great video, to deal with the distance from parking lot to entrance and elevator, my idea is that we can still use same old min queues, but adding the distance to elevators, like this: V = x*distance_to_entrance + y*distance_to_elevator. and put V in min queue
x, y is configurable parameter, if we prefer to be near elevator, y will be bigger than x, if preferring entrance, x > y, else x = y
Thanks for the comment. Yes that is one way based on requirements.
Never went to a parking lot where the spot was assigned at entrance. Just my 32 years experience though. Good video btw!
It was Awesome!!
Thanks for the comment 🙂
Great explanation!
Thanks for the comment 🙂
Really helpful :) Thanks. Please make more videos on OOD interview questions.
Thanks for the comment 🙂
Could you tell me the purpose of the getID()function in Terminal? What is the input and return type of the function?
Tender explanation Thx.
You're welcome
Amazing explanation. Stumbled upon this video by accident, happy that I did. Thank you :) Please make more OOD videos
Thanks for the comment 🙂. Will make more videos on OOD soon. BTW have you seen other videos on my channel?
@@ThinkSoftware i am loving it .make more such videoes on ood
Thanks
Just wow.. 👌👌
Thanks for the comment
We are keeping the min-heaps and free/reserved spot-set in memory. what happens when the system reboots/power failure? how can we build the current configuration in the parking garage?
This was out of scope of this video but to answer your question, in that case, we can't rely on simple in-memory data structures. We need to then also save the state on disk and in case we want to avoid disk failure, we would need to also replicate the state.
Great video!
Thanks for the comment 🙂
Great content!
Thanks for the comment 🙂
Great work man..!
Thanks 🙂
why is it problem to add new type in the Enum? Why would we need to change anything in the code besides the Enum itself? Is it because some specificity of C++ lang?
very well elaborated esp when compared to others.
Thanks for the comment 🙂
What is top-down design you mentioned at 10:31.If bottom-up design starts with object oriented design then what does top-down design starts with?
Thanks for such a nice and detailed explanation. PLease upload more video on System Design such am MMT , UBer etc.
Yes will be uploading from time to time. Also I already have a video on Uber System Design. Haven't you check that yet?
Like your videos..... great content :)
Thanks
when reserving a parkingSpot your getParkingSpot(Terminal terminal) method takes only entrance terminal as parameter, shouldn't it consider parkingSpotType[large/compact/hadicapped] as parameter also?
There is a reason I left it. I plan to create a course on object-oriented system design and will discuss this in that.
Thanks for the session. If the usage of enum violets the Open/Close principle here, then where do we use them ?
Thanks for the comment. In reality, the software we produce is far from the ideal practice. The enum were present in the language constructs way before the introduction of the Open/Close principals in object-oriented design. Also I am going to upload video on elevator system design soon in which I will discuss this as well.
Hi,
how you deal with different types of parking spots with those 4 min heaps?