Saturday, September 3, 2011

Amazon Question: Design LRUCache

It was told that cache will have a key, value pair(int, int).

Solution is to take hash with key as cache key and value is Node where Node is the address of the node in the linked list which contains the same key. Linked list node contains cache key and cache value.


Insert Operation --
  1. Make a node "Node" with key and value and put that node at the end of linked list. 
  2. if count of nodes are more than cache size then remove head node from linked list , also remove hash[head->key].
  3. Update hash as hash[Node->key] = Node

Get Operation --
  1. Get operation will return the cache value of given cache key. Also now it will make this key is the most recently used one.
  2. Get the Node by hash[key] and move that Node at the end of linked list.
  3. Return hash[key]->value.   

Source Code:

struct Node
{
    int key;
    int value;
    Node* next;
    Node(int k, int v, Node* ptr=NULL):key(k), value(v), next(ptr){}
};

class List
{
public:
    List();
    Node* insert(int k, int v);
    Node* remove();
    Node* move(Node* node);
    void swap(Node* node1, Node* node2);
private:
    Node* head;
    Node* tail;
};

class LRUCache
{
public:
    LRUCache(int n);                 // cache can contain maximum of "n" elements
    bool put(int key, int value);   // insert the key value pair in cache
    int get(int key);                 // get the value of the given key, also it updates the lru table as it is the recently used item
 
private:
    int count;
    const int size;
    map<int, Node*> hashMap;
    List list;
};

// Function definitions -- .cpp file

List::List():head(0), tail(0)
{
}

Node* List::insert(int k, int v)
{
    Node* temp = new Node(k, v);
    if(!head)
    {
        head = temp;
        tail = temp;
    }
    else
    {
        tail->next = temp;
        tail = temp;
    }
    return temp;
}

Node* List::remove()
{
    Node* temp = head;
    if(temp == NULL)
        return NULL;
    if(temp == tail)
    {
        tail = NULL;
        head = NULL;
    }
    else
    {
        head = head->next;
    }
    return temp;
}

Node* List::move(Node* node)
{
    if(node == NULL)
        return NULL;
    if(node == tail)
        return tail;
    if(node == head)
    {
        Node* temp = head;
        head = head->next;
        tail->next = temp;
        tail = temp;
        tail->next = NULL;
        return tail;
    }
   
    Node* temp = node->next;
   
    swap(node, temp);
   
    if(temp != tail)
    {
        node->next = temp->next;
        tail->next = temp;
        temp->next = NULL;
        tail = temp;
    }

    return tail;
}

void List::swap(Node* node1, Node* node2)
{
    //Swap Keys
    node1->key = (node2->key)^(node1->key);
    node2->key = (node2->key)^(node1->key);
    node1->key = (node2->key)^(node1->key);
   
    //Swap Values
    node1->value = (node2->value)^(node1->value);
    node2->value = (node2->value)^(node1->value);
    node1->value = (node2->value)^(node1->value);
}

LRUCache::LRUCache(int n):size(n), count(0)
{
}

bool LRUCache::put(int key, int value)
{
    if(hashMap.find(key) != hashMap.end())
    {
        return false;
    }
    if(count < size)
    {
        count++;
        Node* temp = list.insert(key, value);
        hashMap[key] = temp;
    }
    else
    {
        Node* temp = list.remove();
        if(temp)
        {
            hashMap.erase(temp->key);
            delete temp;
            temp = list.insert(key, value);
            hashMap[key] = temp;
        }
        else
            return false;
    }
   
    return true;
}

int LRUCache::get(int key)
{
    int ret = -9999; //error value
    if(hashMap.find(key) != hashMap.end())
    {
        Node* temp1 = hashMap[key];
        ret = temp1->value;
        Node* temp2 = list.move(temp1);
        hashMap[key] = temp2;
        hashMap[temp1->key] = temp1;
    }
    return ret;
}

4 comments:

  1. better yet, use a min priority queue. When a get operation is performed increase the weight of the node by increase_key(node) method. At any point the LRU element will be at the top.

    ReplyDelete
  2. @Shubham... that will not be at O(1)

    ReplyDelete