Amazon Interview Question
Software Engineer / Developersu can find the class structure here:
google for: amazon-interview-question-design-an-oo-parking-lot/764955#764955
But for park() unpark() I think we would a hashtable ,
So a ParkingLot class would have a method say
{public assignSlotToCar(Car car); }
-> which would take in the car as the argument
and compute a hash-function to deliver a bucket(parking slot) for the car,only condition would be that the slot should be the same as the car, e.g. for a compact car, mid-size car, etc
Not sure about unpark() - should it just be a remove element form the hashtable ?
for the park() to be performed in constant time we can use a max-heap of the available parking spaces based on the value of a rank (computed separately e.g distance from the gate)
when a request for park comes we just remove the root element.
when parking space gets free it is added to the tree
for unpark to be performed in constant time we would need a hash table with carNo as the key and parkingspace object as the value.
to free we just remove the value from hash table and add the the available parking space tree
A hash table would be needed only to ensure that unpark() is executed in constant time.
- jack March 30, 2010Once a Car is parked we need a mapping between the Car (identified by reg number) and the slop. And it must be added to the hash table.
For Park() just maintaining a free list would do. Once we execute Unpark() that slot must be added to the free list.