Skip to content

Instantly share code, notes, and snippets.

@KoStard
Created July 19, 2019 13:26
Show Gist options
  • Save KoStard/52bad7bf87342678b73a33eb4509878b to your computer and use it in GitHub Desktop.
Save KoStard/52bad7bf87342678b73a33eb4509878b to your computer and use it in GitHub Desktop.
Implementing LFU Cache with linked lists of linked lists.
class EnhancedLinkedListNode:
def __init__(self, a, b, c):
self.a = a
self.b = b
self.c = c
self.next = None
self.prev = None
def remove(self):
if self.prev:
self.prev.next = self.next
if self.next:
self.next.prev = self.prev
self.next = self.prev = None
def __str__(self):
return '{}/({})'.format(
self.a, self.b) if not self.next else '{}/({}) -> {}'.format(
self.a, self.b, self.next)
class LFUCache:
def __init__(self, capacity: int):
"""
We can use linked list of linked lists
backbone - linked list holding linked lists
map = holding key-node pair for every node of the backbone's linked lists
Backbone Node
a - freq
b - list head
c - list tail
Node
a - key
b - value
c - reference to the backbone node
"""
self.backbone = None
self.map = {}
self.capacity = capacity
def increment_freq(self, key):
node = self.map[key]
bnode_curr = node.c
if bnode_curr.b == node:
bnode_curr.b = node.next
if bnode_curr.c == node:
bnode_curr.c = node.prev
node.remove()
freq = bnode_curr.a
if not bnode_curr.next or bnode_curr.next.a > freq + 1:
bnode = EnhancedLinkedListNode(freq + 1, node, node)
node.c = bnode
bnode.prev = bnode_curr
bnode.next = bnode_curr.next
bnode_curr.next = bnode
if bnode.next:
bnode.next.prev = bnode
else:
bnode = bnode_curr.next
head = bnode.b
bnode.b = node
node.c = bnode
node.next = head
head.prev = node
if not bnode_curr.b:
if self.backbone == bnode_curr:
self.backbone = bnode_curr.next
bnode_curr.remove()
def remove_least_frequent(self):
if self.backbone.c == self.backbone.b:
b = self.backbone
self.backbone = b.next
b.remove()
b.b.remove()
del self.map[b.b.a]
else:
tail = self.backbone.c
self.backbone.c = tail.prev
tail.remove()
del self.map[tail.a]
def get(self, key: int) -> int:
if key in self.map:
self.increment_freq(key)
return self.map[key].b
return -1
def put(self, key: int, value: int) -> None:
if not self.capacity:
return
if key in self.map:
self.map[key].b = value
self.increment_freq(key)
else:
if len(self.map) == self.capacity:
self.remove_least_frequent()
node = EnhancedLinkedListNode(key, value, None)
self.map[key] = node
if not self.backbone or self.backbone.a != 1:
bnode = EnhancedLinkedListNode(1, node, node)
node.c = bnode
bnode.next = self.backbone
if bnode.next:
bnode.next.prev = bnode
self.backbone = bnode
else:
node.c = self.backbone
node.next = self.backbone.b
node.next.prev = node
self.backbone.b = node
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment