146.LRU Cache

Tags: [cache], [data_structure], [linked_list], [double_linked_list], [map]

Com: {fb}

Link: https://leetcode.com/problems/lru-cache/#/description

Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: getand 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

Solution: Map, Double Linked List

class LRUCache(object):

    class ListNode(object):
        def __init__(self, key, val):
            self.key = key
            self.val = val
            self.prev = None
            self.next = None


    def __init__(self, capacity):
        """
        :type capacity: int
        """
        if capacity <= 0:
            raise ValueError('the input capacity is invaid')

        self.capacity = capacity
        self.key_node_map = {}

        self.head = self.ListNode(-1, -1)
        self.tail = self.ListNode(-1, -1)
        self.head.next = self.tail
        self.tail.prev = self.head


    def get(self, key):
        """
        :type key: int
        :rtype: int
        """
        if key not in self.key_node_map:
            return -1

        node = self.key_node_map[key]
        self.remove_node_from_list(node)
        self.link_node_to_head(node)

        return node.val

    def remove_node_from_list(self, node):
        if not node:
            return

        node.prev.next = node.next
        node.next.prev = node.prev


    def link_node_to_head(self, node):
        if not node:
            return

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


    def put(self, key, value):
        """
        :type key: int
        :type value: int
        :rtype: void
        """
        if key in self.key_node_map:
            node = self.key_node_map[key]
            node.val = value
            self.remove_node_from_list(node)
            self.link_node_to_head(node)
        else:
            new_node = self.ListNode(key, value)
            if len(self.key_node_map) == self.capacity:
                removed_node = self.tail.prev
                self.remove_node_from_list(removed_node)
                del self.key_node_map[removed_node.key]

            self.link_node_to_head(new_node)
            self.key_node_map[key] = new_node


# Your LRUCache object will be instantiated and called as such:
# obj = LRUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)

Revelation:

• ListNode need store key and value.

Note:

• Time complexity of each operation = O(1).