LFU Cache
Advanced Implementation & Design DSA practice problem on Onlearn.
Difficulty: hard.
Topics: What is an LFU (Least Frequently Used) cache, and how can it be implemented efficiently?, Data Structures, Algorithm, Hash Map, Doubly Linked List, Time Complexity, Space Complexity, Optimization, Pointer, cache, complexity analysis, frequency counting, hash map, cache replacement policies, linked list, LFU Cache, Cache Design.
LFU Cache Design and implement a data structure for a Least Frequently Used (LFU) cache. It should support the following operations: LFUCache(capacity): Initializes the cache with the given positive capacity. int get(int key): Returns the value of the key if the key exists, otherwise returns 1. When a key is accessed, its frequency count should be incremented. If the key exists, it is considered recently used among items with the same frequency. void put(int key, int value): Updates the value of the key if the key exists. Otherwise, adds the key value pair to the cache. If the number of keys exceeds the capacity from this operation, evict the least frequently used item. If there are multiple items with the same minimum frequency, evict the least recently used among them. Example: