LRU

LRU Cache - LeetCode

O(1) can be found from other people’s posts. If you want to do it step by step, here is a naive O(n) solution. I hope it helps on understanding this problem.

class LRUCache:

    def __init__(self, capacity: int):
        self.C = capacity
        self.d = {}
        self.key_t = {}
        self.t = 0
        

    def get(self, key: int) -> int:
        self.t += 1
        if key in self.d:
            self.key_t[key]=self.t
            return self.d[key]    
        return -1
        

    def put(self, key: int, value: int) -> None:
        self.t += 1
        if len(self.d)==self.C: 
            # if it is full, if the key is already in the dict, update the key value and update the least information which is recorded in self.key_t
            if key in self.d:
                self.d[key]=value
                self.key_t[key] = self.t
                return
             # if it is full, if the key is not in the dictionary. get least and update the dictionary. 
            least_key, _ = min([(k, self.key_t[k]) for k in self.d], key=lambda x:x[1])
            del self.d[least_key]
            del self.key_t[least_key]
            self.d[key]=value
            self.key_t[key] = self.t
        else:
            self.d[key]=value
            self.key_t[key] = self.t
               
# Your LRUCache object will be instantiated and called as such:
# obj = LRUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)