[Top Interview 150] 146. LRU Cache

Solution)

# Doubly Linked List
class ListNode:
    def __init__(self, key=0, val=0, nextt=None, prev=None):
        self.key = key
        self.val = val
        self.next = nextt
        self.prev = prev


class LRUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.storage = {}
        self.root = ListNode(0)
        self.tail = self.root


    def put(self, key: int, value: int) -> None:
        newNode = ListNode(key, value)
        self.append(newNode)

        if key in self.storage:
            self.remove(self.storage[key])

        self.storage[key] = newNode
        
        if len(self.storage)-1 == self.capacity:
            del self.storage[self.root.next.key]
            self.remove(self.root.next)


    def get(self, key: int) -> int:
        if key in self.storage:
            updNode = self.storage[key]

            if updNode != self.tail:
                self.remove(updNode)
                self.append(updNode)

            return updNode.val
        
        return -1

    
    # Helper func that removes a node from a list
    def remove(self, node):
        if self.tail == node:
            self.root.next = None
            self.tail = self.root
        else:
            prev = node.prev
            prev.next = node.next
            node.next.prev = prev

    
    # Helper func that appends a node to a list
    def append(self, node):
        self.tail.next = node
        node.prev = self.tail
        self.tail = node
        node.next = None

 

Problem: LeetCode

 

Time Complexity: O(1)

Space Complexity: O(n)

 

Structure of the Code)

Since this problem is more of an exercise problem to practice doubly linked list rather than a complex logic problem, I'll just explain the abstract structure of the code. I think this is a type of question that you have to do it by yourself once you reailze the steps you need to take.

 

To have LRU cache structure, we need a linked list. We need this to constantly update the sequence in O(1) time complexity. Changing the order of nodes in a linked list is not simple but very efficient.

 

We also need a dictionary to get a specific value and a specific node from LRU cache in O(1) time complexity.

 

We're given 2 methods put() and get(). These two methods both require us to include "functions" of removing a specific node from a list and adding a specific node to the tail of a list. So, instead of just copying the same lines over and over again, we'll make two helper functions remove() and append(). 

 

And using these two helper functions, we can fill up the rest of the codes in put() and get(). Just be careful of updating the nodes in the list and the capacity of a dictionary.

 

 

 

This might be the most unhelpful post in this blog, but trust me. It's a lot helpful for you to ACTUALLY code by yourself than me just explaining what/how I did it for this kind of questions.