Leetcode: LRU Cache

By | 2018 年 7 月 18 日

Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and put.

get(key) – Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
put(key, value) – Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.

Follow up:
Could you do both operations in O(1) time complexity?

Analyze

For get(key), if we want it to be O(1) time complexity, a hash map is needed to map from key to value.

For put(key, value), if total count below capacity, hash map works fine. However, when we consider the LRU requirement, that needs to discard the least recently used element. Hash map is not enough to solve this problem with O(1).

The key here is to find out the least recently used element.

One possible solution is to record a counter with each element, and each time cache get accessed, increase it by 1. And when the time comes, just find out the one with maximum age. This is how it works in hardware. But hardware can do this with O(1). While in the software, we can only do this in O(n). So this is not the target solution here.

Another possible solution is to record the age as position in a list. e.g. in a linked list, we can insert / delete / move node in O(1) time. We can define that the head of list is the newest one, while the tail stores the oldest. In this design:

  • when insert an element, just push it to the head;
  • when capacity reached, we can delete the tail and push a new one to the head;

We can do both of them in O(1) time, almost there. However, when a node in the middle get hit by get(key) method, we need to move that node to the head. In the single direction link list, we can’t do this in O(1), cause we need firstly find the previous node of the given node, this will take O(n). In order to make this in O(1), double-linked list is needed. If we store previous node pointer in each node, then this operation can also get done in O(1).

Thus, this solution can serve all the following operations in O(1):

  • get(key), first check the map get the node pointer if exists, then move the target node in the linked list to the head;
  • put(key, value) while still has space, just create a new node in the head of linked list and record it in the hash map;
  • put(key, value) while capacity reached, instead of delete / create, we can just get the tail of link list, delete the key (old key) from the map, move the node to the head and reassign it’s key/value with the current value, and record the new mapping in the hash map.

Issues

  • be careful about the node moving in link list, there are too many pointers needs modify. can draw a graph to help enumerate all the pointers.
  • std::map<int, Node*>, [] accessor and erase(key) method usage.
  • need initialize the values of private field in c++ class, or it gets random values. e.g. the head, tail, and _size of LinkList class below.

Solution

C++, 98%

struct Node {
    Node* previous = NULL;
    Node* next = NULL;
    int value;
    int key;
};

class LinkList {
private:
    Node* head;
    Node* tail;
    int _size;
public:
    LinkList() {
        head = NULL;
        tail = NULL;
        _size = 0;
    }

    ~LinkList() {
        while(head != NULL) {
            // cout<<"delete "<<head->key<<endl;
            Node* node = head;
            head = head->next;
            delete node;
        }
    }

    int size() {
        return _size;
    }

    void printList() {
        return;
        Node* node = head;
        while(node != NULL) {
            cout<<node->key<<"->";
            node = node->next;
        }
        cout<<endl;
        node = tail;
        while(node != NULL) {
            cout<<node->key<<"<-";
            node = node->previous;
        }
        cout<<endl;
    }

    Node* pushAhead(int key, int val) {
        Node* node = new Node();
        node->value = val;
        node->key = key;
        if (head == NULL) {
            head = tail = node;
        } else {
            node->next = head;
            head->previous = node;
            head = node;
        }
        ++_size;
        return node;
    }

    void moveAhead(Node* node) {
        if (head == node)
            return;
        if (tail == node) {
            tail = node->previous;
        }
        node->previous->next = node->next;
        if(node->next) {
            node->next->previous = node->previous;
        }
        node->previous = NULL;
        node->next = head;
        head->previous = node;
        head = node;
    }

    Node* getTail() {
        return tail;
    }

    Node* refreshLast(int key, int val) {
        if (0 == _size)
            return NULL;
        tail->value = val;
        tail->key = key;
        moveAhead(tail);
        return head;
    }
};

class LRUCache {
private:
    LinkList linkList;
    std::map<int, Node*> map;
    int capacity;
public:
    LRUCache(int capacity) {
        this->capacity = capacity;
    }

    int get(int key) {
        // cout<<"get "<<key<<endl;
        Node* node = map[key];
        if (NULL == node) {
            // linkList.printList();
            return -1;
        } else {
            linkList.moveAhead(node);
            // linkList.printList();
            return node->value;
        }
    }

    void put(int key, int value) {
        // cout<<"put "<<key<<endl;
        Node* node = map[key];
        if (NULL != node) {
            // cout<<"update "<<value<<endl;
            node->value = value;
            linkList.moveAhead(node);
            // linkList.printList();
            return;
        }
        if(linkList.size() == capacity) {
            // cout<<"refresh "<<value<<endl;
            node = linkList.getTail();
            map.erase(node->key);
            node = linkList.refreshLast(key, value);
        } else {
            // cout<<"append "<<value<<endl;
            node = linkList.pushAhead(key, value);
        }
        map[key] = node;
        // linkList.printList();
    }
};

发表评论

电子邮件地址不会被公开。 必填项已用*标注