Design Data Structure (Part I: LRU Cache)

LRU Cache

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

  • Description in short:
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:
  • Solution:

Use 1 dictionary and 1 Doubly Linked List:

dboubly 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

Add node to head:

step 1: define variables:
next_n = node.next
step 2: modify pointers:
head.next = node
node.pre = head
node.next = next_n
next_n.pre = node

Remove from tail:

step 1: define variables:
node = tail.pre
pre_n = node.pre
step 2: modify pointers:
pre_n.next = tail
tail.pre = pre_n

Remove node:

step 1: define variables
pre_n = node.pre
next_n = node.next
step 2: modify pointers:
pre_n.next = next_n
next_n.pre = pre_n
  • Code:

ListNode class:

LRUCache class:

    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
def 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

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store