In Uber interview, I got into DSA part straight away and I thought I was able to build pretty optimised system design but neither did I ask any questions at the start nor I allowed interviewer to speak 😅. Learnt my lesson, take a step back
You're receiving lots of feedback that your approach is not ideal. Nevertheless, I thank you for putting it up. First, newbies have no idea how to start and at least you helped them make a start. Second, your video has provoked this great discussion. So, thanks!
one thing missing in the design that is probably important in all parking lots is time, since parking charge is usually foremost determined by how long the vehicle is parked
Ramon, Thank you. I am not an engineer, I am a UX designer, however, found this incredibly helpful to see a different perspective with colleagues I will be working with, and getting an idea of how others see the "big picture". This was eye-opening.
PriorityQueue will be a better Data Structure to use instead of a stack. We can set the priority based on the natural order(ascending order), which means when a lookup for an empty spot is requested, it always returns the nearest spot. Next, a HashMap can be a better choice. Another choice can be, HashMap where the Integer can be the count. Every time a parking spot is allocated to a vehicle, decrease the count. ex: map.put(L, 5), which means there are 5 spots for the 'L' type vehicle. count 0 means, there is no spot for a vehicle to allot. There are just good designs and bad designs which heavily depend on the use case. We can always impress an interviewer, by bringing up more options and explaining why we are choosing the particular approach, and it's advantages. Anyhow, this video is very useful to frame an approach and move forward with the design and algorithm.
Nice idea, In the hashmap which maintains the counts of the free spots, how would the system identify the spot. Is it like, the hashmap is used to only check the availability and then get them from a set of arraylists/queue which maintain the free slots for each slot size ? ArrayList smallAvailableSlots, ArrayList large AvailableSlots HashMap hashmap; int count = hashmap.get(SmallParkingSlot); if (count > 0) { ParkingSlot ps = smallAvailableSlots.first(); //update hashmap and arraylist return ps; }
I don't understand one thing suppose we use a database(say mysql) then why do we even need data structures, can't we just query from it and achieve our goals. Someone please specify!!!
See this is very intuitive and makes a lot of sense. And this is also the reason why most people does not understand agile. In agile, the best thing to do is just start by building and getting a quick feedback from the interviewer stating this was not what he wants.
Great video. Heres what I got: When asked a question, my answer should start with clarifying questions. Only when having some clarification to a general ask, should i begin implementing such a system. Outside of that specifics about designing the system including OOP classes, properties, and methods are relatively arbitrary. What would have been immensely helpful is identifying components of the system as they relate to specific design patterns ie Singleton, Facade, Observer, etc.
Thanks for the example. But this is answered as a coding design question. I would go about this in a complete different way. Perhaps approach it top down and not rather jump into technical details right away. Just a few thoughts... 1) Write topdown (guess & confirm) nouns, verbs, entities that apply to this example before drilling down( see below) 2) Draw (guess) a diagram of a typical end to end use case scenario for main nouns to derive events that are triggered 3) Discuss which modules could be developed as stand-alone (or is it a monolithic app) 4) Mention a few future features not included in the plan (e.g. maintenance, reservations, emergency, ) 5) ONLY THEN ask where we should drill down to so a detailed technical coding design 1) Static Nouns (entities) - and a bit of attributes (id keys) Customers, (paying customer, balance management, status) Vehicles (license, CustomerID, status), CustomerPayments (CustomerID, VehicleID, status) CompanyInfo, CompanyInvoices, CompanyReceipts, ParkingLots( companyID ), ParkingLotAccess (entries, exits, ) ParkingSpots (type, status, class, ParkingLotID), ParkingPrices ( Parkingclass, PriceperHour, validity) ParkingPaymentLocations 2) Dynamic Nouns (aggregating historically) VehicleParks (vehicle in ParkingSpot) Reservations (Customer) - future feature perhaps to show how to extend the system 3) Verbs (methods, actions) - very partial list :-) AllocateSpot(vehicle), ReleaseSpot, RegisterVehicle, FreezeVehicle, ReleaseVehicle, BlackListVehicle, ReserveSpot, BillSpot, CollectPayment,
Yeah this can be a very high level system design question too! Very important to interact closely with the interviewer to find out what she/he is trying to probe you for.
I disagree with this process. Why design the class hierarchy before we discussed the functionality? Why collect color and how it was used? Why have different classes for the different sizes of the car if there is no difference in behavior? Why placeVehicle is a part of ParkingLot class, while removeVehicle is a part of Spot class? It would be confusing if I would have to support this code. The code is not actually done. The mentions of stack and hashmap are pretty vague. It's not clear how exactly this implementation will be working. Honestly, if I would be the interviewer and just see this, I would not give the high grade.
First thing I wondered... who are we designing for? Are we designing a plan for engineers to build? A recommendation system to direct users to their spot? A record keeping system to help the owner make business decisions?
It's awesome that you covered a part of system design, oop and ds & algos in single video. We can show interviewer that we are good with 3 concepts. That's cool.
Technically unless you're moving the "spot" around in memory, you don't need the four stacks. Simply keep a counter of all the spots of each type and increment and decrement the counters as you use and clear spots. You can still use the hashMap to store the Spot instances.
If teachers are good we won't lean to learn on our won. Time passed, no point in pointing them. Start learning yourself. No offence. I too have same wish btw.
Another more modern approach is to favor composition over inheritance. Composition favors the simple function of parking over predicting a taxonomy of classes very early. What if the parking lot starts as a open space for motor vehicles but requirement changes into a parking lot for bicycles and airplanes, or spaceships (things that may not have license plate or conform to parent class). Would the interviewer trash this application/system and start over again? Inheritance encourages future prediction and is not flexible. This happens all the time in the real world.
I was with you with Bicycles and airplanes. But dude SPACESHIPS :D. ..... Just kidding. I also favor composition over inheritance. nobody wants to find themselves in the Gorilla in the jungle problem.
@Eric Gu can you give us an example of composition can be used in place of inheritance for the objects that can be placed in a parking lot system in this exercise? Thanks
@Eric Gu IDK man, i can see the whole bicycle's not having a license plate, but airplanes and spaceships would definitely conform to it. As i'd assume that spaceships would be treated similarly to airplanes in the FAAs eyes and Airplanes have a n-number/unique identification number which is used by ATC towers/Pilots for communication to avoid potentially disastrous situations as well as for ownership purposes.
I would not call it a modern approach. I learned this in college nearly 20 years ago. The problem is that it was either not emphasized or people quickly ignore it after graduating.
Amazing video! I love this, love how it’s possible to cover all three topics in one design, and allow the interviewer to lead the direction! Thank you!
Thanks for your content and effort, I think this approach is more appropriate for a object oriented design question. Not much discussion is done on the system and its scalability, handling of data, etc. But thank you for the good ideas about implementation side of things!
Very nice detailed video. Thanks for the detailed explanation. But using stack only for tracking how many spots we are left with us is an overkill. Just use counters of any integer type. Increment it as you fill up and decrement it as spaces are free. If you are going to use the stack for a different purpose in future scalable design then that’s a different scenario. As of now stack DS doesn’t make much sense here. For coders out there, Guys coding in C++, can just use std::map instead of writing a hashmap DS, unlike java which has HashMap as a inbuilt container. One mote better powerful DS i can think of is using nested maps which can contain so many information at once. e.g std::map
Hey nice video and I really liked the first part of video where you removed ambiguity and systematic approach. However I have a different approach(not so different) for vehicle parking and unparking. Use a Map unoccupiedSpaces Map occupiedSpaces I am using a List for unoccupied space because it doesn't really matter if I use Stack or List. Actually when we free a vehicle we generally give spot Id to the method. You never mentioned about the Spot class. I believe it should also have something timeIn, timeOut and Vehicle instance. Let me know if am wrong in understanding.
Instead of using stacks, could have used a Priority Queue (keyed by distance from the entrance) so that when spots are returned back to the pool, they still appear in order of proximity from entrance.
I was thinking same scenario, why let car parked at farthest slot from entrance when a slot is free near entrance. But this is will indeed increase TC. Its all about trade off and choices.
This is definitely an awesome explanation. While I always feel in bay area, high tech company cares more about communication skills rather than real technical experience. Even though interviewee can give expected answers for such questions, it is still highly possible in the end they deliver a low availability, low performance, non extensible system. Anyway, it's just some of my concerns. Huge thanks, subscribed already!
Using HashMap in theory for this one sounds a good choice, in practice, it's much better to use a datastore such a table in a relational database (with indexing, keys, etc.). It also may resolve the concurrency issues here with help of transactions and extra attributes such as start/end times, cost, etc. for keeping the records. I don't think one will use the HashMap instead of a database table for this in a working system, particularly, the parking facility is a large one.
I don't understand one thing suppose we use a database(say mysql) then why do we even need data structures, can't we just query from it and achieve our goals. Someone please specify!!!
question : in the findSpot() method , can i use a key-value hashmap , where you can map the available spots using the vehicle type , and i think that you can have one key and multiple values , but still O(n) since you need to traverse all the linked-list of the specific key
This is my first system design question...and all i can think is pegion hole principle and some intelligent hashfunction....,didn't watched the video yet...let see how it goes. this was fun.....
There are more sense to start classifying spots: compact, standard, ev, disabilities. If you want to keep your design, in my mind more sense in queue than in stack - some spots will never be used, that will increase loading some parts of the lot than others. PS: Thank you for your videos!
For my interview I had to design a disaster plan for a political event, consisting of threat analysis, worst case scenarios, and evacuation routes. I wish they asked me this one instead.
I've feel relieved now..i thaught im weird used to think same idea..any issue in this world happen can lead to idea and benefit people then can make money with it.so summary is normal people think ordinary idea/act right? intelligent otherwise.Need to find circle who same think of view and attitude.
thx for the video. isn't there a need for unique lot ID per lot. this can be useful in locating a vehicle by using hashmap. when you park a car into a lot, store the location of the vehicle by map[license number] = parking lot ID. when to retrieve the vehicle, use the same hashmap to locate the lot. this is O(1). Also, usage of Redis would be handy. From your twitter video, understanding the characteristic of the parking lot. Usually, a car come and go within a couple of hours. There is no really need to store this info into a DB. When a car didn't leave this lot for more than 24 hours, this is the time to store into DB. I learnt a lot from you. Thanks a lot. Looking for your next video.
Detailed and easy to understand. Like how it’s being structured step by step building on the top of each step. The only thing I am not agreeing with is the color. 😂. These days they have so many fancy colours.
better enhancement could be assign an x and y to each spot, the entrance of the park as (0, 0), all available spots pushed to a priority queue in which the spot closet to (0, 0) is at the top.
I was thinking it completely different approach. Instead of drawing class or interface.. we can think of when a vehicle arrive how we block a spot, how to free the spot and revenue generation. So vehicle comes..input param vehicle type and time ( automatic). Check how many spot available for that type and block a spot number. Response is the spot number given to driver. While going out. Free the spot, calculate the cost based on duration, input here is the receipt given to the car owner at the beginning. That reads the entry time and calculate the cost.
I think using to store vehicle or booked slot hashmap and stack it will be okay for single terminal. using DB would be good thing if you want to scale and have more than one terminals
This is the second "design a parking lot" challenge I've seen, and this one is at least better than the first, which was for reserving specific spaces well in advance for a block of time (hours, not days) and I don't know why anyone would think to do that. No parking lot operates like that for a good reason: it would not work! Cars would stack up outside the lot waiting to enter for their block of time, because their space is not available until then. And what if they arrive and it's still occupied or the car next to him went over the line and they can't get in or out. So many problems. This POS system is somewhat better but, still, the idea of assigning a space is terrible. At least this one (theoretically) ensures that it's unoccupied, assuming the vehicle that just left actually did use the space they were assigned. Almost every lot charges upon leaving for obvious reasons. It's better to simply track how many spaces are available by how many have entered minus how many have paid, and let people find their own spots. This space-assigning system might be better for valet parking so they keep track of where the car is, which many times requires them moving other cars because they park them in tandem, or long-term parking by the week or month, or for really restricted number of spaces, such as a ferryboat or vehicle transport truck, train, or cargo ship.
Nice overview but there are many design gaps : abstract class should have some size identifier also, ParkingLot should have behaviour to retrieve Vehicle also, also there is no entity which handles Payment. Also how will removeVehicle work without a Ticket ? Vehicle is parked on a spot , Customer get a Ticket, ... time passes ... Customer shows Ticket gets back Vehicle and Pays. Also other things one can think here is adding or modifying of Spots.
Actually i don't know if you have been contractor before, because the first question i normally have if someone ask me to do a job is to figure out why they want to throw money into doing this, ex. what problem they'd like to address.
We had a similar question when I took digital design class. We had to design a functioning parking lot controller using ONLY logic gates and flip flops. LOL
Well, I would assume the interview is not about engineering a physical parking lot but about engineering software that helps to manage that parking lot. So I think in the clarification section it would be useful to discuss what the software should actually be doing rather than how many levels the lot is supposed to have.
such explanation at least boost me and my confidence upto certain level.Thanks a lot sir.Actually helped me to think about what is software design and how to apply the OO concepts instead of only studying it.
Stack is LIFO. The latest empty spot is added to the top of the list and taken out first. The time complexity is O(1), but the design is not very efficient when it comes to multiple parking levels with optimization as key. What if there are a 100 open spots in level 1 and the top of the stack has a spot in level 8. The next vehicle is going to get assigned that spot! Maybe there should be a stack for each level.
@20:25 You said it we have a Medium vehicle it could be in the Medium, or in the Small stack. It should be in the Medium, Large, or XLarge stacks. Medium doesn't fit in Small.
It is interesting that no where in the demo talks about check-in time or check-out time of a vehicle. I would thought it is one of the most important feature of a parking lot
Thanks for the video. You would have added the boundary check for the type of parking lot like PH/Carpool/Regular in the first half session to make more sense of parking lot system design.
This is really nice way to approach a design a system problems. Can you also take example of systems like linkedin/twitter which are real time streaming solutions as well as systems like youtube/netflix/amazon prime like systems. 1. How do you approach a storage requirement? I think in big systems storage technology chosen is really important. 2. Do we need to give estimate of storage required if they give some number e.g. on your Twitter there are 100M users and your system should be able to scale upto 200M users for next 3 years. 3. How do we limit a design such a way that it's not too big but should be able to tell entire story in nutshell way. Thanks for your time and looking forward for more solutions and interactions.
+Hitesh Patel Glad you liked it! Thank you for the feedback, I'm planning a video about streaming but to prepare it properly it will take some time. Regarding point 3: As long as you start from a high level at the beginning of the interview and mention the main features you can let the interviewer guide you and ask what part of the architecture you should dive into. So as long as you don't rush into one aspect of the design and keep *listening* and *asking* you don't have to worry much about the level of detail.
Your recommendation on point 3 is really appreciated. Waiting for design systems like linkedin or twitter. I am not just here to get one way knowledge. I believe in sharing like you do. Some initial thought on twitter 1. Should allow to tweet 2. Should allow it's users to follow any one on twitter 3. Should able to get most recent feeds High level APIs 1. public void tweet(User user, Tweet tweet) User is a class which has name, geo, address, country etc. Tweet : char tweet[256], creation time, geo info, User id 2. public boolean follow(User follower, User wantToFollow) 3. public Feed[] getFeeds(); This looks very interesting problem. We can think this as a observer design pattern. If some celebrity tweets then follower should get into Feeder systems which sorts and gives N recent items and display it on UI. This can be push model to all interested people. Regarding steaming tech: As the user base is large here, the tweet can not be synced. Means twitter system can not guarantee ack immediately. As per CAP theorem it'll be eventual consistency as we want here Availability and parition tolerance. Kafka Queing can be used to queue user's tweet and then twitter systems can process it further. Storing in kafka means down the line we get scalability as number of consumers can be optimally equal to number of partitions in given kafka topic. NoSQL data base is a good fit to store users account info. As it scales way beyound relational db provides. All tweets can be stored in NoSQL db. Caching: We can keep celebrity id in cache as they are likely to tweet often and we need their tweet. Hence there are let say "S" celebrities and for in-memory distributed cache could be "Redis" as it scales well beyound one macine and this is in-memory. Let me know your feedback and forward how you approach this problem. Have a nice day.
+Hitesh Patel Awesome, you covered a lot of ground with those topics. Your mentioning eventual consistency and you seem to know about the tradeoffs. You could dive deeper into the service architecture: How do you slice the architecture into pieces to enable horizontal scaling? You'll find more sys design videos on this channel soon, but also keep an eye out for others. I'm trying to share knowledge beyond interview, making us all better engineers.
Thanks for reply. I first think product from users perspective. What should be done? What is USP of any given product. Try to optimize that usecase rather than small other usecases. e.g. In facebook status update is like realtime but to see my timeline can tolerate some delay. Hence i will not put timeline data into any cache. But feeds/status are near real time data that i can cache for some time. Then with CAP principle we can identify the victim by meeting systems end requirement in best possible way.
i agree with the overall "process" on how to approach this problem. But like others, I question whats the point of implementing a vehicle class? the ability to store the color, size or plate as an object is never reused. if you were to write a function to assign a vehicle to a parking slot, you can just pass the size and the plate # as an argument. parking slots should be objects instead, then you can push and pop them out of their respective stacks and store them as values in your hashmap.
What about using a hash table where the key is the size and the value is the list of available spots? This way if you have a different type of spot (like premium), you just have to add a new entry in the hash table instead of changing the code itself to add a new stack
Thank you for great lesson! One thing I missed is regarding the system itself - why you need to subclass Vehicle and how do you address type/size variance?
Thank you! There are many different ways to design this. If you expect varieties of vehicles inheritance makes sense (you can do type comparison etc) and in the subclasses you can hide things like shape, size, weight etc. If it‘s only one dimension you care about maybe inheritance is overkill and you could get by with some enums
Thanks a lot, great explanation and details. I am wondering - why would you start design of class hierarchy with classes, instead of interfaces? I would say that here, having an interface ICar { String GetPlateNumber(); Enum GetSize(); } Is more than enough and for all the rest of the question we actually don't care, what kind of class hierarchy sits behind that interface. What do you thing about it?
Good one. Nice that you explained why to use stack and why Hashmap. This helps in decision making in similar situations . Please use bigger whiteboard so that entire problem can be seen at once. Waiting to see more such videos.
The architecture. A bigger board will ensure you dont delete something which you have on the board already. That would also help in relating things if needed later in your talk.
@@powder77777 Yes, using a queue instead of stack would work too. And the time and space complexities would remain the same for both stack and queue implementations.
I assume that it's a good idea to add parkinglot parameter into spot constructor because spot can't exist without parkinglot. Class hierarchy should represent some scope possibilities and limitations.
I also kind of disagree with the process, but for different reasons that Sergey. When designing a data structure (class), the very first thing I would do is identify the most important properties of that entity. For example, for class ParkingLot, the absolutely most important property is its maximum capacity. It certainly way more important than Zip Code.
Yeah I'm not sure why the class hierarchy was necessary; from the perspective of the parking lot system the only thing that matters is that there are vehicles and they have some size. I would have done size as an enum.
If I think about to enhance this design to support pricing I think I should add a table in the database for ParkingHistory where I store all parking information: (time, spotId, VehicleId, action - place or remove the vehicle). For placing the vehicle I just add the record there, for removing the vehicle I need to find the corresponding record where the vehicle was placed to that spot and calculate the delta time for charging the price. Of course it can be saved in memory but database seems to be more appropriate. What do you think?
Why use the hashmap? I'd just add a Spot reference in the Vehicle object. What do you think? It may concern only the subject of a Vehicle in a parking lot, but considering the fact that this is a parking lot implementation, I think it's fine.
areas to talk about : Building or open space? Free or Paid? Multiple levels? Accessibility? One building or multiple building? Concurrency? Multiple entrances? Order of filling? Price? Compact - Normal size - Electric charge - Physically challenged?
Thanks for the interesting video. Here are a few thoughts from me. Stack seems not necessary / overkill for keeping track of number of free spaces. You only need a counter (integer). The counter can start on the total number of free spots for a given spot type, and be decremented each time a spot of that type is allocated and incremented when the Spot is Unallocated(). When it reaches 0 it means no more spots available. I didn't catch anything covering the edge case of a full car park / 0 spots available? I'd personally return a Null for the Spot. Its not exceptional for a carpark to be full its a normal function of a car park to be full so I wouldn't throw an exception. Vehicle should probably have a Nominal / Desired SpotSize enum property. (Or even an array or flags enum of Allowed spot sizes could be considered..) In reality, removing a vehicle from a carpark requires you to know its Spot first. I would probably model that by having the CarPark class have an Unallocate(spot) method (Or even Spot.Unallocate()). I'd keep the utility method to find a Spot by vehicle reg number, however it would be better if when the client makes a call to place a car, they keep hold of the spot that is returned so that they can unallocate it again later without having to find it again. One thing I don't like about the design is that extending it with a new spot size means changing the implementation by adding a new stack and not only that but if the spot is larger than other spots, changing the logic that places vehicles in those other spots to also check this new stack when they have no spots remaining. Smells to me. I personally would: 1. Move the PlaceVehicle() method to a new SpotAllocator class - name it something like Allocate(vehicle) and still have it return a Spot like before. 2. SpotAllocator class would use a Dictionary of SpotSize enum (key) SpotAllocationInfo (value). For each size spot (small, medium etc) you have an entry in the dictionary, and the SpotAllocationInfo can hold the integer counter for the remaining spaces for that spot size. It could also have a "NextSpotSize" property indicating the spotsize to check next when 0 spaces are reached. When asked to place a vehicle it gets the spot size for the vehicle and indexes into the dictionary to get the SpotAllocationInfo for that spot size. If there are places available it returns a new Spot (decrementing the counter accordingly). If there are not any spaces available it looks at the NextSpot size and repeats until it either returns a Spot or returns Null if none available. This kind of design would: 1. Allow you to add a new spot size very easily (by adding an enum and a single dictionary entry. All in all it was interesting to think through, so thank you for the video!
The re addition of the empty space to the stack is an O(n) operation which kinda sucks but may be a reasonable tradeoff. A minheap would be better suited to get the best overall performance while sacrificing the entry performance. Otherwise very good video, nicely explained. Especially the part about practicalities of interviews.
I got asked the similar question in an interview about train station design. There I messed up with concurrency part as multiple trains can arrive and depart from platforms simultaneously.. Could you please explain how would you go about handling concurrency in context of parking spots if there are multiple entrances and exits. That would give me a fair idea about train station problem. Thanks in advance. You have explained the problem to the depth and I am really looking forward to seeing other videos of yours.
Awesome video. Can you add for Designing the BookmyShow. How to handle the RACE condition when 1 seat is available and two people try to book the same seat simultaneously.
Thanks a lot. The only question I have is, why do we need an abstraction for Vehicles in parking lot problem.. Why can't we have Spot as Abstract class and Small, medium , large and XL spots as concrete class. All we are interested is , how many spots are available and how many are occupied.. Isn't it?
There is a difference in the system design questions based on you level at companies such as Amazon. As an SDE-1 we would not expect your system designs to go beyond a single system therefor the focus on your data structures and what algorithms you select. Around late SDE-2 to SDE-3 that is where we would start asking you to design more high level stuff like design Facebook or Twitter, where we would like to see that you can build scalable systems that are reliable and such.
I once received the problem "Design a coffee shop" at Oracle and the interviewer stubbornly refused to clarify exactly what did he want - a POS system, etc? It was terrible.
Didn't understand about the use of stack. Why do we need a stack here? Why don't we use a Queue or a List here? Also why do "placeVehicle()" and "removeVehicle()" need to return the spot? What do we do with the returned Spot object? The responsibility of "placeVehicle()" should be *placing* a vehicle rather than *finding* a spot to place a vehicle. Also he should mention that for example, if we can't find a L spot for truck we should find a XL spot for placing a truck.
Very best work sir. Can you please also make a video regarding Designing a shopping cart. And thank you very much for your valuable time and all the efforts you are making. Allah bless you.
The problem with interview questions like this is that you're starting from a bad design and are being tasked to make a very stupid design work. There is a reason most parking lots do not accommodate busses and tractor trailers, there is a reason why rest stops have separate entrances and parking for private two-axle vehicles and busses and tractor trailers. The problem with this test is that you can't say this is bad design and I would either only include busses and tractor trailers in my parking lot or not include them at all. Forget we are even talking about parking lots, it's a terrible design for any use case.
I'm doing a little experiment over on IGTV, the SiT VLOG. Check it out! instagram.com/tv/BkYf4GphfQz/
In Uber interview, I got into DSA part straight away and I thought I was able to build pretty optimised system design but neither did I ask any questions at the start nor I allowed interviewer to speak 😅. Learnt my lesson, take a step back
Requirement gathering is key for system design interviews.
You're receiving lots of feedback that your approach is not ideal. Nevertheless, I thank you for putting it up. First, newbies have no idea how to start and at least you helped them make a start. Second, your video has provoked this great discussion. So, thanks!
one thing missing in the design that is probably important in all parking lots is time, since parking charge is usually foremost determined by how long the vehicle is parked
Ramon,
Thank you. I am not an engineer, I am a UX designer, however, found this incredibly helpful to see a different perspective with colleagues I will be working with, and getting an idea of how others see the "big picture". This was eye-opening.
PriorityQueue will be a better Data Structure to use instead of a stack. We can set the priority based on the natural order(ascending order), which means when a lookup for an empty spot is requested, it always returns the nearest spot.
Next, a HashMap can be a better choice.
Another choice can be, HashMap where the Integer can be the count. Every time a parking spot is allocated to a vehicle, decrease the count.
ex: map.put(L, 5), which means there are 5 spots for the 'L' type vehicle.
count 0 means, there is no spot for a vehicle to allot.
There are just good designs and bad designs which heavily depend on the use case. We can always impress an interviewer, by bringing up more options and explaining why we are choosing the particular approach, and it's advantages.
Anyhow, this video is very useful to frame an approach and move forward with the design and algorithm.
Nice idea, In the hashmap which maintains the counts of the free spots, how would the system identify the spot. Is it like, the hashmap is used to only check the availability and then get them from a set of arraylists/queue which maintain the free slots for each slot size ?
ArrayList smallAvailableSlots,
ArrayList large AvailableSlots
HashMap hashmap;
int count = hashmap.get(SmallParkingSlot);
if (count > 0) {
ParkingSlot ps = smallAvailableSlots.first();
//update hashmap and arraylist
return ps;
}
I don't understand one thing suppose we use a database(say mysql) then why do we even need data structures, can't we just query from it and achieve our goals. Someone please specify!!!
See this is very intuitive and makes a lot of sense. And this is also the reason why most people does not understand agile. In agile, the best thing to do is just start by building and getting a quick feedback from the interviewer stating this was not what he wants.
Great video.
Heres what I got: When asked a question, my answer should start with clarifying questions.
Only when having some clarification to a general ask, should i begin implementing such a system.
Outside of that specifics about designing the system including OOP classes, properties, and methods are relatively arbitrary.
What would have been immensely helpful is identifying components of the system as they relate to specific design patterns ie Singleton, Facade, Observer, etc.
This guy looks (which he is) very very clear in his thought and very organized.
Thanks for the example. But this is answered as a coding design question. I would go about this in a complete different way. Perhaps approach it top down and not rather jump into technical details right away. Just a few thoughts...
1) Write topdown (guess & confirm) nouns, verbs, entities that apply to this example before drilling down( see below)
2) Draw (guess) a diagram of a typical end to end use case scenario for main nouns to derive events that are triggered
3) Discuss which modules could be developed as stand-alone (or is it a monolithic app)
4) Mention a few future features not included in the plan (e.g. maintenance, reservations, emergency, )
5) ONLY THEN ask where we should drill down to so a detailed technical coding design
1) Static Nouns (entities) - and a bit of attributes (id keys)
Customers, (paying customer, balance management, status)
Vehicles (license, CustomerID, status),
CustomerPayments (CustomerID, VehicleID, status)
CompanyInfo, CompanyInvoices, CompanyReceipts,
ParkingLots( companyID ), ParkingLotAccess (entries, exits, )
ParkingSpots (type, status, class, ParkingLotID), ParkingPrices ( Parkingclass, PriceperHour, validity)
ParkingPaymentLocations
2) Dynamic Nouns (aggregating historically)
VehicleParks (vehicle in ParkingSpot)
Reservations (Customer) - future feature perhaps to show how to extend the system
3) Verbs (methods, actions) - very partial list :-)
AllocateSpot(vehicle), ReleaseSpot, RegisterVehicle, FreezeVehicle, ReleaseVehicle, BlackListVehicle, ReserveSpot, BillSpot, CollectPayment,
Yeah this can be a very high level system design question too! Very important to interact closely with the interviewer to find out what she/he is trying to probe you for.
I disagree with this process. Why design the class hierarchy before we discussed the functionality? Why collect color and how it was used? Why have different classes for the different sizes of the car if there is no difference in behavior?
Why placeVehicle is a part of ParkingLot class, while removeVehicle is a part of Spot class? It would be confusing if I would have to support this code. The code is not actually done. The mentions of stack and hashmap are pretty vague. It's not clear how exactly this implementation will be working.
Honestly, if I would be the interviewer and just see this, I would not give the high grade.
Cool, thanks for the feedback!
Welcome. Sorry if I'm a bit too critical, but this is my preception.
removeVehicle is not a method of Spot. It returns a Spot.
It’s not even clear what the “manage parking lot” requirements are.
First thing I wondered... who are we designing for? Are we designing a plan for engineers to build? A recommendation system to direct users to their spot? A record keeping system to help the owner make business decisions?
It's awesome that you covered a part of system design, oop and ds & algos in single video. We can show interviewer that we are good with 3 concepts. That's cool.
This is the best explanation for this interview question I have seen so far. Thanks a lot. Please keep doing more system design questions
Glad I could help you, check out my other videos as well! There are more interview questions but also topics like 'What happens after the interview?'.
Technically unless you're moving the "spot" around in memory, you don't need the four stacks. Simply keep a counter of all the spots of each type and increment and decrement the counters as you use and clear spots. You can still use the hashMap to store the Spot instances.
Agree!
I wish all my teachers were so organized and easy to hear
+JO H Haha favorite comment so far! Thank you
If teachers are good we won't lean to learn on our won. Time passed, no point in pointing them. Start learning yourself. No offence. I too have same wish btw.
At least they must inspire and guide us
Another more modern approach is to favor composition over inheritance. Composition favors the simple function of parking over predicting a taxonomy of classes very early. What if the parking lot starts as a open space for motor vehicles but requirement changes into a parking lot for bicycles and airplanes, or spaceships (things that may not have license plate or conform to parent class). Would the interviewer trash this application/system and start over again? Inheritance encourages future prediction and is not flexible. This happens all the time in the real world.
I was with you with Bicycles and airplanes. But dude SPACESHIPS :D. ..... Just kidding. I also favor composition over inheritance. nobody wants to find themselves in the Gorilla in the jungle problem.
I agree with you on this. Can you please provide me with links to articles you have read which talks more about this approach?
@Eric Gu can you give us an example of composition can be used in place of inheritance for the objects that can be placed in a parking lot system in this exercise? Thanks
@Eric Gu IDK man, i can see the whole bicycle's not having a license plate, but airplanes and spaceships would definitely conform to it. As i'd assume that spaceships would be treated similarly to airplanes in the FAAs eyes and Airplanes have a n-number/unique identification number which is used by ATC towers/Pilots for communication to avoid potentially disastrous situations as well as for ownership purposes.
I would not call it a modern approach. I learned this in college nearly 20 years ago. The problem is that it was either not emphasized or people quickly ignore it after graduating.
Amazing video! I love this, love how it’s possible to cover all three topics in one design, and allow the interviewer to lead the direction! Thank you!
Thanks for your content and effort, I think this approach is more appropriate for a object oriented design question. Not much discussion is done on the system and its scalability, handling of data, etc. But thank you for the good ideas about implementation side of things!
Very nice detailed video. Thanks for the detailed explanation.
But using stack only for tracking how many spots we are left with us is an overkill. Just use counters of any integer type. Increment it as you fill up and decrement it as spaces are free. If you are going to use the stack for a different purpose in future scalable design then that’s a different scenario. As of now stack DS doesn’t make much sense here.
For coders out there, Guys coding in C++, can just use std::map instead of writing a hashmap DS, unlike java which has HashMap as a inbuilt container.
One mote better powerful DS i can think of is using nested maps which can contain so many information at once. e.g
std::map
Would have helped if you could've talked about multiple entrances and hence concurrency?
Hey nice video and I really liked the first part of video where you removed ambiguity and systematic approach.
However I have a different approach(not so different) for vehicle parking and unparking.
Use a
Map unoccupiedSpaces
Map occupiedSpaces
I am using a List for unoccupied space because it doesn't really matter if I use Stack or List.
Actually when we free a vehicle we generally give spot Id to the method.
You never mentioned about the Spot class. I believe it should also have something timeIn, timeOut and Vehicle instance.
Let me know if am wrong in understanding.
Instead of using stacks, could have used a Priority Queue (keyed by distance from the entrance) so that when spots are returned back to the pool, they still appear in order of proximity from entrance.
I was thinking same scenario, why let car parked at farthest slot from entrance when a slot is free near entrance.
But this is will indeed increase TC.
Its all about trade off and choices.
This is definitely an awesome explanation. While I always feel in bay area, high tech company cares more about communication skills rather than real technical experience. Even though interviewee can give expected answers for such questions, it is still highly possible in the end they deliver a low availability, low performance, non extensible system. Anyway, it's just some of my concerns. Huge thanks, subscribed already!
有意思
I would use a Queue to track the empty spots.
Excellent approach on solving complex problem with little baby steps.
Instead of stack u can use a free list and used list (or used map). Getting parking and freeing parking will be O(1) and O(n)/O(1)
Using HashMap in theory for this one sounds a good choice, in practice, it's much better to use a datastore such a table in a relational database (with indexing, keys, etc.). It also may resolve the concurrency issues here with help of transactions and extra attributes such as start/end times, cost, etc. for keeping the records. I don't think one will use the HashMap instead of a database table for this in a working system, particularly, the parking facility is a large one.
I don't understand one thing suppose we use a database(say mysql) then why do we even need data structures, can't we just query from it and achieve our goals. Someone please specify!!!
@@himanshupoddar1395 Did you get an answer to this question? same thoughts!
best explanation on the internet for this question. please make videos on elevator design, vending machine design and atm design.
Yes please!
question : in the findSpot() method , can i use a key-value hashmap , where you can map the available spots using the vehicle type , and i think that you can have one key and multiple values , but still O(n) since you need to traverse all the linked-list of the specific key
Very nice stuff. Explained how to go about tackling the problem. Liked it. Thanks.
This is my first system design question...and all i can think is pegion hole principle and some intelligent hashfunction....,didn't watched the video yet...let see how it goes.
this was fun.....
There are more sense to start classifying spots: compact, standard, ev, disabilities. If you want to keep your design, in my mind more sense in queue than in stack - some spots will never be used, that will increase loading some parts of the lot than others.
PS:
Thank you for your videos!
You are a lifesaver. Thanks!
If we optimize on the place-vehicle and remove-vehicle based on distance from entrance to the spot, we can use heap.
+Saurabh Goyal Yeah, a min-heap on distance. Nice!
For my interview I had to design a disaster plan for a political event, consisting of threat analysis, worst case scenarios, and evacuation routes.
I wish they asked me this one instead.
I've feel relieved now..i thaught im weird used to think same idea..any issue in this world happen can lead to idea and benefit people then can make money with it.so summary is normal people think ordinary idea/act right? intelligent otherwise.Need to find circle who same think of view and attitude.
thx for the video. isn't there a need for unique lot ID per lot. this can be useful in locating a vehicle by using hashmap. when you park a car into a lot, store the location of the vehicle by map[license number] = parking lot ID. when to retrieve the vehicle, use the same hashmap to locate the lot. this is O(1).
Also, usage of Redis would be handy. From your twitter video, understanding the characteristic of the parking lot.
Usually, a car come and go within a couple of hours. There is no really need to store this info into a DB.
When a car didn't leave this lot for more than 24 hours, this is the time to store into DB.
I learnt a lot from you. Thanks a lot. Looking for your next video.
I have an interview with Amazon in about 3 hours.......oh my goodness.....Thank you for this.
And how did it go?
Detailed and easy to understand. Like how it’s being structured step by step building on the top of each step. The only thing I am not agreeing with is the color. 😂. These days they have so many fancy colours.
Thanks! You mean the colors of the whiteboard markers? 😅
better enhancement could be assign an x and y to each spot, the entrance of the park as (0, 0), all available spots pushed to a priority queue in which the spot closet to (0, 0) is at the top.
hash the license plates to spot numbers, have an overflow lot for hashing collisions.
I was thinking it completely different approach. Instead of drawing class or interface.. we can think of when a vehicle arrive how we block a spot, how to free the spot and revenue generation. So vehicle comes..input param vehicle type and time ( automatic). Check how many spot available for that type and block a spot number. Response is the spot number given to driver. While going out. Free the spot, calculate the cost based on duration, input here is the receipt given to the car owner at the beginning. That reads the entry time and calculate the cost.
How do write the „check how many spots available for type“ part?
@@SuccessinTech before reserve we must check that anyway right? That is the api we need to lookup total number of available spot
I think using to store vehicle or booked slot hashmap and stack it will be okay for single terminal. using DB would be good thing if you want to scale and have more than one terminals
One of the best technical videos watched till date.
This is the second "design a parking lot" challenge I've seen, and this one is at least better than the first, which was for reserving specific spaces well in advance for a block of time (hours, not days) and I don't know why anyone would think to do that. No parking lot operates like that for a good reason: it would not work! Cars would stack up outside the lot waiting to enter for their block of time, because their space is not available until then. And what if they arrive and it's still occupied or the car next to him went over the line and they can't get in or out. So many problems. This POS system is somewhat better but, still, the idea of assigning a space is terrible. At least this one (theoretically) ensures that it's unoccupied, assuming the vehicle that just left actually did use the space they were assigned. Almost every lot charges upon leaving for obvious reasons. It's better to simply track how many spaces are available by how many have entered minus how many have paid, and let people find their own spots. This space-assigning system might be better for valet parking so they keep track of where the car is, which many times requires them moving other cars because they park them in tandem, or long-term parking by the week or month, or for really restricted number of spaces, such as a ferryboat or vehicle transport truck, train, or cargo ship.
Nice overview but there are many design gaps : abstract class should have some size identifier also, ParkingLot should have behaviour to retrieve Vehicle also, also there is no entity which handles Payment. Also how will removeVehicle work without a Ticket ? Vehicle is parked on a spot , Customer get a Ticket, ... time passes ... Customer shows Ticket gets back Vehicle and Pays. Also other things one can think here is adding or modifying of Spots.
Actually i don't know if you have been contractor before, because the first question i normally have if someone ask me to do a job is to figure out why they want to throw money into doing this, ex. what problem they'd like to address.
I’d love to see a system design video from a finance perspective.
Well finance is very large complex topic
I think vehicle number is enough to distinguish between the vehicle. Colour is not required or no use of it in parking lot.
We had a similar question when I took digital design class. We had to design a functioning parking lot controller using ONLY logic gates and flip flops. LOL
Well, I would assume the interview is not about engineering a physical parking lot but about engineering software that helps to manage that parking lot. So I think in the clarification section it would be useful to discuss what the software should actually be doing rather than how many levels the lot is supposed to have.
such explanation at least boost me and my confidence upto certain level.Thanks a lot sir.Actually helped me to think about what is software design and how to apply the OO concepts instead of only studying it.
Glad you like'd it! If you wanna do me a favor, share my videos on your social media =)
Stack is LIFO. The latest empty spot is added to the top of the list and taken out first. The time complexity is O(1), but the design is not very efficient when it comes to multiple parking levels with optimization as key. What if there are a 100 open spots in level 1 and the top of the stack has a spot in level 8. The next vehicle is going to get assigned that spot! Maybe there should be a stack for each level.
Or maybe a priority queue with closer levels having higher priority.
Regarding the system design, I would consider to begin with ERD model first and only then move to a class/methods/, coding
@20:25 You said it we have a Medium vehicle it could be in the Medium, or in the Small stack. It should be in the Medium, Large, or XLarge stacks. Medium doesn't fit in Small.
Even I have same thought
He's clearly designing it for NYC.
It is interesting that no where in the demo talks about check-in time or check-out time of a vehicle. I would thought it is one of the most important feature of a parking lot
This is really very helpful . Thank you so much for this video !! 😃
Ha! I gave this problem for over 50 interviews for Amazon.
Let's make this more interesting: a LIVE example! Here's my interview question to you: *design a petrol station.*
Thanks for the video. You would have added the boundary check for the type of parking lot like PH/Carpool/Regular in the first half session to make more sense of parking lot system design.
This is really nice way to approach a design a system problems. Can you also take example of systems like linkedin/twitter which are real time streaming solutions as well as systems like youtube/netflix/amazon prime like systems.
1. How do you approach a storage requirement?
I think in big systems storage technology chosen is really important.
2. Do we need to give estimate of storage required if they give some number
e.g. on your Twitter there are 100M users and your system should be able to scale upto 200M users for next 3 years.
3. How do we limit a design such a way that it's not too big but should be able to tell entire story in nutshell way.
Thanks for your time and looking forward for more solutions and interactions.
+Hitesh Patel Glad you liked it! Thank you for the feedback, I'm planning a video about streaming but to prepare it properly it will take some time. Regarding point 3: As long as you start from a high level at the beginning of the interview and mention the main features you can let the interviewer guide you and ask what part of the architecture you should dive into. So as long as you don't rush into one aspect of the design and keep *listening* and *asking* you don't have to worry much about the level of detail.
Your recommendation on point 3 is really appreciated. Waiting for design systems like linkedin or twitter. I am not just here to get one way knowledge. I believe in sharing like you do.
Some initial thought on twitter
1. Should allow to tweet
2. Should allow it's users to follow any one on twitter
3. Should able to get most recent feeds
High level APIs
1. public void tweet(User user, Tweet tweet)
User is a class which has name, geo, address, country etc.
Tweet : char tweet[256], creation time, geo info, User id
2. public boolean follow(User follower, User wantToFollow)
3. public Feed[] getFeeds();
This looks very interesting problem. We can think this as a observer design pattern. If some celebrity tweets then follower should get into Feeder systems which sorts and gives N recent items and display it on UI. This can be push model to all interested people.
Regarding steaming tech:
As the user base is large here, the tweet can not be synced. Means twitter system can not guarantee ack immediately. As per CAP theorem it'll be eventual consistency as we want here Availability and parition tolerance.
Kafka Queing can be used to queue user's tweet and then twitter systems can process it further. Storing in kafka means down the line we get scalability as number of consumers can be optimally equal to number of partitions in given kafka topic.
NoSQL data base is a good fit to store users account info. As it scales way beyound relational db provides.
All tweets can be stored in NoSQL db.
Caching:
We can keep celebrity id in cache as they are likely to tweet often and we need their tweet. Hence there are let say "S" celebrities and for in-memory distributed cache could be "Redis" as it scales well beyound one macine and this is in-memory.
Let me know your feedback and forward how you approach this problem. Have a nice day.
+Hitesh Patel Awesome, you covered a lot of ground with those topics. Your mentioning eventual consistency and you seem to know about the tradeoffs. You could dive deeper into the service architecture: How do you slice the architecture into pieces to enable horizontal scaling?
You'll find more sys design videos on this channel soon, but also keep an eye out for others. I'm trying to share knowledge beyond interview, making us all better engineers.
Thanks for reply. I first think product from users perspective. What should be done? What is USP of any given product. Try to optimize that usecase rather than small other usecases.
e.g. In facebook status update is like realtime but to see my timeline can tolerate some delay. Hence i will not put timeline data into any cache. But feeds/status are near real time data that i can cache for some time.
Then with CAP principle we can identify the victim by meeting systems end requirement in best possible way.
Also stack isn't O(1) operation, its O(s) where s is the ordinality of your different sizes. Maybe nitpick but it's not arbitrarily constant.
i agree with the overall "process" on how to approach this problem. But like others, I question whats the point of implementing a vehicle class? the ability to store the color, size or plate as an object is never reused. if you were to write a function to assign a vehicle to a parking slot, you can just pass the size and the plate # as an argument. parking slots should be objects instead, then you can push and pop them out of their respective stacks and store them as values in your hashmap.
fantastic video! many thanks !
What about using a hash table where the key is the size and the value is the list of available spots? This way if you have a different type of spot (like premium), you just have to add a new entry in the hash table instead of changing the code itself to add a new stack
Yeah thats good reasoning!
you can also use linked hashMap. First entry will be smallest size, and last will be largest size. Also you can take care of concurrency.
Thank you for sharing your ideas. From my perspective, your approach is better.
Thank you for great lesson! One thing I missed is regarding the system itself - why you need to subclass Vehicle and how do you address type/size variance?
Thank you! There are many different ways to design this. If you expect varieties of vehicles inheritance makes sense (you can do type comparison etc) and in the subclasses you can hide things like shape, size, weight etc. If it‘s only one dimension you care about maybe inheritance is overkill and you could get by with some enums
Thanks a lot, great explanation and details.
I am wondering - why would you start design of class hierarchy with classes, instead of interfaces?
I would say that here, having an interface ICar {
String GetPlateNumber();
Enum GetSize();
}
Is more than enough and for all the rest of the question we actually don't care, what kind of class hierarchy sits behind that interface.
What do you thing about it?
I feel placeVehicle and removeVehicle should be in the same class. Nonetheless, I enjoyed the breakdown!!
you are helping a lot of people , thank you
Thanks a lot! This was a really good explanation for this question.
Thanks a lot for making it look like a quite simple problem...
Good one. Nice that you explained why to use stack and why Hashmap. This helps in decision making in similar situations . Please use bigger whiteboard so that entire problem can be seen at once. Waiting to see more such videos.
+Kapil Sharma thanks for your feedback! What exactly would you like to see on the whiteboard? The problem statement, code or the architecture?
The architecture. A bigger board will ensure you dont delete something which you have on the board already. That would also help in relating things if needed later in your talk.
I think using a queue will work too.
@@powder77777 Yes, using a queue instead of stack would work too. And the time and space complexities would remain the same for both stack and queue implementations.
I assume that it's a good idea to add parkinglot parameter into spot constructor because spot can't exist without parkinglot. Class hierarchy should represent some scope possibilities and limitations.
I also kind of disagree with the process, but for different reasons that Sergey. When designing a data structure (class), the very first thing I would do is identify the most important properties of that entity. For example, for class ParkingLot, the absolutely most important property is its maximum capacity. It certainly way more important than Zip Code.
Yeah I'm not sure why the class hierarchy was necessary; from the perspective of the parking lot system the only thing that matters is that there are vehicles and they have some size. I would have done size as an enum.
If I think about to enhance this design to support pricing I think I should add a table in the database for ParkingHistory where I store all parking information: (time, spotId, VehicleId, action - place or remove the vehicle). For placing the vehicle I just add the record there, for removing the vehicle I need to find the corresponding record where the vehicle was placed to that spot and calculate the delta time for charging the price. Of course it can be saved in memory but database seems to be more appropriate. What do you think?
Yeah sure. I‘d also think about scenarios where you can‘t find the first record.
Kindly provide similar video on Airbnb, Netflix, Twitter, LinkedIn system design problems
Please discuss a design question like "How do you design a music streaming service like Spotify?"
Why use the hashmap? I'd just add a Spot reference in the Vehicle object. What do you think? It may concern only the subject of a Vehicle in a parking lot, but considering the fact that this is a parking lot implementation, I think it's fine.
areas to talk about :
Building or open space? Free or Paid? Multiple levels? Accessibility? One building or multiple building? Concurrency? Multiple entrances? Order of filling? Price? Compact - Normal size - Electric charge - Physically challenged?
Thanks for the interesting video. Here are a few thoughts from me.
Stack seems not necessary / overkill for keeping track of number of free spaces. You only need a counter (integer). The counter can start on the total number of free spots for a given spot type, and be decremented each time a spot of that type is allocated and incremented when the Spot is Unallocated(). When it reaches 0 it means no more spots available.
I didn't catch anything covering the edge case of a full car park / 0 spots available? I'd personally return a Null for the Spot. Its not exceptional for a carpark to be full its a normal function of a car park to be full so I wouldn't throw an exception.
Vehicle should probably have a Nominal / Desired SpotSize enum property. (Or even an array or flags enum of Allowed spot sizes could be considered..)
In reality, removing a vehicle from a carpark requires you to know its Spot first. I would probably model that by having the CarPark class have an Unallocate(spot) method (Or even Spot.Unallocate()). I'd keep the utility method to find a Spot by vehicle reg number, however it would be better if when the client makes a call to place a car, they keep hold of the spot that is returned so that they can unallocate it again later without having to find it again.
One thing I don't like about the design is that extending it with a new spot size means changing the implementation by adding a new stack and not only that but if the spot is larger than other spots, changing the logic that places vehicles in those other spots to also check this new stack when they have no spots remaining. Smells to me. I personally would:
1. Move the PlaceVehicle() method to a new SpotAllocator class - name it something like Allocate(vehicle) and still have it return a Spot like before.
2. SpotAllocator class would use a Dictionary of SpotSize enum (key) SpotAllocationInfo (value). For each size spot (small, medium etc) you have an entry in the dictionary, and the SpotAllocationInfo can hold the integer counter for the remaining spaces for that spot size. It could also have a "NextSpotSize" property indicating the spotsize to check next when 0 spaces are reached. When asked to place a vehicle it gets the spot size for the vehicle and indexes into the dictionary to get the SpotAllocationInfo for that spot size. If there are places available it returns a new Spot (decrementing the counter accordingly).
If there are not any spaces available it looks at the NextSpot size and repeats until it either returns a Spot or returns Null if none available.
This kind of design would:
1. Allow you to add a new spot size very easily (by adding an enum and a single dictionary entry.
All in all it was interesting to think through, so thank you for the video!
Awesome matey! Keep going man!
This approach should have been in all other system design videos of yours, asking questions before jumping into design/coding..
The re addition of the empty space to the stack is an O(n) operation which kinda sucks but may be a reasonable tradeoff. A minheap would be better suited to get the best overall performance while sacrificing the entry performance. Otherwise very good video, nicely explained. Especially the part about practicalities of interviews.
I got asked the similar question in an interview about train station design. There I messed up with concurrency part as multiple trains can arrive and depart from platforms simultaneously.. Could you please explain how would you go about handling concurrency in context of parking spots if there are multiple entrances and exits. That would give me a fair idea about train station problem. Thanks in advance. You have explained the problem to the depth and I am really looking forward to seeing other videos of yours.
Awesome video. Can you add for Designing the BookmyShow. How to handle the RACE condition when 1 seat is available and two people try to book the same seat simultaneously.
Vivek Yadav I was looking for a similar solution. Did you find any videos for that?
Who are you and where have you been all my life?
My lecturers are no where close to being this helpful. :(
Haha thanks!
Thanks a lot. The only question I have is, why do we need an abstraction for Vehicles in parking lot problem.. Why can't we have Spot as Abstract class and Small, medium , large and XL spots as concrete class. All we are interested is , how many spots are available and how many are occupied.. Isn't it?
It's actually more like a coding interview question than a system design question haha
There is a difference in the system design questions based on you level at companies such as Amazon. As an SDE-1 we would not expect your system designs to go beyond a single system therefor the focus on your data structures and what algorithms you select. Around late SDE-2 to SDE-3 that is where we would start asking you to design more high level stuff like design Facebook or Twitter, where we would like to see that you can build scalable systems that are reliable and such.
Awesome... Really soon thankful for the video. Great job. Keep adding more questions.
Thank you very much sir.I have learnt a big deal on the method of approach and points to be kept in mind
+Tnv Madhav Happy I could help, don’t forget to subscribe and follow on Twitter @_SH4DY_ Have a good one!
This is really nice video. Very well explained. Well done man..
I once received the problem "Design a coffee shop" at Oracle and the interviewer stubbornly refused to clarify exactly what did he want - a POS system, etc? It was terrible.
Didn't understand about the use of stack. Why do we need a stack here? Why don't we use a Queue or a List here? Also why do "placeVehicle()" and "removeVehicle()" need to return the spot? What do we do with the returned Spot object? The responsibility of "placeVehicle()" should be *placing* a vehicle rather than *finding* a spot to place a vehicle. Also he should mention that for example, if we can't find a L spot for truck we should find a XL spot for placing a truck.
Very best work sir. Can you please also make a video regarding Designing a shopping cart.
And thank you very much for your valuable time and all the efforts you are making. Allah bless you.
great job Roman!
The problem with interview questions like this is that you're starting from a bad design and are being tasked to make a very stupid design work. There is a reason most parking lots do not accommodate busses and tractor trailers, there is a reason why rest stops have separate entrances and parking for private two-axle vehicles and busses and tractor trailers. The problem with this test is that you can't say this is bad design and I would either only include busses and tractor trailers in my parking lot or not include them at all.
Forget we are even talking about parking lots, it's a terrible design for any use case.
Subscribed!! Your Videos are really high quality. Thanks for taking time to share your knowledge
I think I'd probably put an interface called Dimension to be inherited by Vehicle and Spot classes
Great video, I'd love to see more of them. :)