Microsoft Interview Question Software Engineer / Developers
Country: United States
Interview Type: Phone Interview
A free list is a data structure used in a scheme for dynamic memory allocation. It operates by connecting unallocated regions of memory together in a linked list, using the first word of each unallocated region as a pointer to the next. It's most suitable for allocating from a memory pool, where all objects have the same size.
Free lists make the allocation and deallocation operations very simple. To free a region, one would just link it to the free list. To allocate a region, one would simply remove a single region from the end of the free list and use it. If the regions are variable-sized, one may have to search for a region of large enough size, which can be expensive.
can you please explain more about the data structure and how it work in this scenario? I tried searching over this data structure over the internet but could not get much good info..
At this point, I'm not sure how much memory we have considering we have a million parking spaces.
One possible solution is to use a bit vector. Each spot would be
0: spot available
1: spot occupied.
Thoughts?
Use a priority Queue.
Assuming each parking slot will be having a unique slot number associated with it.and lets also assume that parking spaces on the lower floors get more priority as compared to parking slots on higher floors.
When a new car comes in looking for a parking space just pick pop the top most entry from the Priroty Queue to get the best parking space.
If we use a priority queue here, then how will we be taking the vehicle out of the parking lot?
We need random access to each vehicle. So a map/hash-map is I think the way to go.
Also, the parking space is going to be limited; and we have to think about parking a 2wheeler maybe in an empty slot of a 4 wheeler and vice versa.
@Akheel,
priority q would contain all the AVAILABLE parking lots.
when you take a vehicle out of the parking lot, which means you would free up a parking space, which inturn leads to insertion of the parking space object into the priority queue.
But since there are going to be millions of parking spaces performance could be an issue with this approach.
I believe a bit array data structure will be appropriate. The parking lot can be modeled as a bit array with all 0s to begin with. When the cars begin to fill in turn the 0s at appropriate positions to 1s. Later on, just go through to the array to find the 0s which are still empty spots.
as per my understanding, what is the reason we need to consider only till a group of 10.
say we have an array essentially a integer array in which each array member refers to 100 locations each. The array can take values from 1 to 10 0 saying that there is no place avaible. a value of 1 means that a slot is available in the first 10 slots of the level.
to take it more generic. 100 will be the number of cars a level of car parking can host. and 0 will be the a not available state, and starting from 1 we can basically say whether the slot is available or not, if it is not zero then where it is available.
Thoughts ?
To maintain allotted parking slots, I think dynamic hash array would be better since finding and maintaining is fast.
One vector or dynamically resizeable queue is for maintaining free list of parking slots. The first slot from vector will be allocated for new parking request and details will be stored in hash.
Use Hash<spaceid, Queue<FreeSpaces>>
Hash<spaceid, count of space available in individual queue>
we cannot have all the spaces in memory. So we can cluster the spaces together using some method. Example - if their are 100 spaces, I can use %10 to create 10 spaceids.
now each spaceid will now have 10 spaces. for them we create a queue<free spaces>
whenever a space is required for parking, it is dequeued from queue.
So lets say I want 10 free parking spaces - I will just iterate over the hash<spaceid, count> and get the correspoind spaceids. Then search in Hash<spaceid, queue> and get those free spaces.
Let me know what you think?
Use Hash<spaceid, Queue<FreeSpaces>>
Hash<spaceid, count of space available in individual queue>
we cannot have all the spaces in memory. So we can cluster the spaces together using some method. Example - if their are 100 spaces, I can use %10 to create 10 spaceids.
now each spaceid will now have 10 spaces. for them we create a queue<free spaces>
whenever a space is required for parking, it is dequeued from queue.
So lets say I want 10 free parking spaces - I will just iterate over the hash<spaceid, count> and get the correspoind spaceids. Then search in Hash<spaceid, queue> and get those free spaces.
Let me know what you think?
Use Hash<spaceid, Queue<FreeSpaces>>
Hash<spaceid, count of space available in individual queue>
we cannot have all the spaces in memory. So we can cluster the spaces together using some method. Example - if their are 100 spaces, I can use %10 to create 10 spaceids.
now each spaceid will now have 10 spaces. for them we create a queue<free spaces>
whenever a space is required for parking, it is dequeued from queue.
So lets say I want 10 free parking spaces - I will just iterate over the hash<spaceid, count> and get the correspoind spaceids. Then search in Hash<spaceid, queue> and get those free spaces.
Let me know what you think?
H: Heapify
a: array of parking spaces
CE: Car enters parking lot
CL: car exits/leaves a parking lot
l: left
r: right
H(i, mx)
l = 2*i+1
r = 2*i+2
max = i
if(a[max] < a[l] && l <= mx)
max = l
if(a[max] < a[r] && r <= mx)
max = r
if(max != i)
swap(i, max)
H(i, mx)
a[n] = {0}
CE()
a[0] = 1
H(0,n-1)
CL(i)
a[i] = 0
H(i, n-1)
Use a priority Queue.
Assuming each parking slot will be having a unique slot number associated with it.and lets also assume that parking spaces on the lower floors get more priority as compared to parking slots on higher floors.
When a new car comes in looking for a parking space just pick pop the top most entry from the Priroty Queue to get the best parking space.
What about QuadTree using a map as internal storage element??
private class QuadNode < Value extends Object>
{
QuadNode [] quad ;
Map < String, Value> map;
QuadNode (String key, Value value)
{
if(key== null || value == null)
throw new NullPointerException();
if(quad== null)
quad = new QuadNode[4];
if(map== null)
{
map = new HashMap<>();
map.put(key, value);
}
}
The token for the car can be generated using base4?
So if you have 1 million points, you can first put a few in the map, say if the threshold is 500.
and then split it in 4 quadrants. Time complexity O(n)
Also, you can generate the token id using base 4 , which maps to quadnodes[i] inside the data structure?
Any opinions on that??
Maintain two vectors. One for free slots and one for occupied slots. So whenever we search for free space the free slots vector contains all of the slots that are unoccupied. When a vehicle wants to occupy a free slot , remove that parking slot and insert into the occupied slots vector. Similarly if a Person wants to leave the parking area remove that parking slot from occupied Slots vector and insert it into free slot vector.
Free list?
- Learner February 22, 2012