LRUCache for integers using dict + linkedlist

Question

From leet code question: https://leetcode.com/problems/lru-cache/

Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and put.

get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1. put(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.

Follow up: Could you do both operations in O(1) time complexity?

Example:

LRUCache cache = new LRUCache( 2 /* capacity */ );
cache.put(1, 1);
cache.put(2, 2);
cache.get(1); // returns 1
cache.put(3, 3); // evicts key 2
cache.get(2); // returns -1 (not found)
cache.put(4, 4); // evicts key 1
cache.get(1); // returns -1 (not found)
cache.get(3); // returns 3
cache.get(4); // returns 4

Code: Filename: lru_cache.py

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
class Node:
 def __init__(self, key: int, val: int, prv=None, nxt=None):
 self.prv = prv
 self.nxt = nxt
 self.val = val
 self.key = key
 def __str__(self):
 nx = str(self.nxt)
 return "{}:{} -> {}".format(self.key, self.val, nx)
class LRUCache:
 def __init__(self, capacity: int):
 """
 :type capacity: int
 """
 self.first = None
 self.last = None
 self.cap = capacity
 self.cache = {}
 self.size = 0
 def get(self, key):
 """
 :type key: int
 :rtype: int
 """
 if key not in self.cache:
 return -1
 node = self.cache[key]
 if self.first is self.last:
 return node.val
 if node is self.last:
 return node.val
 if node is self.first:
 nxt = node.nxt
 nxt.prv = None
 self.first = nxt
 node.nxt = None
 else:
 # In the middle
 nxt = node.nxt
 prv = node.prv
 node.nxt = None
 prv.nxt = nxt
 nxt.prv = prv
 self.last.nxt = node
 node.prv = self.last
 self.last = node
 return node.val
 def put(self, key, value):
 """
 :type key: int
 :type value: int
 :rtype: void
 """
 if self.get(key) != -1:
 # Already have
 self.cache[key].val = value
 return
 node = Node(key, value)
 if not self.first:
 self.size = 1
 self.first = node
 self.last = node
 self.cache[key] = node
 return
 self.cache[key] = node
 self.last.nxt = node
 node.prv = self.last
 self.last = node
 self.size = len(self.cache)
 if self.size > self.cap:
 # Need to remove
 first = self.first
 nxt = first.nxt
 nxt.prv = None
 self.first = nxt
 del self.cache[first.key]
 self.size = self.cap
 def __str__(self):
 return "LRUCache:: {}".format(self.first)
def _test():
 cache = LRUCache(2)
 cache.put(1, 1)
 cache.put(2, 2)
 assert cache.get(1) == 1 # returns 1
 cache.put(3, 3) # evicts key 2
 assert str(cache) == "LRUCache:: 1:1 -> 3:3 -> None"
 assert cache.get(2) == -1 # returns -1 (not found)
 cache.put(4, 4) # evicts key 1
 assert str(cache) == "LRUCache:: 3:3 -> 4:4 -> None"
 assert cache.get(1) == -1 # returns -1 (not found)
 assert cache.get(3) == 3 # returns 3
 assert cache.get(4) == 4 # returns 4
 assert str(cache) == "LRUCache:: 3:3 -> 4:4 -> None"
if __name__ == "__main__":
 _test()

What I want reviewed:

1. How pythonic the code is? How can I improve it.
2. Is there any area I can optimise performance ? (This passes all tests on leet-code)
3. Readability improvements?
4. Structure of the code file? Can we place things better?

You are welcome to be strict and brutal.

Additional info:

• I've used black to format code.

Answer 1

Use more abstract data types

In the current implementation two behaviors are mixed together:

• Caching
• Linked list manipulation

It would be better if the linked list manipulation was encapsulated in a dedicated abstract data type. Then LRUCache could use an instance of it, and perform operations that have nice descriptive names like append_node, delete_node, instead of blocks of nameless code. It will reveal more clearly the implemented logic of both the caching and linked list behaviors, and be more intuitively readable.

Avoid unclear side effects

At first glance I found this piece surprising in put:

if self.get(key) != -1:
 # Already have
 self.cache[key].val = value
 return

Why self.get(key) != -1 instead of key not in self.cache? The self.get is of course necessary, for its side effect of moving the node to the end. This may be subjective, but I would prefer to have an explicit private method that moves the node, and call it from both get and put. That will make the intention perfectly clear. Another reason I prefer that is to eliminate using the magic value -1 more than necessary.