Clever Geek Handbook

Finding free space in a huge memory space

The actual question is: What data structure will you use to find free parking spaces in a garage with millions of spaces?

What I thought:

  • I could use LinkedHashMap

    and keep moving the empty seats to the queue, but I don't think this is the right solution.

Any thoughts?

+3


source to share


6 answers


You already know the size of your parking lot (million slots), which physically makes sense. So if you need all the information you need, whether there will be many vacancies, then use a bit array where the vacancy is false and busy, it is true.

boolean slots[] = new boolean[1000000];

If you need to store more information like information about a car in a slot, distance from the slot from the nearest entrance, etc., use:

 Slot[] slots = new Slot[1000000];


and the Slot class would be like

public class Slot{
    Car car;//object for car in slot
    boolean occupied;//whether slot is vacant: may be redundant
    Cost cost;//a set of fields: distance from entrance; parking fee for "good" slots, etc.
}

And so you continue ...

+1


source


PriorityQueue, where priority is defined as the distance between the parking space and the entrance.



0


source


I would use a bit-set where each bit represents a parking spot. A value of 1 is free and 0 to use. A linear search for empty seats should do the job. Very easy to implement and fast enough with asm.

0


source


Improving on kasavbere's solution, I would suggest using BitSet / BitArray if you have the option. BitSet uses arrays of longs with each long value representing 64 slots. This effectively reduces the total size of the array by a factor of 8 compared to boolean ones [Arrays of boolean elements usually take 1 byte per element] . BitSet also provides methods to get the next set or free slot from a specific index, so you don't need to write your own method to do this.

0


source


We can use a queue.

The queue contains all millions of records at the beginning. If a parking space is needed , dequeue . If the parking space becomes free , enque .

0


source


  • Maintaining an array that basically stores 1 - n cars, where n is the size of the parking space. Maintain a minimum heap (PriorityQueue) of parking numbers. Every time a new car arrives, check if the array is full, not by polling the queue for the nearest lot number. Polling removes the smallest from the queue and uses it as the array index.

Once the car leaves the seat, add that seat back to the queue. A future poll will return the nearest parking lot.

0


source






More articles:


All Articles