← Back to companies
[ OK ] Loaded —
[ INFO ]
$ cd
$ ls -lt
01
02
03
04
05
$ ls -lt
01
02
03
04
05
user@intervues:~/$
Design and implement a data structure for a cache that evicts entries based on access frequency. The cache should support two operations:
When a key is accessed (via get or put), its frequency counter increments. The cache must efficiently track both frequency and recency to determine which item to evict.
FrequencyCache class with a constructor that takes the cache capacityget method returns the value for the given key, or -1 if not foundput method inserts or updates a key-value pairExample 1:
cache = FrequencyCache(2) cache.put(1, 10) // cache: \{1:10\} cache.put(2, 20) // cache: \{1:10, 2:20\} cache.get(1) // returns 10, cache: \{1:10, 2:20\}, freq(1)=2, freq(2)=1 cache.put(3, 30) // evicts key 2 (lowest frequency), cache: \{1:10, 3:30\} cache.get(2) // returns -1 (not found) cache.get(3) // returns 30 cache.get(1) // returns 10
Example 2:
cache = FrequencyCache(2) cache.put(1, 100) // cache: \{1:100\}, freq(1)=1 cache.put(2, 200) // cache: \{1:100, 2:200\}, freq(1)=1, freq(2)=1 cache.put(3, 300) // both have freq=1, evict key 1 (LRU), cache: \{2:200, 3:300\} cache.get(1) // returns -1
Hint 1: Data Structures You'll need multiple data structures working together: a hash map for O(1) key lookup, a way to track frequencies, and a way to maintain recency order within each frequency level. Consider using nested structures where you group keys by their frequency count.
Hint 2: Frequency Buckets Maintain a mapping from frequency count to a collection of keys at that frequency. Within each frequency level, use an ordered structure (like a doubly-linked list or ordered dictionary) to track recency. Also keep track of the minimum frequency in the cache for quick eviction.
Hint 3: Updating Frequency When a key's frequency increases, you need to remove it from its current frequency bucket and add it to the next frequency bucket. After removing from a frequency bucket, if that bucket becomes empty and was the minimum frequency, update the minimum frequency tracker.
Full Solution `` Explanation:
The solution uses three key data structures:
- key_to_val_freq: A hash map storing each key's value and current frequency for O(1) lookup
- freq_to_keys: A map from frequency to OrderedDict, where each OrderedDict maintains keys at that frequency in insertion order (LRU order)
- min_freq: Tracks the minimum frequency in the cache for quick eviction
Time Complexity: O(1) average for both get and put operations
- Hash map lookups and OrderedDict operations (insertion, deletion, popitem) are all O(1) average
- We maintain min_freq to avoid scanning all frequencies during eviction
Space Complexity: O(capacity) to store the cache entries and frequency mappings
Key Operations:
- get: Look up the key, update its frequency, and return the value
- put: If the key exists, update its value and frequency. If it's new and cache is full, evict the least frequently and least recently used key (first item in min_freq bucket), then insert the new key with frequency 1
- _update_frequency: Moves a key from its current frequency bucket to the next, maintaining LRU order within buckets
The OrderedDict preserves insertion order, so when we do
popitem(last=False), we get the oldest (least recently used) key at that frequency level.
from collections import defaultdict, OrderedDict
class FrequencyCache:
def __init__(self, capacity: int):
self.capacity = capacity
self.min_freq = 0
# Map from key to (value, frequency)
self.key_to_val_freq = {}
# Map from frequency to OrderedDict of keys (maintains insertion order for LRU)
self.freq_to_keys = defaultdict(OrderedDict)
def _update_frequency(self, key: int):
"""Update the frequency of a key and move it to the appropriate frequency bucket"""
value, freq = self.key_to_val_freq[key]
# Remove key from current frequency bucket
del self.freq_to_keys[freq][key]
# If this was the only key at min_freq and we removed it, increment min_freq
if freq == self.min_freq and not self.freq_to_keys[freq]:
self.min_freq += 1
# Add key to next frequency bucket
new_freq = freq + 1
self.freq_to_keys[new_freq][key] = None # OrderedDict maintains order
self.key_to_val_freq[key] = (value, new_freq)
def get(self, key: int) -> int:
if key not in self.key_to_val_freq:
return -1
# Update frequency before returning value
self._update_frequency(key)
value, _ = self.key_to_val_freq[key]
return value
def put(self, key: int, value: int) -> None:
if self.capacity == 0:
return
# Case 1: Key already exists - update value and frequency
if key in self.key_to_val_freq:
_, freq = self.key_to_val_freq[key]
self.key_to_val_freq[key] = (value, freq)
self._update_frequency(key)
return
# Case 2: New key, check if we need to evict
if len(self.key_to_val_freq) >= self.capacity:
# Evict least frequently used (and least recently used among ties)
# popitem(last=False) removes the first (oldest) item from OrderedDict
evict_key, _ = self.freq_to_keys[self.min_freq].popitem(last=False)
del self.key_to_val_freq[evict_key]
# Insert new key with frequency 1
self.key_to_val_freq[key] = (value, 1)
self.freq_to_keys[1][key] = None
self.min_freq = 1