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 1cache.put(3, 3);    // evicts key 2cache.get(2);       // returns -1 (not found)cache.put(4, 4);    // evicts key 1cache.get(1);       // returns -1 (not found)cache.get(3);       // returns 3cache.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 usedblack to format code.

1 Answer1

Start asking to get answers

Find the answer to your question by asking.

Explore related questions

See similar questions with these tags.