LC146 LRU Cache

time O(N) space O(N)

class LRUCache:
    # data structure queue,  store key and value
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.queue = deque()

    # find index from queue based on key; else return -1
    def _find(self, key):
        for i in range(len(self.queue)): # time O(N)
            tup = self.queue[i]
            if tup[0] == key:
                return i
        return -1

    def get(self, key: int) -> int:
        if self._find(key) == -1:
            return -1
        # remove the k,v and append to tail
        index = self._find(key)
        k,v = self.queue[index]
        del self.queue[index]                  # O(N)
        self.queue.append((k,v))
        return v 
    
    def put(self, key: int, value: int) -> None:
        # check if exist:  1. exist 1.a remove ; append to tail 
        #2. not exist: 2.a exceed limit-> remove head value by popleft() then append to tail; 
        #2.b not exceed: append to tail
        idx = self._find(key)
        if idx == -1:
            if len(self.queue) == self.capacity:
                self.queue.popleft()
        else:
            del self.queue[idx]
        self.queue.append((key,value))

improvement: use dictionary to store key and value ; use queue to track the order of key with LRU feature;

from collections import deque
# time O(N) space O(N)
class LRUCache:
    # data structure queue,  store key and value
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.queue = deque()
        self.valueMap = dict()
    # find index from queue based on key; else return -1

    def get(self, key: int) -> int:
        if key not in self.valueMap:
            return -1
        else:
            self.queue.remove(key)
            self.queue.append(key)
            return self.valueMap[key]
    
    def put(self, key: int, value: int) -> None:
        # check if exist:  1. exist 1.a remove ; append to tail 
        #2. not exist: 2.a exceed limit-> remove head value by popleft() then append to tail;
        #2.b not exceed: append to tail
        if key not in self.valueMap:
            if len(self.queue) == self.capacity:
                temp = self.queue.popleft()
                del self.valueMap[temp]
        else:
            self.queue.remove(key)
        self.queue.append(key)
        self.valueMap[key]=value

solution 3: double linkedlist + dictionary to store reference of node, where each node store key, val, prev, head

#time O(1) space O(N)
class LRUCache:
    # data structure: linkedlist, each node store k,v, ;  use dictionay to store node reference
    class Node:
        def __init__(self,k=-1,v=-1):
            self.k = k 
            self.v = v
            self.prev = None
            self.nxt = None
            
    def __init__(self, capacity: int):
        self.size = capacity 
        self.cnt = 0
        self.d = {} # {key: Node}
        self.head = self.Node()
        self.tail = self.Node()
        self.head.nxt = self.tail
        self.tail.prev = self.head
    
     # tc O(1) sc O(1)    1.remove entry in hashmap 2.remove node in DLList 
    def _remove(self,node)-> None:
        del self.d[node.k]
        node.prev.nxt = node.nxt
        node.nxt.prev = node.prev
        #self.cnt -= 1 

 # tc O(1) sc O(1)    check if key in hashmap : yes --   1. remove current node 2. put new key,val pair Node;  no --- return -1 
    def get(self, key: int) -> int:
        if key in self.d:
            node = self.d[key]
            val = node.v # cache value  
            self._remove(node) 
            self.put(key,val)
            return  val
        return -1 
    
#tc O(1)  sc O(N)  1. check if key in hashmap  yes: remove existing node 2. add new node 3. check if current DLList exceed capacity, remove last node in the tail  
    def put(self, key: int, value: int) -> None:
        if key in self.d:# process updated value for same key 
            node = self.d[key]
            self._remove(node)
        new_node = self.Node(key,value)
        new_node.nxt = self.head.nxt
        self.head.nxt = new_node
        new_node.nxt.prev = new_node
        new_node.prev = self.head
        self.d[key] = new_node
        #self.cnt += 1 
        if len(self.d) > self.size: # self.cnt > self.size   
            last = self.tail.prev 
            self._remove(last)
                

    
    # case1: remove node next to head; case2:remove next to rear; case3: remove bewteen normal  ===> catually make no diff 
    def _remove(self,node):
        node.prev.next = node.next
        node.next.prev = node.prev
    
    def _insert_to_tail(self,node):
        self.rear.prev.next = node
        node.prev = self.rear.prev
        node.next = self.rear
        self.rear.prev = node 

lazy solution: use OrderedDict from python collections lib

from collections import OrderedDict
class LRUCache:
    # data structure: OrderedDict
    def __init__(self,capacity):
        self.cap = capacity
        self.cache = OrderedDict()
      
    def get(self,key):
        if key not in self.cache:
            return -1
        v = self.cache.pop(key)
        self.cache[key] = v
        return v

    def put(self,key,value):
        if key in self.cache:
            self.cache.pop(key)
            self.cache[key] = value
        else:
            self.cache[key] = value
            if len(self.cache)> self.cap:
                self.cache.popitem(last=False)
            