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.

QUESTION:

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.

CODE:

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)[0]]
                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

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.

QUESTION:

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.

CODE:

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)[0]]
                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

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.

QUESTION:

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.

CODE:

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)[0]]
                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

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.

QUESTION:

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.

CODE:

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)[0]]
                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