Searching for first set bit in a huge bitmap

Question

Interview question:

In a parking slot which can hold million cars, you need to find a free parking slot. There is no condition on where the slot could be, i.e., the parking lot can have multiple entrances and finding a slot near the entrance, etc., does not matter. The question was what kind of data structure should be used and what would be complexity of various operations.

I suggested using a bit array of million bits, with 0/1 for taken/free slot, so for finding free spot the question translated to finding first set bit. Do not assume anything about how many cars are there, etc., i.e., the bit array could be sparse or dense.

What is the fastest way to find a set bit in a huge bitmap? I did suggest binary search + efficient ffs() per word as the scheme.

Answer 1

A million 32-bit integers require about 4MB of memory. So I'd say you keep a list of free slots. Whenever a car enters, you take an item off the list and assign that. Whenever a car leaves, you put the freed slot number into the list.

As you'd only ever be manipulating the end of the list (so this is in fact used as a stack or LIFO structure), this gives you optimal O(1) performance both for finding a free slot and for returning a slot to free state. If you do this on a low level with a raw chunk of memory, you'll need a pointer indicating the current end of the list. Finding a slot decrements that pointer and returns its value. Returning a slot assigns to the pointer and increments it afterwards.

If you decide to add additional requirements later on, you could do some manipulation of your data, e.g. turn it into a heap. With a big map of 0/1 bits, such extensions wouldn't be possible.