3

The actual question is as follows: What data structure will you use to find free parking spots in a parking garage with million spots?

What I thought:

  • I could use a LinkedHashMap and keep moving the free spots to the front of the queue but I don't think that is the right solution.

Any thoughts?

Seph
  • 8,472
  • 10
  • 63
  • 94
noMAD
  • 7,744
  • 19
  • 56
  • 94
  • Do you care about finding the nearest spot or all "free parking spots"? Is the garage multi-level? How would you determine the cost of going up to the next level compared to driving further on this level? These are all questions you could ask while you think about the solution. – Seph Mar 29 '12 at 11:29
  • 1
    A simple solution will be maintaining static array for all parking spots and a linked list for free spots. First all spots are in free linked list. When a parking request comes, you return head of the link list and remove it from it, also mark it in the array. When a spot frees up, add it to the linked list(mark it in array). – Priyank Bhatnagar Mar 29 '12 at 17:24

6 Answers6

2

You already know the size of your parking structure (one million slots), which physically makes sense. So if all the information you need is whether a lot is vacant, then use a bit array, where vacancy is false and occupied is true

boolean slots[] = new boolean[1000000];

If you need to store more info, such as information of car in the slot, distance of slot from nearest entrance, etc., then use:

 Slot[] slots = new Slot[1000000];

and Slot class would be similar to

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 keep going...

kasavbere
  • 5,873
  • 14
  • 49
  • 72
0
  1. Maintain an array which basically holds 1 - n cars where n is the size of the parking lot. Maintain a min heap (PriorityQueue) of parking lot numbers. Everytime a new car comes in, check if the array is full, is not poll the queue for the nearest lot number. Poll removes the smallest from the queue and use that as the index of the array.

Once a car leaves the spot, add that spot back to the queue. A future poll will return the next nearest parking lot available.

user2100441
  • 1
0

PriorityQueue where priority is defined as a distance between the parking spot and the entrance.

iehrlich
  • 3,572
  • 4
  • 34
  • 43
  • `LinkedHashMap` uses a priority queue. But you cannot store a million nodes in the queue. At least that's what I think. – noMAD Mar 29 '12 at 04:44
0

I would use a bit set, where every bit represents a parking spot. Value 1 for free and 0 for used. A linear search for free spots should do the job. Very easy to implement and with asm fast enough.

knivil
  • 916
  • 5
  • 10
0

Improving kasavbere's solution, I'd suggest using BitSet/BitArray class if you have the option. BitSet uses arrays of longs, with each long value representing 64 slots. This effectively reduces the total size of array by a factor of 8 compared to booleans [Arrays of booleans typically occupy 1 byte per element]. BitSet also provides methods for getting next set or free slot from an particular index so you don't have to write your own method for that.

Community
  • 1
  • 1
Faisal
  • 31
  • 1
  • 2
0

We can use a Queue.

The Queue contains all the million entries at the start. If a parking space is needed, dequeue. If a parking spot becomes free, enque.

Sandeep
  • 7,156
  • 12
  • 45
  • 57