146. LRU Cache

LeetCode 146. LRU Cache

Description

Design a data structure that follows the constraints of a Least Recently Used (LRU) cache.

Implement the LRUCache class:

• LRUCache(int capacity) Initialize the LRU cache with positive size capacity.

• int get(int key) Return the value of the key if the key exists, otherwise return -1.

• void put(int key, int value) Update the value of the key if the key exists. Otherwise, add the key-value pair to the cache. If the number of keys exceeds the capacity from this operation, evict the least recently used key.

Follow up: Could you do get and put in O(1) time complexity?

Example 1:

Input
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
Output
[null, null, null, 1, null, -1, null, -1, 3, 4]

Explanation
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // cache is {1=1}
lRUCache.put(2, 2); // cache is {1=1, 2=2}
lRUCache.get(1);    // return 1
lRUCache.put(3, 3); // LRU key was 2, evicts key 2, cache is {1=1, 3=3}
lRUCache.get(2);    // returns -1 (not found)
lRUCache.put(4, 4); // LRU key was 1, evicts key 1, cache is {4=4, 3=3}
lRUCache.get(1);    // return -1 (not found)
lRUCache.get(3);    // return 3
lRUCache.get(4);    // return 4

Constraints:

• 1 <= capacity <= 3000

• 0 <= key <= 3000

• 0 <= value <= 10^4

• At most 3 * 10^4 calls will be made to get and put.

Tags

Design

Solution

We use both linked list (node{key, value}) and hash table (key:node) to construct the LRU Cache.

Get. Check if we can obtain a node from the hash table with the given key. If it exists, we move the node to the front of the linked list and return the value stored in the node. Otherwise, return -1.

Put. Check if we can obtain a node from the hash table with the given key. If it exists, we modify the value of the node and move it to the front of the linked list. Otherwise, we build a new node with the input key-value pair. Then add it to the hash table and insert it to the head of the linked list. At this time, we have to check if there is an overflow. If the length of hash table is greater than the capacity, we remove the last node of the linked list and delete the key-node pair from the hash table.

Complexity

• Time complexity: $O(1)$

• Space complexity: $O(n)$

Code

type LRUCache struct {
    cap int
    m map[int]*list.Element
    l *list.List
}

type pair struct {
    k, v int
}

func Constructor(capacity int) LRUCache {
    return LRUCache{cap: capacity, m: make(map[int]*list.Element), l: list.New()}
}


func (this *LRUCache) Get(key int) int {
    if ele, ok := this.m[key]; ok {
        this.l.MoveToFront(ele)
        return ele.Value.(pair).v
    }
    return -1
}


func (this *LRUCache) Put(key int, value int)  {
    if ele, ok := this.m[key]; ok {
        ele.Value = pair{key, value}
        this.l.MoveToFront(ele)
        return
    }
    this.m[key] = this.l.PushFront(pair{key, value})
    if len(this.m) > this.cap {
        rear := this.l.Back()
        this.l.Remove(rear)
        delete(this.m, rear.Value.(pair).k)
    }
}

Reference

1. https://books.halfrost.com/leetcode/ChapterThree/LRUCache/