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
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
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".
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
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.