There's a common interview question that will be some variety of the Parking Lot simulation- the gist of which is you have a parking lot with parking spots of varying sizes (small, medium, large) and cars of varying sizes (small, medium, large), and it's your job to simulate inserting a car into the lot, and removing a specific car from the lot.My question is specifically related to a wrinkle that gets thrown into the problem; what happens if you let either small or medium sized cars into parking spots larger than the respective size, and then later on, find yourself with a large car trying to enter a lot with only a small parking spot left?I've had interviewers ask me how to best construct a switching algorithm, with optimal data structures, that can move a small car occupying a large parking spot into the open small spot, and then put the large car in the now-open large spot. I have no idea how to go about this, beyond simply iterating through an array of occupied large parking spots and stopping when you find your first small car. However, I'm not sure O(n) time for insertion is the most optimal time, but I've run out of ideas to improve this runtime.So I ask, what is the most, or at the very least, a more optimal algorithm, to find and switch cars from parking spots of varying sizes?
Switching algorithm for Parking Lot Software Design Problem
design;design patterns;object oriented
Interview questions are all about getting to know you as a person - how you think, how you communicate, what questions you ask, and so on.Having a perfect answer to any given puzzle of the week isn't useful, because the only interaction that happens is that the interviewer asks a canned question (thus indicating a lack of originality and effort), and you reply with a canned answer (thus indicating some degree of memorization but not really sharing any insights into whether or not you'd be a good fit for the position).For this question, I'd first give the interviewer the you've got to be kidding me - are we really going down this road? stare, then I'd start asking questions:how many parking spots are we talking about?how many cars can we move at a time?are any cars double-parked (i.e., blocked by other cars)?are any spots easier to access than others (i.e., geography concerns)what's the expected arrival/departure of the cars?how long will the cars typically stay there?do we know in advance when a particular car will leave?and finally, define 'optimal' In this instance I would define 'optimal' as minimizing the developer's time.  Write the simplest, easiest to understand and maintain code and don't worry about any optimization. Making the code run a little faster isn't going to matter, compared to the time required to reposition the cars. See also this relevant XKCD - Is It Worth the Time?. You might spend a couple hundred hours shaving a few milliseconds off your algorithm - which will pay for itself in a few decades.As you can see, the questions tell the interviewer a little bit more about me - how I think, what I consider important, what level of detail I focus on, and so on.  To answer your specific questionSo I ask, what is the most, or at the very least, a more optimal algorithm, to find and switch cars from parking spots of varying sizes?Keep track of which cars are put into over-size spaces.  Hopefully this is the exception, so if your lot has 200 cars you'll only have 10 or 20 in this list.When you need to switch cars around, you can use this list to go directly to the cars that need to be moved.