Python concise solution with comments (Using OrderedDict).


  • 24
    C
    def __init__(self, capacity):
        self.dic = collections.OrderedDict()
        self.remain = capacity
    
    def get(self, key):
        if key not in self.dic:
            return -1
        v = self.dic.pop(key) 
        self.dic[key] = v   # set key as the newest one
        return v
    
    def set(self, key, value):
        if key in self.dic:    
            self.dic.pop(key)
        else:
            if self.remain > 0:
                self.remain -= 1  
            else:  # self.dic is full
                self.dic.popitem(last=False) 
        self.dic[key] = value

  • 12
    C

    Another solution by using dictionary and deque in Python:

    def __init__(self, capacity):
        self.deque = collections.deque([])
        self.dic = {}
        self.capacity = capacity
    
    def get(self, key):
        if key not in self.dic:
            return -1
        self.deque.remove(key)
        self.deque.append(key)
        return self.dic[key]
    
    def set(self, key, value):
        if key in self.dic:    
            self.deque.remove(key)
        elif len(self.dic) == self.capacity:
            v = self.deque.popleft()  # remove the Least Recently Used element
            self.dic.pop(v)
        self.deque.append(key)
        self.dic[key] = value 

  • 0
    Z

    Very clear solution. A little suggestion for else statement under the set function: if len(self.dic) >= self.remain: self.dic.popitem(last=False). Two lines instead of four lines. Thanks for sharing!


  • 6

    I think if this question is solved by using OrderedDict or other built-in advanced data structures, it makes no sense. That is not what interviewers expect.


  • 0
    C

    Maybe, but the idea to solve the problem should be the same.


  • 0
    S
    This post is deleted!

  • 1
    M

    @caikehe Hey I don't think this is the better than OrderedDict you posted, since removing from Queue will be O(n) while removing from OrderedDict will be O(1) complexity. What do you think?


  • 0
    H

    @caikehe Can anyone clarify the implementation/performance of deque?
    As far from what I know the implementation of deque in python is indeed doubly-linked list. But the accessing time to the middle is roughly O(n).


  • 0
    A

    Just using a list instead of deque or orderedDict will also do the work:

    class LRUCache(object):
    
        def __init__(self, capacity):
            """
            :type capacity: int
            """
            self.cap = capacity
            self.order = []
            self.cache = {}
    
        def get(self, key):
            """
            :rtype: int
            """
            if key in self.cache:
                self.order.remove(key)
                self.order.append(key)
                return self.cache[key]
            else:
                return -1
            
    
        def set(self, key, value):
            """
            :type key: int
            :type value: int
            :rtype: nothing
            """
            
            if key in self.cache:
                self.order.remove(key)
            elif len(self.order) == self.cap:
                    self.cache.pop(self.order[0])
                    self.order.pop(0)
                    
            self.order.append(key)
            self.cache[key] = value
        
    

  • 6

    As per python document, the removal operation of deque is indeed O(n).


  • 1

    @abyellow7511 said in Python concise solution with comments (Using OrderedDict).:

    Just using a list instead of deque or orderedDict will also do the work:

    Depends on how you define "do the work". If we use OrderedDict, both operations would be O(1) on average. And when we use deque instead, at least for set operation, when capacity is full and the key we want to push is not in cache, we get O(1) on average. And in your case, both operations take O(n).


  • 1
    T

    @caikehe deque.remove() use O(n) time complexity


Log in to reply
 

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