Amazon Interview Question Software Engineer / Developers
1of 1 voteImplement an LRU cache
Hi Shar3oob,
In the previous solution where are you maintaining the LRU element, every time you access an element you'll have to update the least recently used element which will be a little more time consuming than O(1).
Also I dont understand what is the use of maintaining a list, I suppose cache will be of a constant size so we can just maintain an array and store the index of the array in the hash table instead of storing a pointer(which will take more space)
Thanks,
Loony
in Array i think the problem will be in updation . Since in LRU u move the most recenlty used item to the TOP then in array u have to shift all the elements 1 by 1 . Which I think is more complex then in LinkLists as it might take worst case O(n) .
and a hash is mantained so as to quickly index what is the current location of the item . rather than traversing the LinkList..
Hope this helps
public class LRUCache<K,V>{
private MyLinkedHashMap<K,V> cache;
private final int cache_size;
public LRUCache(int size){
cache_size = size;
this.cache = new MyLinkedHashMap<K,V>(){
protected boolean removeEldestEntry(MyLinkedHashMap.Entry<K,V> eldest){
//System.out.println("remove Eldest entry: " + (cache_size >= size()));
return cache_size < size();
}
};
}
public V get(K key){
return cache.get(key);
}
public void put(K key, V value){
cache.put(key,value);
}
public boolean containsKey(K key){
return cache.containsKey(key);
}
public void print(){
cache.print();
}
public void printTable(){
this.cache.printTable();
}
}
Maintain two data structures. A linked list and a hash table. The hash table should contain the (key, pointer), where pointer is a pointer to the element in the linked list. LRU evicts the least recently used element from the cache. On removing an element, remove from both the linked list and the hash table. On requesting an element, move it to head of the linked list.
- Shar3oob May 25, 2009This solution is O(1) time complexity. Space complexity is O(n)