System Design Interview Question: DESIGN A PARKING LOT - asked at Google, Facebook

the following is a very versatile interview question asked that companies like Google Facebook or Amazon depending on how the interviewer puts it this could lead into a system design question an algorithmic problem solution question or an object-oriented design question stay tuned the problem statement design a parking lot let's say you are the owner of a parking lot and you have to manage maybe hundreds or even more of parking spots and you want the system which helps you manage it so I'm sure a lot of possible solutions and a lot of approaches will come to your mind immediately but at this point early in the interview the interviewer wants to see two things from you the first one being handling ambiguity so this means the interviewer wants to see that you are able to recognize the breadth of this problem statement you want to ask some clarifying questions and first of all you should ask what kind of problem area he wants to get into so you could just ask do you want me to come up with a system design do you want me to come up with a class hierarchy or should we get into a certain specific question and then write some methods second systematic approach so the second thing the interviewer is probing and testing you for is how you approach the problem you want to show a clear and systematic approach how you tackle this problem so it helps to take a step back and don't rush into one solution immediately and again it's time to ask questions and it's time to clarify some assumptions so those questions are always asked and so that they're not clear 100% they're not 100% clear and they purposefully leave details and it's your job to ask and find out what details they left out if you don't do it you'll get a worse great so you're saying interview and your chances of getting the job are lower okay now what kind of questions could you ask if you without thinking about system design or algorithms or anything just to think about what does a parking lot look like so first question could be how is this parking lot design is this a building is this an open space are some parking lots only accessible if other parking lots are free so this could be the first question for example second question could be how many spots are we talking about is this a parking lot with ten spots or are we handling maybe thousands of spots in multiple buildings third questions could be does this parking lot have multiple levels so is there a problem of how to get cars or vehicle from one level to another one if you want to get into the very advanced things you could get into the question are there multiple entrances and this already sounds a little bit like concurrency right so you could also discuss concurrency issues with this and are there multiple levels as I said but are there maybe dependencies between levels so should we should we fill up the upper level first and then go down should we optimize to fill up certain areas first and then you could get into the topic of price so if we have multiple sizes of slots so if there are two or three different sizes of slots do they have different prices and what is the pricing strategy may be a bigger slot to occupy is more expensive but if there are no more slots of the right size for this car should we think about making a fair pricing strategy and just charge for the type of week the customer is putting in there instead of charging for the actual slot he occupies and then lastly if you want to drill down more into the business side of things maybe you want to mention premium parking spots or parking spots for people with a disability which have to be in front of the entrance or parking spots which are for some reason not expensive or cheaper than other ones it doesn't hurt to mention those things because it's not only about how you code up this problem or draw it up it's about how you think about it and with with mentioning a lot of different topics from different areas you show that you have a complete picture of the business and in the end it's about making money and being valuable to the customer ok now let's assume that the interviewer planned to do to the right direction and you could clarify a lot of questions let's assume he wants you to design a system with four different sizes for different sizes of parking spots so four sizes and then there is a small medium large and x-large so you could imagine the smallest for motorcycles the medium is for small cars the largest for big cars and the X large is for buses or something like that so with that in mind we had the question which was about which car to put in what kind of spot so let's assume that you are allowed to put smaller cars in bigger Lots in bigger spots so you could put a small car into the spot of a bus so you were doing allowed to put a medium-sized car into an XL sized car and it is an exercise spot or a large spot but on the other hand you're not allowed to to put a large car into a small spot and now we know more details about this problem and we should come up with a class hierarchy so let's just think about the keywords we mentioned here we want to represent and design the parking lot system so one of the classes will be the parking lot then you want to represent vehicles cars motorcycle buses and then you want to represent the spot itself so maybe let's start with the vehicles we said there are some some classes of spots some some different types of sports and with with cars and motorcycles and buses they have a lot of things in common so immediately this should ring a bell and you should think about an inheritance inheritance strategy so we could have an abstract vehicle so the abstract really true for example has a license plate because it's our main form of identification so now you could store all kinds of information this abstract vehicle is something that all of the cars motorcycles buses and big cars small cars have in common so for example it could make sense to have a color in there so you see I'm using some sort of an enum here probably the interviewer won't let you draw it out and then write it out but just mention that in case of a caller it makes sense to use an enum okay now we have this abstract vehicle and you want to have implementations of this vehicle and it makes sense to create four different vehicles so for classes which inherit from this vehicle okay so in this case we have four different kind of vehicles one is the car one is a motorcycle one is a bus and one is a truck so they would correspond to medium small X large and large right so in your desired programming language you could have something like this as a class hierarchy so this one it's the abstract one and those are implementations of this abstract liquor class okay now let's see we have a beautiful class and we can represent vehicles what else do we need we need some sort of a big system because we need to have a method or a function where we can place a car we can put a car into the parking lot so this big thing is represented by the parking lot so it makes sense a parking lot class and thinking about a parameter to pass into a constructor if we have multiple of those parking lots because we maybe own multiple buildings with parking lots we could give it something like zip code now what kind of method does this parking lot have to provide probably the most important one will be the situation where a driver of a car comes into the parking lot and wants to put his career so we have to offer something like place card or place vehicle and now we have to think what do we pass into this mess this method and what do we return so what we definitely pass is the abstract class here a vehicle and then we return probably a spot right so now you already see we need a class parking spot okay place vehicle takes a vehicle return to spot class spot in here should also have some member variables for most something like an ID we have to identify this spot and we have to link it to the car rights because we want to use another method to find the car and then free up that spot again if the car leaves the parking lot so spot definitely has an ID could be something like a long and on the other hand we should probably mention where in which level this spot could be and some other things and then what's also crucial is to mention the size of the spot so how do we represent a size so you could think about using a number four it may be an int but there is a little bit a better way to do it with an enum so let's just use an enum now this starts to look pretty nice we have an abstract vehicle we have a little bit of an inheritance to those vehicle types they have a parking lot with with the location and we have this crucial method of placing and we have a representation of a spot so we could place a vehicle into the parking garage and if you want to do this and if the interviewer asks you to code some part of this and we're getting into the algorithmic coding question and for this it makes sense to ask what kind of gold we have with this for example one twist of this question could be you have to make the retrieving of a car the placing and the retrieving of a car as efficient as possible so you start thinking about how do we store this kind of information in reality and this makes sense to mention in reality there would be database back-end which stores all the information where our cars which should kind of sports we have and where are our parking lots and so on so we came up with a pretty reasonable design and classes and the interviewer could now ask you to implement some of it so now we're getting into the algorithmic coding question and there will be some sort of goal we have to optimize for or something we have to solve so maybe the interviewer wants you to write a method where you can place that vehicle and then also retrieve the vehicle again so passing something like a license plate and then retrieving the vehicle and freeing up that spot again and you could say something like make it as efficient as fast as possible to place the vehicle and also retrieve it and find it okay okay what does that mean in reality there will be some sort of database back-end where we store all the vehicle and spot information let's say we abstract this way for this use case and all the vehicle information all the spot information where each vehicle stays is in memory okay so we put in a vehicle and we have to store in some kind of data structure and this is mostly the point of those algorithmic interview questions that you have to choose the right kind of data structure so we need to think about how to retrieve the first spot which is suitable for the kind of card we're getting okay so place vehicle will have to find the first available spot and it makes sense to check first for a spot where this exact type of vehicle fits so imagine we're getting one of those or let's say a truck right we're getting a truck vehicle and vehicle with with a size large and we call place vehicle with it and place vehicle will check all our free track spots okay so how do we store those spots one option could be we just have an array or a list of spots but that would mean that whenever we take a place vehicle call we would have to run through each element of that list and check if that spot is free so this would be a linear operation it's probably not that nice because all we want to know is is there a free spot if yes give it to me and let's place the car in there so we could think about something like maybe a stack where we have only open spaces in there so maybe we're not as concerned about space but were concerned about time as the interviewer setting that goal so you could keep a stack where you have spots which are not occupied at that moment and then if you go into place vehicle and you get a truck you have essentially three three types of spots which are which could fit this drug or sorry one other which will fit this drug so you could check a stack for open spots for drugs because drugs also fit into the bus spot do you could have a second stack which only contains bus spots and Jack if this one has an available spot so from a newcomer linear operation we just got down to a constant because we're we only have a finite amount of types so we check in this case one or two stacks and if both of them don't contain any spots we just have to return an exception or something telling the customer no there are no more available spots okay now let's write down sort of things we just said okay so we mentioned place vehicle we'll call multiple stacks so we need in this case four stacks and place vehicle itself will then be a constant operation okay you mentioned that the place vehicle method uses for some sort of stacks where as long as there is some element as long as there's at least one element in each stack for each size this is a constant operation because we have only four sizes so place vehicle for the search is only a know of one because if we don't find a spot in the stack of the the appropriate size may for example s or M we just go down so the worst case would be we have to do four lookups to find if there is a single free spot okay then we know we can place the vehicle there and then in order to be efficient when removing and looking for the vehicle we have to use the right data structure so let's just give you the name let's say remove vehicle where we return also the spot of the of the vehicle where it where the vehicle is at the moment so the spot will then contain the spot ID the location information about that ok so if we if we place the vehicle and we use something like this stack or a linked list or one of those data structures and when removing it we don't know where the vehicle is at the moment so we only know it's for example a medium sized vehicle so it could be if we again use multiple lists it could be in the medium list of vehicles or it could also be in place in the small vehicle list if we use instead of four similar lists we use a big one it's going to be the same time complexity we have to research through one big list and have a linear rate linear time complexity so worst case would be it's it's at this it's at the last spot in the list so we have to search through all the available spots which is not it's not it's not going to be a good answer for interviewer so what kind of service raksha's do we have could we use a heap could be you two three what do we want we want fast lookup and always if you have some sort of fast lookup operation if you need a faster cooperation what you have to think about is a hash net because with the hash map with the information of what exactly we're looking for the hash table is perfect in telling us where the information for exact element is so remove vehicle will take the vehicle and we are after placing the vehicle checking first spot we are doing a second operation here which is put in hashmap so when placing the vehicle we put it in a hashmap and you could for example use multiple hashmaps but maybe if you have many different sizes you could gain a little bit from this because you would you would index and you could keep less fewer fewer hashmaps in the memory but in any case if as long as you use a hash map oh the goal time complexity will stay the same and we can do a lookup with a hash map so removing a vehicle takes for example that a license plate of the vehicle as as to lookup key and the assistant just look in national and that's where we got the spot back and the spot contains the information about the vehicle and that's all we need to place a vehicle and remove the vehicle again okay now let's do a quick recap how we got to this point we started with the very general designer parking lot question and we handle ambiguity we try to find out what exactly we want to get into and we thought about a systematic approach how to tackle this problem so first step is actually a step back take a step back think about what you want to achieve in here and ask a lot of questions so you know what the interviewer expects from you and then starting off we we treated it like a system design question we try to find out about sizes we try to find out about pricing and all kinds of that stuff and then we moved over into more of an object oriented question where we drew up a small class diagram and maybe the interviewer wanted to see some classes coded and it's always a good idea to write real code because interviewer one interviewers usually want to see that you are able to write clean bug-free code so tell them your your favorite language your your language of choice whatever it may be Java or C or C++ and write down some of the classes in this case you could have wrote we could have written the abstract vehicle class that the car classes and also the parking lot class so now we were at a system design question we moved over to a object-oriented design question and then at the very end we ended up with an algorithmic design question where we thought about what data structure to use and we came up with a with an algorithm which is very good in terms of time complexity maybe not the best in memory complexity because we're keeping quite a lot of information in a hashmap and in some other form of a stack where we're just interested in free spots so those four stacks here I mentioned we're just keeping so that we at every point in time we know exactly if we have a free spot of every size that's just optimization for time so say so then we came up with the place vehicle and we said placing the vehicle looking up a free spot just takes constant time because we check four of those stacks plus we put into a hash map which on average also takes constant time and then removing the vehicle it's just a look up in this hash map and when we said looking it up we used for example the license plate and we exactly know which vehicle is where we can remove it from this hash map and then then very less that we do is just adding that free spot because we just removed the vehicle to the stack where we were the size fits so if this vehicle was a car and it also was in one of the medium-sized spots we put it in the stack in here and that's all to it now if you want to get more into one of those questions and maybe you're very experienced and interviewers want to get deeper into more complex edge cases of this of this design and as I mentioned you could talk about concurrency concurrency is a big issue if you have multiple entrances and you could run into some sort of race conditions when your system tries to access the same spot at the same time so what what happens then on the other hand you could also think about pricing strategies so if you have different sizes in here and this system would then be self-managed so to say and the customer has to pay at the counter you could think about a price system where either you get the customer gets the same price for every spot or you give it you have to price him higher because he uses a bigger spot the most important part about those kinds of questions is ask questions but then also take hints and let the interviewer lead you through the question because probably he has a list of things on his mind where he has to test you and and probe you and he for example wants to see you do well with system design part or maybe he's just there to see your object-oriented design so don't force your way into it take his hints and do what he wants and then do it with will good confidence okay this is today's video I hope you liked it there will be more system design questions on this channel if you want to see a certain interview question being treated and being explained like this please leave comments and don't forget to subscribe my name is Ramon Lopez this is success in tech [Music] [Music]

Channel: Success in Tech

Views: 693,796

Keywords: system design, interview question, amazon interview question, google interview question, parking lot question, amazon locker interview question, parking lot system design, google object oriented, amazon object oriented, how to system design

Id: DSGsa0pu8-k

Length: 29min 18sec (1758 seconds)

Published: Wed Aug 23 2017