A Parking Lot Problem (Parijat@Oracle)
We have a golf club parking lot with multiple entrances and exits. The parking lot has fixed number of parking spaces, say N. Some spaces are reserved for VIP (n1) and club members (n2). Rest (n3) are general parking spaces. n1 and n2 are smaller percentage of N. n1 < n2 << n3.
The parking rule is that VIP should attempt to park in VIP space if available. If not then tries to park in club member space. Even if that is not available then parks in a general space. The club members first tries to park in a club member space and if not any such available then parks in a general space. Any other car should park only in general spaces. If no space is found following the rule, the requesting car is notified that no space is available.
We design the parking lot as a singleton with three queues implementing the parking space pool. The first queue Q1 has all the available spaces marked VIP category, Q2 has all the available spaces marked club member category and Q3 has all the available general category parking spaces. If you are using Java, you can use ArrayBlockingQueue, which is a synchronized queue. We need synchronized queues as we have mutiple entrances and exits in this parking lot.
Note that the enque and deque functions are O(1) hence this solution is more efficient than having a single queue (popularly known as Priority Queue) or a simple array as the searching a space of a type will be O(n). For Priority Queues you should have either insertion O(n) or the retrieval O(n).
Read full article from A Parking Lot Problem (Parijat@Oracle)
No comments:
Post a Comment