1

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?

4
  • For any reasonable number of parking lots of a real-world area, O(n) is probably fine. But FWIW, you can lower this order by managing six different hashsets of occupied spots, separated by their size as well as the size of the car by the space it is occupied (you need six and not nine because a bigger car does not fit in a smaller space, I guess this is obvious). Updating these hashsets when a car gets parked or moved is O(1), checking the hashsets if there is a smaller car on a larger space is O(1), too.
    – Doc Brown
    Commented Aug 31, 2016 at 17:41
  • @DocBrown Why is checking the hashsets if there is a smaller car on a smaller space O(1) time?
    – TheFooh
    Commented Aug 31, 2016 at 18:31
  • For parking a medium sized car, you have exactly 3 sets to check: the "large space occupied with medium car" set, the "large space occupied with small car" set and the "medium space occupied with small car" set. For large cars, you only need to check the first two. Each check is a test if the set is empty, which should be O(1) operation on any sensible hashset implementation, as well as to find one arbitrary element in the set if it is not empty.
    – Doc Brown
    Commented Aug 31, 2016 at 20:24
  • softwareengineering.stackexchange.com/questions/389316/…
    – user317612
    Commented Mar 27, 2019 at 18:11

1 Answer 1

Reset to default
2

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:

  1. how many parking spots are we talking about?
  2. how many cars can we move at a time?
  3. are any cars double-parked (i.e., blocked by other cars)?
  4. are any spots easier to access than others (i.e., geography concerns)
  5. what's the expected arrival/departure of the cars?
  6. how long will the cars typically stay there?
  7. do we know in advance when a particular car will leave?

and finally,

  1. 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 question

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?

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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.