LRU Cache

Design a data structure that acts as a size-limited cache, efficiently storing and retrieving data while prioritizing the most recently accessed entries. This problem tests your understanding of data structures and algorithms, crucial for building performant and scalable systems.

cachelinked listhash mapdata structuredesign

Problem Statement

Implement a FrequencyCache class that mimics a cache with a fixed maximum capacity. The cache should support two primary operations: retrieve(key) which returns the value associated with the given key, or -1 if the key is not present; and store(key, value) which adds a new key-value pair to the cache. If the cache is full when store is called, the least frequently used item should be evicted to make room for the new entry. When an item is accessed using retrieve, its frequency should be increased. If multiple items have the same frequency, the least recently inserted of these should be evicted.

Example 1

Input: [store(1, 5), store(2, 10), retrieve(1), store(3, 15), retrieve(2), retrieve(1), store(4, 20), retrieve(3), retrieve(2), retrieve(1), retrieve(4)] with capacity = 3

Output: [5, -1, 5, 15, -1, 5, 20]

Initial state: Cache is empty. store(1, 5): Cache is [1:5]. store(2, 10): Cache is [1:5, 2:10]. retrieve(1): Returns 5, Cache is [2:10, 1:5]. store(3, 15): Cache is [2:10, 1:5, 3:15]. retrieve(2): Returns -1, Cache is [1:5, 3:15]. store(4, 20): Cache is [1:5, 3:15, 4:20]. retrieve(3): Returns 15, Cache is [1:5, 4:20, 3:15]. retrieve(2): Returns -1, Cache is [1:5, 4:20, 3:15]. retrieve(1): Returns 5, Cache is [4:20, 3:15, 1:5]. retrieve(4): Returns 20.

Example 2

Input: [store(5, 25), store(10, 50), store(5, 30), retrieve(10), store(15, 75), retrieve(5), retrieve(10), retrieve(15)] with capacity = 2

Output: [50, 30, 50, 75]

Initial state: Cache is empty. store(5, 25): Cache is [5:25]. store(10, 50): Cache is [5:25, 10:50]. store(5, 30): Cache is [5:30, 10:50]. retrieve(10): Returns 50, Cache is [5:30, 10:50]. store(15, 75): Cache is [10:50, 15:75] (5:30 is evicted). retrieve(5): Returns -1, Cache is [10:50, 15:75]. retrieve(10): Returns 50, Cache is [15:75, 10:50]. retrieve(15): Returns 75.

Constraints

-All keys and values are non-negative integers.
-The cache capacity is a positive integer.
-The number of store and retrieve operations will be significant.
-Keys are unique.
-The values of the keys are not necessarily unique.

Brute Force Approach

Imagine the cache as a simple array. When you need to retrieve a value, you'd have to search the entire array. When you need to store a value and the array is full, you'd iterate through the array to find the least frequently used item and replace it. This involves linear scans for both retrieval and insertion, making it inefficient for larger caches.

TimeO(n)

SpaceO(n)

Ready to practice?

Work through this problem with AI coaching and get real-time feedback

Practice This Problem