Least Recently Used Cache Daily Coding Practice

Question

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

Answer 1

At first look, it seems like it should be O(1), except for the list(self.vals())[0]. Try iterating over the keys instead:

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[next(iter(self.vals))]    #### changed
            self.vals[key] = value

Answer 2

Your code reads very much like you have written some Java and are trying to translate it to Python. You need to "drink the Kool-Aid" and start embracing idiomatic Python, instead.

First, start by noting that storing None as a value is a legitimate thing to do in Python. So the idea of returning None to mean "no key found" is weak. A better approach would be to raise an exception -- probably a KeyError.

However, since it's part of your problem statement, we can ignore that issue (except to note that your problem statement likely came from Java or C++ or someplace like that).

In your set() method:

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

You can overwrite items in a dictionary directly. Just assign to them:

if key in self.vals:
    self.vals[key] = value

And your missing-key code is redundant. You assign value in both branches of the if/else statement. Just refactor the assignment down:

if len(self.vals) >= self.max_size:
    del self.vals[list(self.vals)[0]]

self.vals[key] = value

Once you do that, you realize that the assignment is also present in the upper (key-found) condition, and you can refactor it again:

def set(self, key, value):
    vals = self.vals
    if key in vals and len(vals) >= self.max_size:
        del vals[list(vals)[0]]
    vals[key] = value

In your get() method:

You are doing things pretty much spot-on, here, but you are depending on dictionaries to preserve insertion order. That is a somewhat new feature in python (added as an implementation detail in 3.6, and guaranteed in 3.7) that won't work in 3.5. You should at least comment this, and probably should add code at the top of your module to verify the version of python.

On the other hand: there is a collections.OrderedDict in the standard library that has been around for a while, and which even includes an example of building an LRU cache in the documentation. Just sayin'. ;-)