Python solution with detailed explanation


  • 0
    G

    Solution

    LRU Cache https://leetcode.com/problems/lru-cache/

    Data-Structures

    • Node class which has a key and value.
    • DoublyLinkedList class which is a container of type node. It supports O(1) operations for insert, appendleft, append, remove, pop, and popleft. We implement it using the concept of sentinel nodes which dramatically simplifies implementation. Exceptions are thrown for any invalid operation. If the list is empty, then get_head and get_tail return None.Now note that searching in a linked list using a key is O(N). This gives us our next data-structure
    • LinkedHashSet is a key-value store that supports maintaining an ordered list of key, value pairs in O(1) time. It supports appendleft(key, value), moveleft(key), append(key, value), moveright(key), contains(key), search(key), and pop()/popleft() in O(1). appendleft(key, value)/append(key,value) both support update and new insertion and move the new k,v pair to head or to tail in constant time.

    Algorithm

    • get(): uses contains(key)/search(key)/moveleft(key) APIs
    • put(key,value): supports update and put. If fresh insert and cache is full, then pop(). use appendleft(key,value) which updates or inserts.
    class Node(object):
        def __init__(self, key, value):
            self.key, self.value = key, value
            self.prev, self.nxt = None, None 
            return
    
    class DoubleLinkedList(object):
        def __init__(self):
            self.head_sentinel, self.tail_sentinel, self.count = Node(None, None), Node(None, None), 0
            self.head_sentinel.nxt, self.tail_sentinel.prev = self.tail_sentinel, self.head_sentinel
            self.count = 0
     
        def insert(self, x, node):
            if node == None:
                raise
            temp = x.nxt
            x.nxt, node.prev = node, x
            node.nxt, temp.prev = temp, node
            self.count += 1
    
        def appendleft(self, node):
            if node == None:
                raise
            self.insert(self.head_sentinel, node)
    
        def append(self, node):
            if node == None:
                raise
            self.insert(self.get_tail(), node)
    
        def remove(self, node):
            if node == None:
                raise
            prev_node = node.prev
            prev_node.nxt, node.nxt.prev = node.nxt, prev_node
            self.count -= 1
    
        def pop():
            if self.size() < 1:
                raise
            self.remove(self.get_tail())
    
        def popleft():
            if self.size() < 1:
                raise
            self.remove(self.get_head())
    
        def size(self):
            return self.count
    
        def get_head(self):
            return self.head_sentinel.nxt if self.count > 0 else None
        
        def get_tail(self):
            return self.tail_sentinel.prev if self.count > 0 else None        
    
    class LinkedHashSet():
        def __init__(self):
            self.node_map, self.dll = {}, DoubleLinkedList()
    
        def size(self):
            return len(self.node_map)
            
        def contains(self, key):
            return key in self.node_map
        
        def search(self, key):
            if self.contains(key) == False:
                raise
            return self.node_map[key].value
    
        def appendleft(self, key, value):
            if self.contains(key) == False:
                node = Node(key, value)
                self.dll.appendleft(node)
                self.node_map[key] = node
            else:
                self.node_map[key].value = value
                self.moveleft(key)
    
        def append(self, key, value):
            if self.contains(key) == False:
                node = Node(key, value)
                self.dll.append(node)
                self.node_map[key] = node
            else:
                self.node_map[key].value = value
                self.moveright(key)
        
        def moveleft(self, key):
            if self.contains(key) == False:
                raise
            node = self.node_map[key]
            self.dll.remove(node)
            self.dll.appendleft(node)
    
        def moveright(self, key):
            if self.contains(key) == False:
                raise
            node = self.node_map[key]
            self.dll.remove(node)
            self.dll.append(node)
    
        def remove(self, key):
            if self.contains(key) == False:
                raise
            node = self.node_map[key]
            self.dll.remove(node)
            self.node_map.pop(key)
        
        def popleft(self):
            key = self.dll.get_head().key
            self.remove(key)
    
        def pop(self):
            key = self.dll.get_tail().key
            self.remove(key)
    
    class LRUCache(object):
        def __init__(self, capacity):
            """
            :type capacity: int
            """
            self.cap = capacity
            self.cache = LinkedHashSet()
            return
    
        def get(self, key):
            """
            :rtype: int
            """
            result = -1
            if self.cache.contains(key):
                result = self.cache.search(key)
                self.cache.moveleft(key)
            return result
    
        def set(self, key, value):
            """
            :type key: int
            :type value: int
            :rtype: nothing
            """
            if self.cache.size() == self.cap and self.cache.contains(key) == False:
                self.cache.pop()
            self.cache.appendleft(key, value)
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.