Implement an LRU cache

Q: Implement an LRU cache

This question evaluates understanding of cache design and eviction policies (LRU), along with competency in selecting and reasoning about data structures and complexity to support efficient get and put operations under capacity constraints.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

Problem: LRU Cache

Design and implement a data structure that supports an LRU (Least Recently Used) cache with a fixed capacity.

Requirements

Implement a cache with the following operations:

get(key) -> value
- If key exists in the cache, return its value and mark the entry as most recently used .
- If key does not exist, return -1 .
put(key, value) -> void
- Insert or update the (key, value) pair.
- If inserting causes the number of keys to exceed capacity , evict the least recently used entry.
- Updating an existing key should also mark it as most recently used .

Performance Constraints

Target time complexity: O(1) average for both get and put .
Space complexity: O(capacity) .

Example

Assume capacity = 2:

put(1, 10)
put(2, 20)
get(1) -> 10 (now key 1 is most recently used)
put(3, 30) (evicts key 2 as least recently used)
get(2) -> -1

Notes

You may choose any programming language, but clearly describe the data structures you use and how you ensure O(1) operations.