Very short solution using Python's OrderedDict


  • 13
    G

    Here is a simple fast solution using Python's OrderedDict. Original credits to http://www.kunxi.org/blog/2014/05/lru-cache-in-python/ . It could be even shorter if python 3.2 was supported with move_to_end.

    class LRUCache:
    
        # @param capacity, an integer
        def __init__(self, capacity):
            self.capacity = capacity
            self.cache = collections.OrderedDict()
    
        # @return an integer
        def get(self, key):
            if not key in self.cache:
                return -1
            value = self.cache.pop(key)
            self.cache[key] = value
            return value
    
        # @param key, an integer
        # @param value, an integer
        # @return nothing
        def set(self, key, value):
            if key in self.cache:
                self.cache.pop(key)
            elif len(self.cache) == self.capacity:
                self.cache.popitem(last=False)
            self.cache[key] = value

  • 9
    T

    Hi. I am just wondering if one implement a solution like this during interview would it be accepted? Cause the problem is basically asking you to implement an ordereddict-like structure.

    (EDIT) I myself was actually asked this problem during an interview. I asked the inteviewer "can I use OrderedDict?" and he said "Sure".


  • 0

    May I ask which company?


  • 0

    Even shorter:

    class LRUCache(object):
        def __init__(self, size):
            self.size = size
            self.cache = OrderedDict()
    
        def get(self, key):
            value = self.cache.pop(key, None)
            if value is None:
                return -1
            self.cache[key] = value
            return value
        
        def set(self, key, value):     
            if not self.cache.pop(key, None) and self.size == len(self.cache):
                self.cache.popitem(last=False)
            self.cache[key] = value

  • 0
    C

    Shorter yet by making the pop() default -1:

    def get(self, key):
        value = self.cache.pop(key, -1)
        if value != -1:
            self.cache[key] = value
        return value
    

Log in to reply
 

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