## Interview Question

Country: India

Comment hidden because of low score. Click to expand.
2
of 2 vote

Hashtable + Doubly Linked List is the standard O(1) (expected) solution for LRU cache.

Comment hidden because of low score. Click to expand.
0

Correct. LinkedHashMap is ideal choice for LRU cache. We would require to overwrite the following method

``````private static final int MAX_ENTRIES = 100;

protected boolean removeEldestEntry(Map.Entry eldest) {
return size() > MAX_ENTRIES;``````

}

Comment hidden because of low score. Click to expand.
0

The key data structure of the algorithm is the combination of Hash Map and Doubly-Linked List. We initialize a Hash Map in a per-defined size to store pairs, and use Doubly-Linked List to index the pairs in the order of data age.

Here is C++ code for LRU,

#include <iostream>
#include <vector>
#include <hash_map>

using namespace std;
using namespace stdext;

template<class K, class T>
struct LRUCacheEntry
{
K key;
T data;
LRUCacheEntry* prev;
LRUCacheEntry* next;
};

template<class K, class T>
class LRUCache
{
private:
hash_map< K, LRUCacheEntry<K,T>* > _mapping;
vector< LRUCacheEntry<K,T>* > _freeEntries;
LRUCacheEntry<K,T> * tail;
LRUCacheEntry<K,T> * entries;
public:
LRUCache(size_t size){
entries = new LRUCacheEntry<K,T>[size];
for (int i=0; i<size; i++)
_freeEntries.push_back(entries+i);
tail = new LRUCacheEntry<K,T>;
tail->next = NULL;
}
~LRUCache()
{
delete tail;
delete [] entries;
}
void put(K key, T data)
{
LRUCacheEntry<K,T>* node = _mapping[key];
if(node)
{
detach(node);
node->data = data;
attach(node);
}
else{
if ( _freeEntries.empty() )
{
node = tail->prev;
detach(node);
_mapping.erase(node->key);
node->data = data;
node->key = key;
attach(node);
}
else{
node = _freeEntries.back();
_freeEntries.pop_back();
node->key = key;
node->data = data;
_mapping[key] = node;
attach(node);
}
}
}

T get(K key)
{
LRUCacheEntry<K,T>* node = _mapping[key];
if(node)
{
detach(node);
attach(node);
return node->data;
}
else return NULL;
}

private:
void detach(LRUCacheEntry<K,T>* node)
{
node->prev->next = node->next;
node->next->prev = node->prev;
}
void attach(LRUCacheEntry<K,T>* node)
{
node->next->prev = node;
}
};

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.