I have the following challenge problem for which I was able to get a solution working, but not in \$O(1)\$ time as the problem asks for. Could someone point me in the right direction to optimize this? I am also open to other criticisms of my coding style.
Implement an LRU (Least Recently Used) cache. It should be able to be initialized with a cache size n, and contain the following methods:
set(key, value): sets key to value. If there are already n items in the cache and we are adding a new item, then it should also remove the least recently used item.
get(key): gets the value at key. If no such key exists, return null.
Each operation should run in \$O(1)\$ time.
class LRUcache(): def __init__(self,n): self.vals = dict() self.max_size = n def set(self,key,value): if key in self.vals: del self.vals[key] self.vals[key] = value else: if(len(self.vals) < self.max_size): self.vals[key] = value else: del self.vals[list(self.vals)] self.vals[key] = value def get(self,key): if key in self.vals: tempval = self.vals[key] del self.vals[key] self.vals[key] = tempval return self.vals[key] return None