Achieve Internet Interview Question Software Engineer / Developers
Priority Queues work when you want to determine which page is to be replaced... we replace the one with least priority...
but cache should also allow access to any element.. which is not possible with priority queues.. right?
This is my idea -
Run a timer (counts 1, 2, 3, ...). At each time click, a page has to be loaded. It may either be in memory or in the back-store. Do the following operations.
1. Assume that the memory supports only K pages max. Let the first k pages needed be p1, p2, ... , pk. Now form a min heap with all the k pages. The key of each element in the heap must be the time at which (the counter time) the page has been accessed. The reason I am using a min-heap here is, I need to replace the oldest (with minimum time) with the newest one. So finding the oldest is made very simple when a min-heap is used.
2. After the first k pages, for any page pT (got at time T) we need to insert the page pT in the heap if it is not already present. If present, we must change its time to T. So we need to check whether a page is present or not. For that use a hash. H(p) is true if the page is present. Else it is false.
3. If H(p) is false, it is easy. Pop out the minimum element from the min-heap. Set the hash of that element to false, and insert this element in the heap. Set the hash for the new element true.
4. If H(p) is true, it means the page is available in memory. So I just need to adjust the element's key (time). However, for this I need to find the element in the heap first. To optimize this, instead of using the Hash to show true or false, Hash shows null if the page is not present and a pointer to the node in the min-heap if it is present.
I would have said a single link list had hash not been a friend of Heap in the solution given by MKR. So far to me it seems the perfect solution with O(1) lookup and O(logn) insertion and deletion time.
Ok, something clicking in my mind what if i use a hash and a single link list.
With the same concept as that of MKR hash would store a NULL if the page is not present in the memory o.w. pointer to that page in the list.
In case of a pagefault you have O(1) lookup and O(1) insertion time just add the new page to the front of the list. The page being moved out shall be the last page do update the hash table entry accordingly.
if the page is in the memory all you need to do is bring it to the front.
This will not only avoid maintaining the timer field but will give you O(1) insertion and deletion time.
Any expert comments. What do you think MKR? Am i missing something?
Queues... or Priority Queues if we need to put some priority on few caches...
- Anonymous February 14, 2010