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?