LeetCode 460: LFU Cache

Use a doubly linked list to maintain elements that have the same reference frequency in order of use. Two hash maps have been used to keep track of elements present in the cache and linked lists with different reference frequencies.

LFU summary card

Table of Contents
· Problem
· Approach
· Graphical Explanation
· Code Implementation
  ∘ Complexity
  ∘ Golang
  ∘ Python

Problem

Design a Least Frequently Used(LFU) cache

• evict policy: discard least frequently used key when the cache is full. When there is a tie(keys at the same frequency), get rid of the least recently used(LRU) key.
• implement two functions, get and put
  1. get: input → (key int); output → return value or -1 if key is not existed
  2. put: input → (key int, value int); update the value and the cache if key is present
• The functions get and put must each run in O(1) average time complexity.

LFU Cache - LeetCode

Approach

We use doubly linked lists to maintain elements that have the same reference frequency in order of use . The least recently used(LRU) key at the head and the most recently used(MRU) key at the tail. This lets us access or remove elements at the head or tail in O(1) time.

For each element in the cache, we have a hash map to keep track of all keys and refer to nodes in the doubly linked lists. In order to access doubly linked lists at a specified frequency in constant time, a frequency hash map with frequency as keys and linked list as value has been used.

A minFreq variable is used to track currently minimum frequency for eviction.

Graphical Explanation

• get(key)

get logic

• put(key, value)

put logic

• process

1

2

3

4

5

Code Implementation

Complexity

Time: O(1) for get and put operations
Space: O(c)
c:the capacity of the cache

Golang

Python

You can access the source code here.

Related story:

• LeetCode 146: LRU Cache