My python solution using dict + deque + lazy deletion -- O(1) and beats 95%


  • 2
    K

    one dict is used to record the <key, value>

    deque (linked list) is used to record the order of keys.

    another dict is used to record the times the key has been updated (lazy deletion)

    For detailed explanation, please check my blog

    from collections import deque
    class LRUCache(object):
    
        def __init__(self, capacity):
            """
            :type capacity: int
            """
            self.d = {}
            self.n = capacity
            self.stack = deque([])
            self.hasUpdated = {}
    
        def get(self, key):
            """
            :rtype: int
            """
            k = self.d.get(key, '-1')
            if k != -1:
                self.hasUpdated[key] = self.hasUpdated.get(key,0) + 1
                self.stack.append(key)
            return int(k)
    
        def set(self, key, value):
            """
            :type key: int
            :type value: int
            :rtype: nothing
            """
            if self.d.get(key, -1) != -1:
                self.d[key] = value
                self.hasUpdated[key] = self.hasUpdated.get(key,0) + 1
                self.stack.append(key)
            else:
                if self.n > 0:
                    self.n -= 1
                else:
                    oldKey = self.stack.popleft()
                    while self.hasUpdated.get(oldKey,0) > 0:
                        self.hasUpdated[oldKey] -= 1
                        oldKey = self.stack.popleft()
                    self.d.pop(oldKey)
                self.d[key] = value
                self.stack.append(key)
    

  • 0
    C

    Excellent strategy!

    I implemented with you idea, now 160ms 99.65%.

    from collections import deque
    

    class LRUCache(object):

    def __init__(self, capacity):
    
        self.capacity=capacity
        self.data=dict()
        self.ocurrenceInHistory=dict()
        self.history=deque()
    
    
    def get(self, key):
    
        if key not in self.data:
            return -1
        self.ocurrenceInHistory[key]+=1
        self.history.append(key)
        return self.data[key]
        
    
    def set(self, key, value):
    
        if key not in self.data and len(self.data) == self.capacity:
            keyToDel=self.history.popleft()
            while self.ocurrenceInHistory[keyToDel]>1:
                self.ocurrenceInHistory[keyToDel]-=1
                keyToDel=self.history.popleft()
    
            self.ocurrenceInHistory.pop(keyToDel,0)
            self.data.pop(keyToDel,0)
        
        self.data[key]=value
        self.ocurrenceInHistory[key]=1 if key not in self.ocurrenceInHistory else self.ocurrenceInHistory[key]+1
        self.history.append(key)
    

  • 1
    S

    I don't think this is a good way to do in the interview, although its performance is good for the test data in OJ.

    If we call a lot of get(), and very few set(), then the size of your queue will grow unboundedly because of this line in the get() method: ".append(key)".


  • 0
    J

    Oops! Your blog is inaccessible now.


Log in to reply
 

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