leetcode-design

146. LRU Cache.py

class LRUCache:
    """
    把最近一次使用的放到ordercit的end端, 最後沒被使用的放在beginning端
    
    1.we need a hashmap to help us to find a key in O(1)
    2.each time when get and put method is invoked, we need doubly-linked-list to put the key into the end (latest data) and remove the data associated this key in O(1)
    """
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.od = collections.OrderedDict()

    def get(self, key: int) -> int:
        if key not in self.od:
            return -1
        self.od.move_to_end(key)
        return self.od[key]

    def put(self, key: int, value: int) -> None:
        if key in self.od:
            self.od.move_to_end(key)
        self.od[key] = value
        if len(self.od) > self.capacity:
            self.od.popitem(last=False)
            

class Node:
    def __init__(self, k=None, v=None):
        """node in doubly linked-list"""
        self.key = k
        self.value = v
        self.next = None
        self.prev = None
        
class LRUCache:
    """
    Thought Prcoess: Queue + Dict, where, we use doubly linked list to implement queue.
    
    capacicy = how many data we can store in the cache at most?
    
    Idea is using Doubly Linked List to maintain most recencly used nodes with size of capacity because it provides insert/delete in O(1). Also, it maintains chronological order. It's like queue, FIFO.
    
    oldest                      latest
    .... <-> n1 <-> n2 <-> n3 -> ....
             k1    k2     k3
    
    dict = {k1: n2, k2:n2, k3:n3}, dictionary provides us to access node in O(1)
    """
    def __init__(self, capacity: int):
        self.cap = capacity
        self.dict = {} # {key:Node}
        self.head = Node()
        self.tail = Node()
        self.head.next, self.tail.prev = self.tail, self.head
        
    def _add(self, n):
        """add node into the rightmost of q (least recently used node), which represent it"""
        l, r = self.tail.prev, self.tail
        l.next = r.prev = n
        n.prev, n.next = l, r
        
    def _remove(self, n):
        """remove node n from linked-list"""
        l, r = n.prev, n.next
        l.next, r.prev = r, l
    
    def _pop(self):
        """remove oldest node in the queue(the leftmost)"""
        n = self.head.next
        self._remove(n)
        return n
    
    def get(self, key: int) -> int:
        if key in self.dict:
            n = self.dict[key]
            # to make the node n least recently
            self._remove(n)
            self._add(n)
            return n.value
        return -1

    def put(self, key: int, value: int) -> None:
        # if key exists, update value
        if key in self.dict:
            self._remove(self.dict[key])
        n = Node(key, value)
        self._add(n)
        self.dict[key] = n
        # if exceeds capacity
        if len(self.dict) > self.cap:
            # delete the oldest node in the linked list
            del self.dict[self._pop().key]


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