[LC] 146. LRU Cache

Design a data structure that follows the constraints of a Least Recently Used (LRU) cache.

Implement the LRUCache class:

• LRUCache(int capacity) Initialize the LRU cache with positive size capacity.
• int get(int key) Return the value of the key if the key exists, otherwise return -1.
• void put(int key, int value) Update the value of the key if the key exists. Otherwise, add the key-value pair to the cache. If the number of keys exceeds the capacity from this operation, evict the least recently used key.

Follow up:
Could you do get and put in O(1) time complexity?

Approach

Although I’m crazy about the system design, it was my first coding without any reference, and accepted one. I used the priority queue as our basic data structure. To be specific, Max Heap is used for implementing LRU Cache. We can simply save a tuple of (time, key, value) in the max heap. in here, the key is the time which is created by time.time() that returns Epoch time (float). So, I was thinking I can use it as a key and it will be sorted out whenever the tuple is changed. So, every put/get action need at least O(logN) time.

import heapq
import time

class LRUCache:
    cache = []
    size = 0
    def __init__(self, capacity: int):
        self.cache = []
        self.size = capacity
        

    def get(self, key: int) -> int:
        if len(self.cache) == 0:
            return -1
    
        
        if key in [k for t,k,v in self.cache]:
            for i,c in enumerate(self.cache):
                t,k,v = c
                if k == key:
                    t = time.time()
                    self.cache[i] = (t,k,v)
                    heapq.heapify(self.cache)
                    return v
            
        return -1

    def put(self, key: int, value: int) -> None:
        
        if key not in [k for t,k,v in self.cache] and len(self.cache) == self.size:
            heapq.heappop(self.cache)
        
        found = False
        if key in [k for t,k,v in self.cache]:
            for i,c in enumerate(self.cache):
                t,k,v = c
                if k == key:
                    t = time.time()
                    self.cache[i] = (t,k,value)        
                    found = True
                    break
        if not found:   
            t = time.time()
            heapq.heappush(self.cache, (t, key, value))
        else:
            heapq.heapify(self.cache)
    

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

I think it’s okay but the follow-up request gets and puts in O(1) time complexity. I think without a heap, there is no way to sort the cache. The trick is the amortized analysis. If we make a max heap whenever the cache is full, it requires just a few times except every time we put a different key, which has not happened frequently. So, in the revised code, I do the heapify only when the cache is full.

import heapq
import time

class LRUCache:
    cache = []
    size = 0
    def __init__(self, capacity: int):
        self.cache = []
        self.size = capacity
        

    def get(self, key: int) -> int:
        if len(self.cache) == 0:
            return -1
    
        
        if key in [k for t,k,v in self.cache]:
            for i,c in enumerate(self.cache):
                t,k,v = c
                if k == key:
                    t = time.time()
                    self.cache[i] = (t,k,v)
                    heapq.heapify(self.cache)
                    return v
            
        return -1

    def put(self, key: int, value: int) -> None:
        
        if key not in [k for t,k,v in self.cache] and len(self.cache) == self.size:
            heapq.heappop(self.cache)
        
        found = False
        if key in [k for t,k,v in self.cache]:
            for i,c in enumerate(self.cache):
                t,k,v = c
                if k == key:
                    t = time.time()
                    self.cache[i] = (t,k,value)        
                    found = True
                    break
        if not found:   
            t = time.time()
            heapq.heappush(self.cache, (t, key, value))
        else:
            heapq.heapify(self.cache)
    

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

I first use for loop to find the cache by key but I soon realized that it does not match the follow-up question because every time when I put or get, I need actual index by key and I used for loop to find the index which requires O(N) So, revised #1 is O(N), not O(1)

So, I thought that O(1) is required some kind of max heap + hashmap structure. When putting the item, hashmap saves the index (in here, I just simply save size of the cache -1 since I always add item in the end), And when I need heapify again, I should update the index which requires O(N). So, the worst case of put() is logN + N but it will be working O(1) based on the amortized analysis.

import heapq
import time

class LRUCache:
    cache = []
    size = 0
    m = {}
    def __init__(self, capacity: int):
        self.cache = []
        self.m = {}
        self.size = capacity
        
    def get(self, key: int) -> int:
        if len(self.cache) == 0:
            return -1
    
        if key in self.m:
            t,k,v = self.cache[self.m[key]]
            t = time.time()
            self.cache[self.m[key]] = (t,k,v)  
            return v
            
        return -1

    def put(self, key: int, value: int) -> None:
        if key not in [k for t,k,v in self.cache] and len(self.cache) == self.size:
            heapq.heapify(self.cache)
            t,k,v = heapq.heappop(self.cache)
            self.m.pop(k)
            t = time.time()
            self.cache.append((t, key, value))
            for i,c in enumerate(self.cache):
                t,k,v = c
                self.m[k] = i
        elif key in self.m:
            t,k,v = self.cache[self.m[key]]
            t = time.time()
            self.cache[self.m[key]] = (t,k,value)    
            
        else:
            t = time.time()
            self.cache.append((t, key, value))
            self.m[key] = len(self.cache) - 1

Submission

Runtime: 2508 ms, faster than 5.06% of Python3 online submissions for LRU Cache.

Memory Usage: 23.5 MB, less than 62.47% of Python3 online submissions for LRU Cache.

Time/Space Complexity

O(1) (based on amortized analysis)