Parking Lot Design | Grokking The Object Oriented Design Interview Question
Вставка
- Опубліковано 19 чер 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 🙂.
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 UA-cam 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
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
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 🙂
You are so thorough, clear, and simple at the same time. Great effort. Keep it up
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 🙂
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 😊
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.
Best approach to a systems design/oop question I have seen so far!
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 🙂
The special guest appearance made me feel guilty about even thinking about leaving without liking! Great content. Thank you
Thanks 🙂
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 🙂
Best Design Pattern Video I found on youtube. No nonsense, crisp and clear! Thank you sir
Thanks for the comment 🙂
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 very much for this great video! It helped me prep for my code design C++ interview:)
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 🙂
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 🙂
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 🙂
so impressive guest appearance , her glance was too amazing !!!
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.
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 🙂
absolutely precise, the art of bringing design patterns into real practice while solving the problem. Great content and explanation.
Thanks for the comment 🙂
love to watch ur designs with creation/structural/behavioural patterns. thank u so much
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 😊
I loved the way you used the Design Patterns while designing the system.
Thank you for the video.
Thanks for the comment 🙂
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.
Thank you so much for your video. It helps me a lot with my final project on campus.
You are welcome 🙂
Very clear and helpful. Thank you for making this video!
Thanks for the comment 🙂
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
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 🙂
Never went to a parking lot where the spot was assigned at entrance. Just my 32 years experience though. Good video btw!
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 🙂
This is the clearest and concise description ever!! Thank you so much. Please do more if you can!
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
she was sooo cute!!! after watching 27 minutes of this video, appearance of her was mind refreshing :). Great content.
Thanks 🙂
We all love you and your cute little special guest !
Thanks for the comment 🙂
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.
This is one of the best videos on system design. Loved it sir. Extremely impressed.
Thanks
best source I have seen so far Thanks a ton
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.
Need more of these! loved it
Thanks for the comment 🙂
Simply wow. Excellent explanation. Please continue to make such videos. Thank you for your time.
Thanks for the comment 🙂
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.
Very well explained. Video is extremely well organised and trimmed. Thank you so much.
Thanks for the comment 🙂
Crisp and clear system design. Very great work. Keep it up 👍
Thanks for the comment 🙂
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.
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.
Love your especial guest. Awesome teaching video, I learned somethings.
Thanks 🙂
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.
It was very good and clear explanation, Thank you
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
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 🙂
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.
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.
Thanks. It is very useful.
You have showed in the demo that how the System Design, OOD, Design pattern, SOLID Principal and Data structure can be applied. It would have been good that this video more granular level on the each topic.
Thanks for the comment 🙂
This is so genius. Thank you so much for your tutorial. That ending tho 🤣🤣🤣
Thanks for the comment 🙂
Really helpful :) Thanks. Please make more videos on OOD interview questions.
Thanks for the comment 🙂
Very instructive, thank you!
Thanks for the comment 🙂
The special guest's tips at the end were motivating .. thank you :) 🥰
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 🙂
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 🙂
Thanks a lot . You are a good teacher.
Thanks for the comment 🙂
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?
Nice video, sir. Please make more OOD videos in future. Looks like special guest has already started to code in Machine code !!
Thanks. Will make more videos.
Great Content! Would Love to see more of this. Thank you Sir.
Thanks for the comment 🙂
That's an awesome video. I was once asked in an interview to design a "Cricket Score board". I wish I had this material back then. Could you please give it a try. Would love to see how your approach
thanks for the comment :) will do.
Very good explanation. Thanks for your effort.
Thanks for the comment 🙂
It's a useful video on handling and understanding the problem. It could be more useful, if we have complete code to have an idea of "how to write code and apply design patterns". Thanks a lot for these videos.
Thanks for the comment 🙂
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
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 my opinion getParkingSpot() should take ParkingSpotType along with the Terminal as parameters because we need to know what type of vehicle(compact, large, motorcycle) is coming in parking before assigning it a spot.
Also, getTicket() should take ParkingSpot which was returned by getParkingSpot() above as Parameter instead of ParkingSpotType because the ParkingSpot will have all the required info to be printed on the ticket than just the ParkingSpotType.
Overall a great video, thank you for the clear explanation.
Thanks for the comment 🙂
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
Very useful. Thank you
waiting for more content.Best OOD videos. Please make some more on this topic.
Thanks for the comment 🙂. Will see.
@@ThinkSoftware Please make more content on Object oriented Design please
extremely clear and precise
Thanks for the comment 🙂
Awesome content! Thank you.
You are welcome 🙂
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.
very well elaborated esp when compared to others.
Thanks for the comment 🙂
I think for solving the parking spot that is closest to the entrance and a elevator, I can define a specfic data type for putting into the min heap. For example, , the min heap defines the judgement condition can be :
return o1.distance_Entrance < o2.distance_Entrance && o1.distance_Elevator < o2.distance_Elevator ? -1 : 1
Great video! It does get harder to focus at around 50% but that can jut be me
Thanks for the comment.
Great explanation. Please make more object oriented design videos.
Thanks. Will do so.
Hi, great work! Could you please elaborate further on enums and OCP ? Also where can I learn this stuff ?
Thank you. I liked your approach to the question and also, how you mentioned the different design patterns. May I know how you made the design decision to create a simple class and when u decided to create an interface?
Thanks for the comment. You usually talk in terms of interface until you need to have some specific implementation where you then talk in terms of class.
Loved this video. One thing I didn't understand is how we can efficiently remove a parking spot from the min heaps for the other terminals? It likely won't be the closest available spot to the other terminals so it won't be the root of the min heap.
Thanks for the comment 🙂. We have discussed this already in several other comments
This video is explanatory and all the concepts are linked together. Very well explained. Although it is not scope of this video but until it is visible at code level how to implement it , it does not give confidence.Is this possible to created more detailed video on OOPS and how to decide the data structure use for solving a problem.
Thanks for the comment 🙂. Will look into this.
minimize ( sum of distance from door and each of the elevator ) means final distance will be the distance of parking lot from door plus min(distance of all elevator from the parting lot)
amazing video, thank you a lot .
Thanks for the comment :)
great video not many videos like this on internet, Please make more Videos like this
Thanks for the comment 🙂
Super helpful!. Thank you so much, sir! I have a question here. I saw some online resources mention the use case and user activity analysis. What do you think of these? Are they part of the requirements collection?
Yes they should be part of requirements collection
Very informative video, thanks.
I think we could aldo add a requirement regarding the parking lot being either "long-term" or "short-term"?
The video is super helpful. Thanks. :) Would it be possible to have more object oriented design related videos?
Also any resources if you would recommend for OOD and Design patterns would be helpful
Thanks for the comment 🙂. I will try to come up with more videos. It is just a matter of time. Currently I am busy in working on my book so didn't get much time to produce more videos but once the book is launched I will have more time. As far as resources are concerned, I don't think there is any single good resource. You might have to read from multiple places and still try to make sense of it. Might be another idea for my future book 🙂
This is good you create curiosity what could be done to fix, what could be done to optimise.. Good teacher does not provide the exact solution they lead to that solution
Detailed and well explained! Thanks for sharing
Thanks for the comment 🙂
Awesome content and great explanation. Please make a video on basic OO design patterns.
Thanks for the comment 🙂. Will look into this.
We can use BFS algorithm to find the nearest free spot in our building, for that we should define our building and floors as matrix
It all depends on the requirements.
Hi! Thank you for this video. I am not sure I understand why using an enum for the Parking Spot type is a bad idea? Everywhere I've worked enums were widely used to describe the type of an entity