146. LRU Cache

Description

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.

The cache is initialized with a positive capacity.

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

Example:

LRUCache cache = new LRUCache( 2 /* capacity */ );

cache.put(1, 1);
cache.put(2, 2);
cache.get(1);       // returns 1
cache.put(3, 3);    // evicts key 2
cache.get(2);       // returns -1 (not found)
cache.put(4, 4);    // evicts key 1
cache.get(1);       // returns -1 (not found)
cache.get(3);       // returns 3
cache.get(4);       // returns 4

Solutions

1. Hash Table + Double Linked List

# Time: O(1)
# Space: O(n)

class ListNode():
    def __init__(self, key, value):
        self.key = key
        self.val = value
        self.pre = None
        self.next = None

class DoubleLinkedNode():
    def __init__(self):
        self.header = None
        self.tail = None

    def add_head(self, node):
        if not self.header:
            self.header = node
            self.tail = node
        else:
            header = self.header
            self.header = node
            node.next = header
            header.pre = node

    def remove(self, node):
        pre, next = node.pre, node.next
        if pre:
            pre.next = next
        else:
            self.header = next
        
        if next:
            next.pre = pre
        else:
            self.tail = pre
        
        node.pre = None
        node.next = None
        # del node

    def remove_last(self):
        if not self.tail:
            return None
        tail = self.tail
        self.remove(tail)
        return tail

class LRUCache:

    def __init__(self, capacity: int):
        self.capacity = capacity
        self.cache = dict()
        self.size = 0
        self.linkedlist = DoubleLinkedNode()

    def get(self, key: int) -> int:
        if key not in self.cache:
            return -1
        node = self.cache[key]
        self.linkedlist.remove(node)
        self.linkedlist.add_head(node)
        return node.val

    def put(self, key: int, value: int) -> None:
        if key not in self.cache:
            self.size += 1
            node = ListNode(key, value)
            self.cache[key] = node
            self.linkedlist.add_head(node)
        else:
            node = self.cache[key]
            node.val = value
            self.linkedlist.remove(node)
            self.linkedlist.add_head(node)

        if self.size > self.capacity:
            self.size -= 1
            tail = self.linkedlist.remove_last()
            del self.cache[tail.key]

# Your LRUCache object will be instantiated and called as such:
# obj = LRUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)

# 18/18 cases passed (208 ms)
# Your runtime beats 64.76 % of python3 submissions
# Your memory usage beats 6.06 % of python3 submissions (22.5 MB)

References

146. LRU Cache