2
\$\begingroup\$

I'm posting my code for a LeetCode problem. If you'd like to review, please do so.

Problem

  • 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.

  • The cache is initialized with a positive capacity.

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

Accepted Python

class LRUCache:
    def __init__(self, capacity: int) -> None:
        self.cache = {}
        self.capacity = capacity
        self.next = {}
        self.prev = {}
        self.head = 'HEAD'
        self.tail = 'TAIL'
        self.connect(self.head, self.tail)

    def connect(self, node_a: int, node_b: int) -> None:
        self.next[node_a], self.prev[node_b] = node_b, node_a

    def remove(self, key: int) -> None:
        self.connect(self.prev[key], self.next[key])
        del(self.prev[key], self.next[key], self.cache[key])

    def append(self, key: int, val: int) -> None:
        self.cache[key] = val
        self.connect(self.prev[self.tail], key)
        self.connect(key, self.tail)
        if len(self.cache) > self.capacity:
            self.remove(self.next[self.head])

    def get(self, key: int) -> int:
        if key not in self.cache:
            return -1
        val = self.cache[key]
        self.remove(key)
        self.append(key, val)
        return val

    def put(self, key: int, val: int) -> None:
        if key in self.cache:
            self.remove(key)
        self.append(key, val)

LeetCode's Solution (Not for review)

class DLinkedNode(): 
    def __init__(self):
        self.key = 0
        self.value = 0
        self.prev = None
        self.next = None
            
class LRUCache():
    def _add_node(self, node):
        """
        Always add the new node right after head.
        """
        node.prev = self.head
        node.next = self.head.next

        self.head.next.prev = node
        self.head.next = node

    def _remove_node(self, node):
        """
        Remove an existing node from the linked list.
        """
        prev = node.prev
        new = node.next

        prev.next = new
        new.prev = prev

    def _move_to_head(self, node):
        """
        Move certain node in between to the head.
        """
        self._remove_node(node)
        self._add_node(node)

    def _pop_tail(self):
        """
        Pop the current tail.
        """
        res = self.tail.prev
        self._remove_node(res)
        return res

    def __init__(self, capacity):
        """
        :type capacity: int
        """
        self.cache = {}
        self.size = 0
        self.capacity = capacity
        self.head, self.tail = DLinkedNode(), DLinkedNode()

        self.head.next = self.tail
        self.tail.prev = self.head
        

    def get(self, key):
        """
        :type key: int
        :rtype: int
        """
        node = self.cache.get(key, None)
        if not node:
            return -1

        # move the accessed node to the head;
        self._move_to_head(node)

        return node.value

    def put(self, key, value):
        """
        :type key: int
        :type value: int
        :rtype: void
        """
        node = self.cache.get(key)

        if not node: 
            newNode = DLinkedNode()
            newNode.key = key
            newNode.value = value

            self.cache[key] = newNode
            self._add_node(newNode)

            self.size += 1

            if self.size > self.capacity:
                # pop the tail
                tail = self._pop_tail()
                del self.cache[tail.key]
                self.size -= 1
        else:
            # update the value.
            node.value = value
            self._move_to_head(node)

Reference

On LeetCode, there is a class usually named Solution with one or more public functions which we are not allowed to rename.

\$\endgroup\$
1
\$\begingroup\$

Something smells funny here:

    self.head = 'HEAD'
    self.tail = 'TAIL'
    self.connect(self.head, self.tail)

def connect(self, node_a: int, node_b: int) -> None:

Those are strings, not integers. Briefly looking through your code, there's nothing requiring that your node keys be integers; they only need to be hashable. This is probably what you want to use for your type hints:

https://docs.python.org/3/library/typing.html#typing.Hashable

Beyond that, though, I question using those strings for HEAD and TAIL. It would be safer to make sentinel objects self.head = object(); self.tail = object() that will not match anything the user provides.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.