Google Interview Question Software Engineer / Developers
You need a doubly link list to be able to delete and move the item to the beginning. With a singly linked list, you would need to also have (apart from the pointer to the node to be removed) the pointer to the 'prev' element to delete/move an item.
We do not need a doubly linked list. The list is always sorted in the LRU ordering.
if(cache miss)
head is the candidate for removal
else if(cache hit){
// we have to put the cache hit object to the end of the list
if(cache hit object is tail)
do nothing
else
copy the next node to current node and remove the next node
}
How about using a Min Heap with Least recently used node(based on time stamp of access) as the root?
What if you use a hash table, and separately maintaining the least recently used item in another variable / file / hardware unit. Then whenever a new item is inserted, you could check if its last usage is older than the current max, and replace if necessary. The problem with this is that when the max item gets deleted, finding the next max item is no longer O(1).
One possible way to solve this is by using a stack. Ie, when a node is inserted, if its last used time is greater than the top of the stack, push it on. When a node gets deleted, check if it is the top element of the stack. If so, pop, and the next operation becomes the LRU. If the deleted element is present elsewhere on the stack, don't worry about it. Eventually when you do get down it, you can check back with the hash table to see if it exists. If it doesn't, pop and move down to the next node.
However, this still has a problem. Since this is a cache we're talking about, its perfectly possible that the timestamps on any of the elements on the stack could change after they've been pushed. For instance, let the memory locations be a,b,c,... Initially, the stack is ordered as:
b
a
c
--
Now, 'a' gets accessed, so strictly speaking, the stack should look like:
b
c
a
--
but it doesn't. So if 'b' gets deleted, then we get a faulty answer from the stack. This is where I'm stuck, and I would look at the interviewer for a clue... ;)
Use a doubly linked list, instead of stack. Whenever an item is accessed remove it and put it at the top. The LRU item will always be at the end. (i.e tail). You should have a pointer to tail(say T) to remove LRU item fast. Its a double linked list instead of single, bcos you can update the T with T->prev
good one by Thiyaneshwaran. just to add one point : To find least recently used item when u have full emory and u want to delete any item before u can insert the next one. it will be at the tail of doubly linked list.
but here space used: 2*content size+2*(space for pointer)*no of items
space used is too much dont u think so ??
Use a Hashmap along with doubly linked list.
- Thiyaneshwaran S November 08, 2009Insertion: When an element is inserted into the hashmap create a new node at the front of the doubly linked list. The hashmap entry will have the reference to this node in the douly linked list. Also the node in the liked list will have a reference to the entry in the hashmap.
So Insertion : O(1)
Deletion: Delete the entry from the hashmap and also following the reference to the doubly linked list, delete the node too.
So O(1)
Access: Get the element in the hashmap, follow the reference to the doubly linked list and just move this node in the doubly linked list to the front of the list.
Recently used: Get the first element from the linked list.
So Access: O(1)