LRU Cache

LeetCode 146. LRU Cache (Medium): https://leetcode.com/problems/lru-cache/

• Description in short:
`Design a data structure that follows the constraints of a Least Recently Used (LRU) cache.Implement the LRUCache class:- LRUCache(int capacity) Initialize the LRU cache with positive size capacity.- int get(int key) Return the value of the key if the key exists, otherwise return -1.- void put(int key, int value) Update the value of the key if the key exists. Otherwise, add the key-value pair to the cache. If the number of keys exceeds the capacity from this operation, evict the least recently used key.Follow up: Could you do get and put in O(1) time complexity?Eg.1:Input["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"][[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]Output[null, null, null, 1, null, -1, null, -1, 3, 4]`

a. Solution I, using one dictionary and one doubly LinkedList

• Diagram:
`cache capacity = 2, assume the left side is the most recently used sideput(1, 1):        |k=1,v=1|___|put(2, 2):       |k=2,v=2|k=1,v=1|get(1):       |k=1,v=1|k=2,v=2|       return 1put(3, 3):       |k=3,v=3|k=1,v=1|          evicts k=2,v=2get(2):       |k=3,v=3|k=1,v=1|               returns -1 (not found)put(4, 4):       |k=4,v=4|k=3,v=3|          evicts k=1,v=1get(1):       |k=4,v=4|k=3,v=3|       return -1 (not found)get(3):        |k=3,v=3|k=4,v=4|       return 3get(4):        |k=4,v=4|k=3,v=3|       return `
• Solution:

Use 1 dictionary and 1 Doubly Linked List:

`lru_cache = {cache_key:cache_value}cache_key=keycache_value=doubly linked list nodedboubly linked list: node (key,value,pre,next)         cache_key=1        cache_key=2        cache_key=3         cache_value=node1  cache_value=node2  cache_value=node3                 |               |               | head <-------> node1 <-------> node2 <-------> node3 <-------> tail               key=1           key=2           key=3                         value=1         value=2         value=3                     pre=head        pre=node1       pre=node2               next=node2      next=node3      next=tail                 |                                |         most recently used               least recently used         add new node here                remove node here`

`head <-------> nodex <-------> nodey <-------> nodez <-------> tail        node  next_n step 1: define variables:    next_n = node.nextstep 2: modify pointers:      head.next = node     node.pre = head     node.next = next_n     next_n.pre = node`

Remove from tail:

`head <-------> nodex <-------> nodey <-------> nodez <-------> tail                               pre_n           nodestep 1: define variables:     node = tail.pre     pre_n = node.prestep 2: modify pointers:     pre_n.next = tail     tail.pre = pre_n`

Remove node:

`head <-------> nodex <-------> nodey <-------> nodez <-------> tail               pre_n           node            next_nstep 1: define variables     pre_n = node.pre     next_n = node.nextstep 2: modify pointers:     pre_n.next =  next_n     next_n.pre = pre_n`
• Code:

ListNode class:

`class ListNode():        def __init__(self, key, value, pre=None, next=None):        self.key = key        self.value = value        self.pre = pre        self.next = next`

LRUCache class:

`class LRUCache:    def __init__(self, capacity: int):                self.capacity = capacity        self.cache_dict = {}                self.head = ListNode(None, None)        self.tail = ListNode(None, None)        self.head.next = self.tail        self.tail.prev = self.head              def add_node_to_head(self, node):                next_n = self.head.next                self.head.next = node        node.pre = self.head        node.next = next_n        next_n.pre = node                    def remove_node(self, node):                pre_n = node.pre        next_n = node.next                pre_n.next =  next_n        next_n.pre = pre_n            def remove_from_tail(self):                node = self.tail.pre        pre_n = node.pre                pre_n.next = self.tail        self.tail.pre = pre_n                    def move_to_head(self, node):                self.remove_node(node)        self.add_node_to_head(node)            def get_size(self):        return len(self.cache_dict)                    def get(self, key: int) -> int:        # if exist, move the node to the head                if key not in self.cache_dict:            return -1                node = self.cache_dict[key]        self.move_to_head(node)        return node.value                 def put(self, key: int, value: int) -> None:        # add the node to the head                if key in self.cache_dict:            node = self.cache_dict[key]            node.value = value            self.move_to_head(node)        else:            node = ListNode(key, value)            self.cache_dict[key] = node            self.add_node_to_head(node)                    if self.get_size() > self.capacity:            self.remove_from_tail()            del self.cache_dict[lru_cache.tail.pre.key]`

b. Solution II, using Python OrderedDict

Note. this is not the solution the interviewer is looking for. Also, Python’s OrderedDict is implemented using a dictionary and a doubly linked list. See source code: https://svn.python.org/projects/python/trunk/Lib/collections.py

• Code
`class LRUCache(OrderedDict):    def __init__(self, capacity: int):                self.capacity = capacitydef get(self, key: int) -> int:                if key not in self:            return -1               self.move_to_end(key)        return self[key]def put(self, key: int, value: int) -> None:                if key in self:            self.move_to_end(key)        self[key] = value        if len(self) > self.capacity:            self.popitem(last = False)`

Software Engineer

More from Jing Dong

Software Engineer

Type Assertion and Type Conversion in Golang

Get the Medium app