Katkat
Back

Implement an LFU cache

SalesforceSoftware Engineer · Onsite
HardSoftware EngineerOnsiteCoding & Algorithms

Last updated

This question evaluates understanding of data structures and cache eviction policies, specifically frequency tracking for LFU caches and LRU tie-breaking among equal-frequency items.

Problem: LFU Cache

Design and implement a Least Frequently Used (LFU) cache with a fixed capacity.

The cache supports the following operations:

  • get(key) -> value

  • Return the value of key if it exists in the cache.

  • Otherwise return -1.

  • If the key exists, its usage frequency increases by 1.

  • put(key, value) -> void

  • Insert or update the value of key.

  • If the cache reaches capacity, it must evict one key before inserting.

Eviction Policy

  1. Evict the key with the lowest frequency (LFU).
  2. If multiple keys have the same (lowest) frequency, evict the least recently used (LRU) among them.

Requirements / Constraints

  • Capacity is a non-negative integer.
  • Aim for O(1) average time per operation.
  • If capacity == 0, put does nothing and get always returns -1.

Example

If capacity = 2:

  • put(1, 1)
  • put(2, 2)
  • get(1) returns 1 (freq(1)=2)
  • put(3, 3) evicts key 2 (freq(2)=1 is lowest)
  • get(2) returns -1
  • get(3) returns 3