Apple Interview Question
Software Engineer / DevelopersTeam: Sales
Country: United States
Interview Type: Phone Interview
for maintaining filled slots you can also use Set. Add and remove to and from the Set. All this happens in constant time.
Since we have fixed number of slots, why cant we use a simple stack where slots are pushed farthest to nearest. Nearest spot will be on the top. Keep poping the slots as car arrives. Push the slot when a car leaves.
Since the parking lot size is fixed, why cant we use a simple stack? You can push the slots farthest to nearest. Nearest one will be at the top. Keep poping the slots as the cars arrive. Push the slot back in when the car leaves.
simple stack won't work unless cars leave in farthest to nearest order. since a stack only adds to back, if a car that is nearer to entrance leaves before a car that is farther, the further will be returned first. a priority queue which assigns priority according to distance from entrance is better
Adding OO Code using PriorityQueue. You can enhance this to use a blocking queue if multiple entrances/exits exist.
public class ParkingLot {
private static final int maxFloors = 5;
private static final int maxSlotsPerFloor = 10;
private PriorityQueue<ParkingSpace> pq = new PriorityQueue<ParkingLot.ParkingSpace>((maxFloors * maxSlotsPerFloor),
new Comparator<ParkingSpace>() {
@Override
public int compare(ParkingSpace o1, ParkingSpace o2) {
if(o1.getFloor() == o2.getFloor()) {
return o1.getSlot() - o2.getSlot();
}
else
return o1.getFloor() - o2.getFloor();
}
}
);
public ParkingSpace park(){
ParkingSpace ps = getNextAvailable();
if(ps == null) {
throw new IllegalStateException("Parking Lot is Full.");
}
pq.remove(ps);
return ps;
}
public void unpark(int floor, int slot) {
ParkingSpace ps = new ParkingSpace(floor, slot);
if(!pq.contains(ps)) {
pq.add(ps);
}
else {
throw new IllegalStateException("Invalid Parking Lot.");
}
}
public void addParkingSpace (int floor, int slot) {
ParkingSpace ps = new ParkingSpace(floor, slot);
pq.add(ps);
}
public ParkingSpace getNextAvailable(){
if(pq.size() > 0)
{
return pq.peek();
}
return null;
}
public static void main(String[] args) {
ParkingLot pl = new ParkingLot();
pl.addParkingSpace(1, 1);
pl.addParkingSpace(2, 1);
pl.addParkingSpace(3, 1);
pl.addParkingSpace(1, 2);
pl.addParkingSpace(2, 2);
pl.addParkingSpace(3, 2);
ParkingSpace n = pl.getNextAvailable();
System.out.println("Parked at Floor: " + n.getFloor() + ", Slot: " + n.getSlot());
pl.unpark(2, n.getSlot());
}
class ParkingSpace {
private int floor;
private int slot;
public int getFloor() {
return floor;
}
public int getSlot() {
return slot;
}
public ParkingSpace(int floor, int slot) {
if(floor > maxFloors || slot > maxSlotsPerFloor) {
throw new IllegalArgumentException("Capacity is 5 floors and 10 slots per floor.");
}
this.floor = floor;
this.slot = slot;
}
@Override
public boolean equals(Object obj) {
if(obj instanceof ParkingSpace) {
ParkingSpace ps = (ParkingSpace) obj;
return (this.getFloor() == ps.getFloor() &&
this.getSlot() == ps.getSlot());
}
return false;
}
}
}
since slots have numbers associated as the closer slot w/ a lower number, sorted tree(heap) to provide the closest slot. an object array represents the occupation, which gives you a quick look up time for availability . a list structure that contains slot object that mappes at the array object will give you all the occupied slots.
when one slot is freed up, throw it back to the heap and heapify
For maintaining the nearest empty slot use min heap. Put the slot when someone leaves and remove and give when someone arrives. For maintaining filled slots use hash map. Remove when someone leaves and add when someone arrives.
- nitiraj February 13, 2014