Python Solution using Heap to track LRU item


  • 1
    C
    import heapq
    from time import time
    
    class LRUCache(object):
    
        def __init__(self, capacity):
            """
            :type capacity: int
            """
            self.capacity = capacity
            self.data = dict()
            self.access = []
            
    
        def get(self, key):
            """
            :rtype: int
            """
            if key not in self.data:
                return -1
            (val, _) = self.data[key]
            d_at = time()
            self.data[key] = (val, d_at)
    
            return val
    
        def set(self, key, value):
            """
            :type key: int
            :type value: int
            :rtype: nothing
            """
            d_at = time()
            if key in self.data:
                self.data[key] = (value, d_at)
                return
    
            if self.capacity == 0:
                self.remove_lru()
    
            self.data[key] = (value, d_at)
            heapq.heappush(self.access, (d_at, key)) # Assuming "set"ting is also counted as "use"
            self.capacity -= 1
    
        def remove_lru(self):
            while True:
                (lru_at, key) = self.access[0]
                (_, d_at) = self.data[key]
                if d_at > lru_at:
                    heapq.heappop(self.access)
                    heapq.heappush(self.access, (d_at, key))
                else:
                    heapq.heappop(self.access)
                    del self.data[key]
                    self.capacity += 1
                    return

  • 0
    P

    very smart solution! I had a similar idea, but was stuck on how to update the time value in heap in function get. You bypassed it!


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.