146. LRU Cache

[sophryu99]

146. LRU Cache

https://leetcode.com/problems/lru-cache/description/

The functions get and put must each run in O(1) average time complexity.

Ordered dict approach Ordered dict: dictionary subclass specially designed to remember the order of items, which is defined by the insertion order of keys.

1. Initialize an ordered dict to keep track of the (key, val) in the input order
2. Get method: returns the value associated with a key, moves the called key to the end of the dict
3. Put method: If the current length of the dict exceeds the capacity, pop the first element from the dictionary. Update the value to the dict.

from collections import OrderedDict

class LRUCache:
    def __init__(self, capacity):
        self.size = capacity
        self.cache = OrderedDict()

    def get(self, key):
        if key not in self.cache: 
            return -1
        val = self.cache[key]
        self.cache.move_to_end(key) # Ordered dict internal function
        return val

    def put(self, key, val):
        if key in self.cache: 
            del self.cache[key]
        self.cache[key] = val
        if len(self.cache) > self.size:
            self.cache.popitem(last=False)

N: number of input cache

• Time Complexity: O(1) with only add, del, move to end operation
• Space Complexity: O(N)

[sophryu99]

Doubly Linked List Approach

class Node:
    def __init__(self, k, v):
        self.key = k
        self.val = v
        self.prev = None
        self.next = None

class LRUCache:
    def __init__(self, capacity):
        self.capacity = capacity
        self.dic = dict()
        self.prev = self.next = self

    def get(self, key):
        if key in self.dic:
            n = self.dic[key]
            self._remove(n)
            self._add(n)
            return n.val
        return -1

    def put(self, key, value):
        if key in self.dic:
            self._remove(self.dic[key])
        n = Node(key, value)
        self._add(n)
        self.dic[key] = n
        if len(self.dic) > self.capacity:
            n = self.next
            self._remove(n)
            del self.dic[n.key]

    def _remove(self, node):
        p = node.prev
        n = node.next
        p.next = n
        n.prev = p

    def _add(self, node):
        p = self.prev
        p.next = node
        self.prev = node
        node.prev = p
        node.next = self