Cisco Systems Interview Question
Software Engineer / DevelopersCountry: India
Interview Type: Written Test
I think, we can keep two pointers (FreeList, AllocatedList). Initially AllocatedList will be null, and FreeList pointing to the first cell in the 5X5 matrix. All the cells in the matrix are connected via doubly linked list.
When a Car comes, it can find the free slot by getting the first cell from FreeList, once the car is parked, we need to insert that cell to the AllocatedList (may be at the beginning of the List) and give the node address as Parking token (or the index of the cell if it is continuously allocated).
So getting a free slot is O(1) and returning the free slot is also O(1) if Parking token is used.
do a 5x5 array pointer with type of the structure you wish to allocate. Point them to null so they all point something. Then allocate them by finding what first elements is pointing to null. The reason why link list is not a good idea to use is because link list is used for dynamic listing, where in this problem is finite listing (5x5).
we do not need to allocate a 5x5 Matrix because everything gets allocated in a linear order(1-D).
- c.pc8 October 08, 2013Using only singly linked list can solve the problem.
skip this if you heard of headernode
headernode (structure) has two fields a data part, and other pointer to a structure part, data part stores the no of elements in Linked list.
so, if (headernode->data)<25 then there is space available in parking lot.
Insertion & Deletion is done at very low complexity in linked list so, using this as a DS for parking a car in the lot, and driving it away wont be a problem at all.