26. Least Recently Used (LRU) / Least Frequent Used (LFU)
Question: Write a Least Recently Used (LRU) class where you can retrieve the value by key and also set a new value for a key; both methods should execute on constant time O(1).
Hints:
- You will need to keep the order of the access (read and write),
- You will need to have direct access to all values,
- To achieve this, you will need two data structures, one double-linked list for the order and one dictionary to get the values.
Solution:
class LRUCache<Key: Hashable, Value> {
// 1.
typealias Element = (key: Key, value: Value)
// 2.
let size: Int
let orderList = DoubleLinkedList<Element>()
var cache = [Key: DoubleLinkedListNode<Element>]()
init(size: Int) {
self.size = size
}
// 3.
func getValue(for key: Key) -> Value? {
// 4.
guard let node = cache[key] else {
return nil
}
// 5.
orderList.moveUp(node: node)
return node.value.value
}
// 6.
func setValue(_ value: Value, for key: Key) {
guard size > 0 else { return }
// 7.
let element = Element(key: key, value: value)
if let node = cache[key] {
// 8.
node.value = element
orderList.moveUp(node: node)
return
}
if cache.count == size {
// 9.
if let key = orderList.removeFirst()?.key {
cache.removeValue(forKey: key)
}
}
// 10.
let node = orderList.append(element)
cache[key] = node
}
}
extension DoubleLinkedList {
// 11.
func moveUp(node: DoubleLinkedListNode<T>) {
// 12.
guard node !== tail else {
return
}
// 13.
if head === node {
head = node.next
}
// 14.
node.next?.previous = node.previous
node.previous?.next = node.next
node.next = nil
// 15.
tail?.next = node
node.previous = tail
tail = node
}
}Explanations:
1. Let’s define a new type (tuple) to store the key and value.
typealias Element = (key: Key, value: Value)2. Because we need to access in O(1), we need to have a dictionary; as we need to keep the order, we require a sequence, as we want to be able to reorder also in O(1). we will use a double-linked list with our tuple as value and a dictionary with the key as key and the double-linked list node as value.
let size: Int
let orderList = DoubleLinkedList<Element>()
var cache = [Key: DoubleLinkedListNode<Element>]()3. Let’s create the get method.
func getValue(for key: Key) -> Value? {4. If our dictionary does not have this key let’s return nil.
guard let node = cache[key] else {
return nil
}5. Let’s “move up” (this function is explained later) the key associated node and return the stored value (the node’s value’s value)..
orderList.moveUp(node: node)
return node.value.value6. Let’s create the set method
func setValue(_ value: Value, for key: Key) {7. We create a new tuple with the key and the value.
let element = Element(key: key, value: value)8. If a node exists in our dictionary for the given key, let’s update its value and “move up” the node.
if let node = cache[key] {
node.value = element
orderList.moveUp(node: node)
return
}9. If we have reached the capacity limit, let’s remove the first element from the double-linked list and remove its key from the dictionary.
if cache.count == size {
if let key = orderList.removeFirst()?.key {
cache.removeValue(forKey: key)
}
}10. Append the new tuple into the linked list, and set the new node into the dictionary too.
let node = orderList.append(element)
cache[key] = node11. Let’s create the “move up” method (taking any node from the list and send it to the tail).
func moveUp(node: DoubleLinkedListNode<T>) {12. If the node is already the tail, nothing to do.
guard node !== tail else {
return
}13. If the given node is the current head, make the current node’s next node the new head.
if head === node {
head = node.next
}14. To remove the node from the list, connect its previous with its next node.
node.next?.previous = node.previous
node.previous?.next = node.next
node.next = nil15. Let’s connect the current tail with the given node and make it the new tail.
tail?.next = node
node.previous = tail
tail = nodeComplexity:
- Time Complexity: As per requirement, both get and set methods are constant in time complexity O(1),
- Space Complexity: To achieve this performance, there is some data duplication, but the space complexity remains linear O(n).
Test-cases:
public func testLRU() {
let lruCache = LRUCache<String,String>(size: 3);
lruCache.setValue("1",for: "test1");
lruCache.setValue("2",for: "test2");
lruCache.setValue("3",for: "test3");
_ = lruCache.getValue(for: "test1")
_ = lruCache.getValue(for: "test2")
_ = lruCache.getValue(for: "test3")
assert("1" == lruCache.getValue(for: "test1"), "mainLRU 1 not equal");
assert("2" == lruCache.getValue(for: "test2"), "mainLRU 2 not equal");
assert("3" == lruCache.getValue(for: "test3"), "mainLRU 3 not equal");
lruCache.setValue("1",for: "test1");
lruCache.setValue("2",for: "test2");
lruCache.setValue("3",for: "test3");
_ = lruCache.getValue(for: "test1")
lruCache.setValue("4",for: "test4");
_ = lruCache.getValue(for: "test1")
assert(lruCache.getValue(for: "test1") == "1", "mainLRU 4 not equal");
_ = lruCache.getValue(for: "test2")
assert(lruCache.getValue(for: "test2") == nil, "mainLRU 5 not equal");
}Follow-up:
Write a Least Frequent Used (LFU).
Hints:
- You still need to care about the order but also need to store the frequency,
- Think about keeping buckets for the same frequency,
- You need to know the least current frequency.
Solution:
class LFUCache<Key: Hashable, Value> {
// 1.
typealias Element = (key: Key, value: Value, frequency: Int)
// 2.
let size: Int
var frequencyMap = [Int: DoubleLinkedList<Element>]()
var cache = [Key: DoubleLinkedListNode<Element>]()
var currentFrequency: Int = 0
init(size: Int) {
self.size = size
}
// 3.
func getValue(for key: Key) -> Value? {
// 4.
guard let node = cache[key] else {
return nil
}
// 5.
update(key: key, node: node)
return node.value.value
}
// 6.
func setValue(_ value: Value, for key: Key) {
guard size > 0 else { return }
// 7.
if let node = cache[key] {
node.value.value = value
update(key: key, node: node)
return
}
if cache.count == size,
let node = frequencyMap[currentFrequency]?.removeFirst() {
// 8.
cache.removeValue(forKey: node.key)
if frequencyMap[currentFrequency]?.isEmpty ?? false {
// 9.
frequencyMap.removeValue(forKey: currentFrequency)
}
}
// 10.
currentFrequency = 1
let list = frequencyMap[currentFrequency] ?? DoubleLinkedList<Element>()
let node = list.append((key: key, value: value, frequency: currentFrequency))
frequencyMap[currentFrequency] = list
cache[key] = node
}
// 11.
func update(key: Key, node: DoubleLinkedListNode<Element>) {
// 12.
let frequency = node.value.frequency
_ = frequencyMap[frequency]?.remove(node)
if frequencyMap[frequency]?.isEmpty ?? false {
// 13.
frequencyMap.removeValue(forKey: frequency)
if currentFrequency == frequency {
currentFrequency = frequency + 1
}
}
// 14.
let list = frequencyMap[frequency + 1] ?? DoubleLinkedList<Element>()
let newNode = list.append((key: key, value: node.value.value, frequency: frequency + 1))
frequencyMap[frequency + 1] = list
cache[key] = newNode
}
}Explanations:
1. Let’s define a new type (tuple) to store the key, the value, and its frequency.
typealias Element = (key: Key, value: Value, frequency: Int)2. Because we need to access in O(1), we need to have a dictionary for the key and the frequency; as we need to keep the order, we need a sequence, as we want to reorder also in O(1). We will use a dictionary with the frequency as the key and a double-linked list with our tuple as the value. We will also use a dictionary with the key and the double-linked list node as the value.
let size: Int
var frequencyMap = [Int: DoubleLinkedList<Element>]()
var cache = [Key: DoubleLinkedListNode<Element>]()
var currentFrequency: Int = 03. Let’s create the get method.
func getValue(for key: Key) -> Value? {4. If our cache does not have this key let’s return nil.
guard let node = cache[key] else {
return nil
}5. Let’s “update” the key/node (this function is explained later), and return the stored value (the node’s value’s value).
update(key: key, node: node)
return node.value.value6. Let’s create the set method.
func setValue(_ value: Value, for key: Key) {7. If our cache has this key, let’s update the node’s value’s value, “update” the key/node and return.
if let node = cache[key] {
node.value.value = value
update(key: key, node: node)
return
}8. If we have reached the capacity limit, let’s remove the first element from the double-linked list at our current frequency and remove its key from the cache.
if cache.count == size,
let node = frequencyMap[currentFrequency]?.removeFirst() {
cache.removeValue(forKey: node.key)9. If the double-linked list at the current frequency is empty, let’s remove the current frequency from the frequency map.
if frequencyMap[currentFrequency]?.isEmpty ?? false {
frequencyMap.removeValue(forKey: currentFrequency)
}10. Let’s reset the current frequency at 1 (this is a new entry), get or create the double linked list for frequency 1, append to it the new tuple, and update the cache and the frequency map.
currentFrequency = 1
let list = frequencyMap[currentFrequency] ?? DoubleLinkedList<Element>()
let node = list.append((key: key, value: value, frequency: currentFrequency))
frequencyMap[currentFrequency] = list
cache[key] = node11. Let’s create the “update key/node”.
func update(key: Key, node: DoubleLinkedListNode<Element>) {12. Remove the given node from its list.
let frequency = node.value.frequency
_ = frequencyMap[frequency]?.remove(node)13. If its list becomes empty remove the list from the frequency map and increment the current frequency if the same frequency.
if frequencyMap[frequency]?.isEmpty ?? false {
frequencyMap.removeValue(forKey: frequency)
if currentFrequency == frequency {
currentFrequency = frequency + 1
}
}14. Let’s get or create the double linked list for frequency its frequency + 1, append to it the new tuple, and update the cache and the frequency map.
let list = frequencyMap[frequency + 1] ?? DoubleLinkedList<Element>()
let newNode = list.append((key: key, value: node.value.value, frequency: frequency + 1))
frequencyMap[frequency + 1] = list
cache[key] = newNodeComplexity:
- Time Complexity: As per requirement, both get and set methods are constant in time complexity O(1),
- Space Complexity: To achieve this performance, there is some data duplication, but the space complexity remains linear O(n).
Test-cases:
public func testLFU() {
let lfuCache = LFUCache<String,String>(size: 3);
lfuCache.setValue("1",for: "test1");
lfuCache.setValue("2",for: "test2");
lfuCache.setValue("3",for: "test3");
_ = lfuCache.getValue(for: "test1")
_ = lfuCache.getValue(for: "test2")
_ = lfuCache.getValue(for: "test3")
assert("1" == lfuCache.getValue(for: "test1"), "mainLFU 1 not equal");
assert("2" == lfuCache.getValue(for: "test2"), "mainLFU 2 not equal");
assert("3" == lfuCache.getValue(for: "test3"), "mainLFU 3 not equal");
lfuCache.setValue("1",for: "test1");
lfuCache.setValue("2",for: "test2");
lfuCache.setValue("3",for: "test3");
_ = lfuCache.getValue(for: "test1")
lfuCache.setValue("4",for: "test4");
_ = lfuCache.getValue(for: "test1")
assert(lfuCache.getValue(for: "test1") == "1", "mainLFU 4 not equal");
_ = lfuCache.getValue(for: "test2")
assert(lfuCache.getValue(for: "test2") == nil, "mainLFU 5 not equal");
}Follow-up:
No more follow-up question.
<< More Interview Questions | Data Structures and Algorythms >>
