Design Data Structure (Part II: LFU Cache)

LFU Cache

LeetCode 460. LFU Cache (Hard):

  • Description in short:
  • Diagram:
  • Thought

Review how LRU Cache was solved, and adding frequency on top of the design

Anytime a new node adds to the doubly linked list, it adds to the middle of the linked list, according to its frequency. If anytime we have to add/remove in the middle of the linked list, it will be O(N) time complexity since we need to traverse the linked list.

  • Solution: Use 2 dictionaries and a list of the doubly linked list, according to the frequency.
  • Code:

List Node:

Doubly Linked List: (see diagram in LRU Cache session)

LFU Cache:

  • Other solution: using Python ordered dictionary

Note. this is not the solution the interviewer is looking for. See details in the LRU cache session.

Software Engineer