Katkat
Back

Implement an LFU Cache

CiscoSoftware Engineer · Technical Screen
HardSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to design a data structure that supports O(1) insertions and lookups while managing cache eviction based on access frequency and recency.

Problem: Least Frequently Used (LFU) Cache

Design and implement a data structure for an LFU cache. The cache should support the following operations with O(1) time complexity per operation:

  • LFUCache(int capacity): Initializes the object with the capacity of the data structure.
  • int get(int key): Gets the value of the key if the key exists in the cache, otherwise returns -1.
  • void put(int key, int value): Updates the value of the key if present, or inserts the key if not already present. When the cache reaches its capacity, it should invalidate and remove the least frequently used key before inserting a new item. If there is a tie in frequency, the least recently used key among those is removed.

Constraints:

  • 0 <= capacity <= 10^4
  • 0 <= key <= 10^5
  • 0 <= value <= 10^9
  • At most 2 * 10^5 calls will be made to get and put.

Example:

lfu = LFUCache(2)
lfu.put(1, 1)
lfu.put(2, 2)
lfu.get(1)      # returns 1, cache is {1:1, 2:2}, freq of 1 is 2
lfu.put(3, 3)   # evicts key 2, cache is {1:1, 3:3}
lfu.get(2)      # returns -1
lfu.get(3)      # returns 3, cache is {1:1, 3:3}, freq of 3 is 2

Hints

Hint 1

Use a hash map to map keys to their values and another map to keep track of the frequency of each key.

Hint 2

To achieve O(1) time, you need a data structure that allows constant time removal and addition of elements, such as a Doubly Linked List for each frequency tier.

Hint 3

Maintain a global variable to track the current minimum frequency in the cache to quickly identify which element to evict.

Follow-up questions

  • How would you modify your implementation if the capacity were extremely large and you needed to persist the cache to disk?
  • What are the trade-offs of using a Doubly Linked List compared to a Min-Heap for maintaining frequency ordering?
  • How would you ensure thread safety if multiple threads were accessing this cache simultaneously?