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
@@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...
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.
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!
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 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.
Thank you a lot for referencing what others do in their system design TH-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.
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 .
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.
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.
@@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.
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!
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)).
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.
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!
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 :)
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.
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.
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.
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.
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.
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.
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!
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.
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.
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.
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.
This was a good video with clear and concise information. I just wish you would remake the elevator system design video without the divide and conquer approach and consider each lift to service all floors.
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.
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)
no satisfactory solution for multiple elevator system design is available on net, can you fill the void? Also, if rough text notes are available then post that too else may be write patterns used on board on respective model, that way revising just before interview one can simply slide through screenshots instead of whole video. Was asking for rough text notes only if you already have, so that making ankii cards out of it would be much effortless. You are doing good job with videos, I can precisely guess many times what solutions of others you are criticizing, paid or free most are simply not acceptable in interviews for fang. I have answered one for parking lot from net and simple got rejected.
Thanks for the comment 🙂. Yes I will make a video on elevator system design soon. It is just a matter of time. Regarding rough text notes, this is where I am writing a book which will have more detail information and also can be quickly go through if needed during interview preparation.
I got this question once in an interview and it went very poorly - I couldn't figure out what the interviewer wanted me to do! Thanks for this video because it showed me what the interviewer actually wanted, and helped confirm my hypothesis: this question is nonsense (FWIW I did get the job, but am still salty about this question). The first thing I asked the interviewer was: "what software is being developed? Is this for a game? Is it an API that runs on some on premise server or some cloud service? If so what API calls do the hardware make?", etc, etc. He couldn't answer, instead kept asking me to design a class diagram. I don't think that is reasonable. In real software you need to know what the input and output of the programs you are writing are before you can meaningfully decide on any of the internal structure. For instance, your class diagram would look wildly different if the software were powered by a relational database and request/response model vs a persistent set of objects being simulated in a game engine. Or maybe the program just accepts a flat csv file of parking spots and returns the closest available spot from a certain entrance. If that were the case, you could solve this easily with a very simple data model and no design patterns at all. As an industry we need to stop asking questions like this, and focus on real world problem solving. Also I don't mean to be critical of your video - you weren't the one who started this trend. But when I look at the answer to this interview question, all I see is an empty shell of an architecture that serves no purpose and solves no problem.
for 22:00 problem , we can use two way BFS. Because we have two sources (one is Entry Point and Second is Elevator), and we have to find destination such that it should be minimum w.r.t both. Therefore, applying BFS in both sources and whenever they meet at a point and parking slot is empty, this will be the minimum distance w.r.t both.
If the slot is not empty , then I think we should continue searching further, because what if after having non-empty slots we get a empty slot. For example:- If my entry point source has already traversed from some empty slots, and when Source 1 meet with Source 2, it is having non-empty slots, so if we traverse further then there is a chance that Source 2 will reach to a empty slot that Source 1 has already traversed. So, we can take a set in which we will keep track of slots, in which Source 1(Entry point) and Source 2(Elevator point) has already traversed. And , yes we will be consuming a lot of space (Queue and unordered_set)😶 . That's what coming in my mind to solve this problem. Well, I'm relating this problem with LeetCode:- Word Ladder in which I've used two way BFS to solve this problem. There, might be a better solution to solve this (Entry and Elevator) problem.
I liked your video, that you have not considered the Vehicle class. 1. Initially, you mentioned, not going to use ParkingSpotType, but you have used that many times 2. In ParkingTicket class what is the use of ParkingSpotType, that we can get from ParkingSpotId I think you are using ParkingSpotType enum as well apart from ParkingSpot class. You should consider discussing factory/builder design patterns to create objects of ParkingSpot
21:25 complexity of removing top element in min heap is log(n) but for other 3 heaps we will have to search for parking spot to be removed and hence complexity for them will be O(n). Hence overall complexity will be (k-1) *n not k*log(n) as mentioned in video.
in each minheap you store a node which stores the parking spot along with pointer to the nodes in other minheaps. So you don't need to search the node in other minheap and have to directly remove the nodes from other minheap resulting in O(log n)
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.
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 video. Have a couple of questions - 1. Where will the heaps reside If we have different strategies of assigning the parking spot which class owns state. If state is in the parkingSystem class will we pass state to the strategy ? 2. Do terminal class own any state ? 3. Which class will imitate payment ?
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
Overall, good explanation. However, the parking spot near entrance strategy solution probably require further thinking. 1. If four cars enter from four entrances at same time, how to synchronize the avaible spots? I don't think four mine heaps here would make things easy. 2. Building a heap is O(n), pop root opertion for min heap is O(1), and remove a particular item from the heap of other entrances require O(n). 3. How to find the parking spot not only available but also match the parking spot type? I believe singleton arrays + sorting algorithms should be more suitable for this.
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
If you have a separate minheap for each entrance, you will have to remove the spot from each of them when it’s occupied. The search of the element is O(N) as minheap only makes sure that the first element is the smallest and that each father is smaller then both of its children, but there is no internal order between elements. I would just have a linked lists for each of the entrances and add links for each of those lists to my “parking spot” . So when it’s used, just unlink it from all lists, when user frees the spot, add it to all lists, that would be O(log n) using binary search.
For unlinking node,when its used, won't that take O(N) time,? and when user frees spot, and adding it to all lists, How TE is O(logN) means how can you apply Binary search on linkdlist?
@@rameshsapphire7945 I meant double linked list, to unlink it double linked node is O(N). And for binary search you are right, my bad, it can’t be applied to a linked list. Need to think about a different solution...
@@irinairina131 how about using heap as he told and maintaining its indexes in a separate map? Since the inserted node values are uniques, we can store them in map and it's indexes, and when deleting node in heap , the other nodes indexes change, so then can we update their indexes as well in map while modifying the heap..?
Thinking up loud, as the distance between the parking lots and entrance doesn’t change, we can have a double linked list of all existing spots for each entrance arranged by the distance. When we have to add a spot, we go from the spot checking closest spots one by one , once we find it, we know after which spot we need to be added to the “available spots list”. Complexity is O(d) where d is the number of closest spots occupied, so in the worst case is O(N) ... looks messy 🤪just thinking of different options...
If I were interviewing with you and you gave me this problem, I’d ask my role: architect or developer. If my role is developer, your response is great. But if an architect, I’d stop you after collecting requirements to point out this system is insane and will fail because the requirements assume human behavior that fails irl.
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.
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 great vid! One thing I don't 100% agree is that we need to design classes for ParkingSpot instead of using Enum. The reasoning you gave in the vid is 1. It's anti OOD pattern. 2. If we want to add new parking type, we will need modify the Enum. To me #1 is not a strong reason since it's dogmatic. #2 is also a very weak reason as well for couple of reasons: 1. You have to write more boilerplate code just to add a new ParkingSpot type. 2. You still have a ParkingSpotType field in your ParkingSpot class, which will very likely be an enum anyway, so you didn't address the problem in #2 above. 3. It's an overkill. Why do you want to create, say 30k, ParkingSpot instances that doesn't do anything other than holding a state or some simple info?
@@ThinkSoftware Thanks for this awesome video with clear explaination. The strategy pattern and the application of minheap provides view on design pattern use case as well as algorithm within the same video . On the derived classes for parkingspot, I have the same question too on the need of having so many classes without any additional purpose other than the type. The enum would provide the distinction and if any new type gets added, I think the enum would be changed and not the actual parking class. On the vehicle, I came across a question where requirements related and rules around vehicles like large vehicle can occupy additional spaces etc. In that case, vehicles related information may also need to be stored?
When we use enums, in the code we would be forced to write logics using instanceof checks and switch statements. So when we extend functionality, we will end up re-writing well test code which violates open closed principle. But if we are using separate classes, whenever there is an extension in the functionality, we can simply extend a new child class which has the logic within itself and inject the dependency wherever needed leveraging polymorphism.
@@ergtful Can you be more specific w.r.t this question? I don't see any case for this question where you would need to use instanceof checks for enums and not do the same for separate classes. Can you elaborate?
I looked at many sources for implementation of the parking spot problem, which all used the vehicle hierarchy thing. That really confused me because I took their words as truth, but I just couldn't see who needs to use the vehicle class, I couldn't see the human driver manipulating the class and calling methods on it. Thanks for clarifying that, the OOD field really needs more insight, otherwise it's really hard to truly learn it with so many false information online...
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
16:34 getParkingSpot(EntryTerminal terminal); The getParkingSpot function would only use an entryTerminal, there i no reason to give it an abstract ParkingSpot because you don't get parking spots at the exit terminal.
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)
For adding one more requirement for assigning parking lot near to elevator ... Instead of sorting based on entrance... We have to implement secondary sorting while preparing binary tree of min heap
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
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.
Sounds good to
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
The special guest appearance made me feel guilty about even thinking about leaving without liking! Great content. Thank you
Thanks 🙂
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 😊
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 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.
Thank you a lot for referencing what others do in their system design TH-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.
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 🙂
You are so thorough, clear, and simple at the same time. Great effort. Keep it up
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 🙂
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 🙂
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 🙂
i think we can sum the distance of the parking lot to the entrance + parking lot to the elevator and then push that to the min heap right?
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 🙂.
Definitely one of the cleanest design videos. Just what's required in an LLD round.
Thanks for the comment
so impressive guest appearance , her glance was too amazing !!!
thanks for the comment :)
This is one of the best videos on system design. Loved it sir. Extremely impressed.
Thanks
she was sooo cute!!! after watching 27 minutes of this video, appearance of her was mind refreshing :). Great content.
Thanks 🙂
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
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.
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.
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 🙂
thanks for this, this is the best system design session i have seen :}
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 🙂
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 🙂
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.
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 Design Pattern Video I found on youtube. No nonsense, crisp and clear! Thank you sir
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 🙂
Love your especial guest. Awesome teaching video, I learned somethings.
Thanks 🙂
Watched thanks
Start at 11:20
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.
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.
The special guest's tips at the end were motivating .. thank you :) 🥰
Thanks for the comment 🙂
Best approach to a systems design/oop question I have seen so far!
Thanks
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 🙂
Need more of these! loved it
Thanks for the comment 🙂
Very well explained. Video is extremely well organised and trimmed. Thank you so much.
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?
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.
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 😊
this is a very well described approach, you need more subscribers for sure. lol the kid at the end ...
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.
This was a good video with clear and concise information. I just wish you would remake the elevator system design video without the divide and conquer approach and consider each lift to service all floors.
This is so genius. Thank you so much for your tutorial. That ending tho 🤣🤣🤣
Thanks for the comment 🙂
very well elaborated esp when compared to others.
Thanks for the comment 🙂
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.
amazing video, thank you a lot .
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 🙂
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
Never went to a parking lot where the spot was assigned at entrance. Just my 32 years experience though. Good video btw!
no satisfactory solution for multiple elevator system design is available on net, can you fill the void?
Also, if rough text notes are available then post that too else may be write patterns used on board on respective model, that way revising just before interview one can simply slide through screenshots instead of whole video. Was asking for rough text notes only if you already have, so that making ankii cards out of it would be much effortless. You are doing good job with videos, I can precisely guess many times what solutions of others you are criticizing, paid or free most are simply not acceptable in interviews for fang. I have answered one for parking lot from net and simple got rejected.
Thanks for the comment 🙂. Yes I will make a video on elevator system design soon. It is just a matter of time. Regarding rough text notes, this is where I am writing a book which will have more detail information and also can be quickly go through if needed during interview preparation.
BTW you can find the video on elevator system design as well now.
I got this question once in an interview and it went very poorly - I couldn't figure out what the interviewer wanted me to do! Thanks for this video because it showed me what the interviewer actually wanted, and helped confirm my hypothesis: this question is nonsense (FWIW I did get the job, but am still salty about this question).
The first thing I asked the interviewer was: "what software is being developed? Is this for a game? Is it an API that runs on some on premise server or some cloud service? If so what API calls do the hardware make?", etc, etc. He couldn't answer, instead kept asking me to design a class diagram. I don't think that is reasonable. In real software you need to know what the input and output of the programs you are writing are before you can meaningfully decide on any of the internal structure. For instance, your class diagram would look wildly different if the software were powered by a relational database and request/response model vs a persistent set of objects being simulated in a game engine.
Or maybe the program just accepts a flat csv file of parking spots and returns the closest available spot from a certain entrance. If that were the case, you could solve this easily with a very simple data model and no design patterns at all.
As an industry we need to stop asking questions like this, and focus on real world problem solving. Also I don't mean to be critical of your video - you weren't the one who started this trend. But when I look at the answer to this interview question, all I see is an empty shell of an architecture that serves no purpose and solves no problem.
Thanks for your comment
at 21:43 the complexity will be k*Nlog(N) as removing a spot that is nearest(at top of one heap) will require on average O(n) from other heaps
Thanks for the comment. There is already a discussion on other comments which you can check regarding this.
for 22:00 problem , we can use two way BFS. Because we have two sources (one is Entry Point and Second is Elevator), and we have to find destination such that it should be minimum w.r.t both. Therefore, applying BFS in both sources and whenever they meet at a point and parking slot is empty, this will be the minimum distance w.r.t both.
Thanks for the comment. This would be O(n). And what if they meet and parking spot is not empty.?how will you backtrack?
If the slot is not empty , then I think we should continue searching further, because what if after having non-empty slots we get a empty slot. For example:- If my entry point source has already traversed from some empty slots, and when Source 1 meet with Source 2, it is having non-empty slots, so if we traverse further then there is a chance that Source 2 will reach to a empty slot that Source 1 has already traversed.
So, we can take a set in which we will keep track of slots, in which Source 1(Entry point) and Source 2(Elevator point) has already traversed. And , yes we will be consuming a lot of space (Queue and unordered_set)😶 . That's what coming in my mind to solve this problem. Well, I'm relating this problem with LeetCode:- Word Ladder in which I've used two way BFS to solve this problem. There, might be a better solution to solve this (Entry and Elevator) problem.
It was very good and clear explanation, Thank you
amazing..............buddy......do more videos.... ill buy ur courses........
I liked your video, that you have not considered the Vehicle class.
1. Initially, you mentioned, not going to use ParkingSpotType, but you have used that many times
2. In ParkingTicket class what is the use of ParkingSpotType, that we can get from ParkingSpotId
I think you are using ParkingSpotType enum as well apart from ParkingSpot class.
You should consider discussing factory/builder design patterns to create objects of ParkingSpot
Thanks for the comment :)
21:25 complexity of removing top element in min heap is log(n) but for other 3 heaps we will have to search for parking spot to be removed and hence complexity for them will be O(n). Hence overall complexity will be (k-1) *n not k*log(n) as mentioned in video.
in each minheap you store a node which stores the parking spot along with pointer to the nodes in other minheaps. So you don't need to search the node in other minheap and have to directly remove the nodes from other minheap resulting in O(log n)
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.
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 🙂
Thanks for the video. Have a couple of questions -
1. Where will the heaps reside If we have different strategies of assigning the parking spot which class owns state. If state is in the parkingSystem class will we pass state to the strategy ?
2. Do terminal class own any state ?
3. Which class will imitate payment ?
I think I will add these details to a course 🙂
best source I have seen so far Thanks a ton
Thanks for the comment 🙂
Very good explanation. Thanks for your effort.
Thanks for the comment 🙂
Great work man..!
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.
Overall, good explanation. However, the parking spot near entrance strategy solution probably require further thinking.
1. If four cars enter from four entrances at same time, how to synchronize the avaible spots? I don't think four mine heaps here would make things easy.
2. Building a heap is O(n), pop root opertion for min heap is O(1), and remove a particular item from the heap of other entrances require O(n).
3. How to find the parking spot not only available but also match the parking spot type?
I believe singleton arrays + sorting algorithms should be more suitable for this.
Thanks for the comment
Correction: heap.top() is O(1). heap.pop() is log(n).
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
explained very well and so easily
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
Best part of the video started from 27:29
Thanks for the comment ....
Excellent video. Can you do an example of designing an online Chess game?
Thanks. Will look into this. It is just a matter of time at my end.
If you have a separate minheap for each entrance, you will have to remove the spot from each of them when it’s occupied. The search of the element is O(N) as minheap only makes sure that the first element is the smallest and that each father is smaller then both of its children, but there is no internal order between elements. I would just have a linked lists for each of the entrances and add links for each of those lists to my “parking spot” . So when it’s used, just unlink it from all lists, when user frees the spot, add it to all lists, that would be O(log n) using binary search.
For unlinking node,when its used, won't that take O(N) time,? and when user frees spot, and adding it to all lists, How TE is O(logN) means how can you apply Binary search on linkdlist?
@@rameshsapphire7945 I meant double linked list, to unlink it double linked node is O(N). And for binary search you are right, my bad, it can’t be applied to a linked list. Need to think about a different solution...
@@irinairina131 how about using heap as he told and maintaining its indexes in a separate map? Since the inserted node values are uniques, we can store them in map and it's indexes, and when deleting node in heap , the other nodes indexes change, so then can we update their indexes as well in map while modifying the heap..?
Thinking up loud, as the distance between the parking lots and entrance doesn’t change, we can have a double linked list of all existing spots for each entrance arranged by the distance. When we have to add a spot, we go from the spot checking closest spots one by one , once we find it, we know after which spot we need to be added to the “available spots list”. Complexity is O(d) where d is the number of closest spots occupied, so in the worst case is O(N) ... looks messy 🤪just thinking of different options...
If I were interviewing with you and you gave me this problem, I’d ask my role: architect or developer. If my role is developer, your response is great. But if an architect, I’d stop you after collecting requirements to point out this system is insane and will fail because the requirements assume human behavior that fails irl.
Thanks for the comment. I think it would be a good video to discuss what an architect is supposed to do in such an interview.
Simply wow. Excellent explanation. Please continue to make such videos. Thank you for your time.
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?
Very clear and helpful. Thank you for making this video!
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
Thank you so much for your video. It helps me a lot with my final project on campus.
You are 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
Special apprearence made my day.
Thanks for the comment 🙂
Really helpful :) Thanks. Please make more videos on OOD interview questions.
Thanks for the comment 🙂
Thanks a lot . You are a good teacher.
Thanks for the comment 🙂
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 🙂
Thanks for the great vid! One thing I don't 100% agree is that we need to design classes for ParkingSpot instead of using Enum. The reasoning you gave in the vid is
1. It's anti OOD pattern.
2. If we want to add new parking type, we will need modify the Enum.
To me #1 is not a strong reason since it's dogmatic.
#2 is also a very weak reason as well for couple of reasons:
1. You have to write more boilerplate code just to add a new ParkingSpot type.
2. You still have a ParkingSpotType field in your ParkingSpot class, which will very likely be an enum anyway, so you didn't address the problem in #2 above.
3. It's an overkill. Why do you want to create, say 30k, ParkingSpot instances that doesn't do anything other than holding a state or some simple info?
Thanks for the comment. I think I need one more video to actually show the actual design.
@@ThinkSoftware Thanks for this awesome video with clear explaination. The strategy pattern and the application of minheap provides view on design pattern use case as well as algorithm within the same video . On the derived classes for parkingspot, I have the same question too on the need of having so many classes without any additional purpose other than the type. The enum would provide the distinction and if any new type gets added, I think the enum would be changed and not the actual parking class. On the vehicle, I came across a question where requirements related and rules around vehicles like large vehicle can occupy additional spaces etc. In that case, vehicles related information may also need to be stored?
When we use enums, in the code we would be forced to write logics using instanceof checks and switch statements. So when we extend functionality, we will end up re-writing well test code which violates open closed principle. But if we are using separate classes, whenever there is an extension in the functionality, we can simply extend a new child class which has the logic within itself and inject the dependency wherever needed leveraging polymorphism.
@@ergtful Can you be more specific w.r.t this question? I don't see any case for this question where you would need to use instanceof checks for enums and not do the same for separate classes. Can you elaborate?
Very useful. Thank you
I looked at many sources for implementation of the parking spot problem, which all used the vehicle hierarchy thing. That really confused me because I took their words as truth, but I just couldn't see who needs to use the vehicle class, I couldn't see the human driver manipulating the class and calling methods on it. Thanks for clarifying that, the OOD field really needs more insight, otherwise it's really hard to truly learn it with so many false information online...
Also, the bottom-up order in which you build the classes are clear, ParkingSpot -> Ticket -> Terminal. Thanks for the amazing content.
Thanks for the comments 🙂
Love this video
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.
16:34 getParkingSpot(EntryTerminal terminal); The getParkingSpot function would only use an entryTerminal, there i no reason to give it an abstract ParkingSpot because you don't get parking spots at the exit terminal.
This is the clearest and concise description ever!! Thank you so much. Please do more if you can!
Thanks for the comment 🙂
Doesn't O/C Principle say open for extension & closed for modification?? ~~ @14:10
yes
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.
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)
It was very good explanation. Keep up the good work
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 🙂
For adding one more requirement for assigning parking lot near to elevator ... Instead of sorting based on entrance... We have to implement secondary sorting while preparing binary tree of min heap
Thanks for the comment.
Not persisting data, what if system crash
Everything depends on the requirements. If the requirements include durability then the design will change accordingly