Implement an LRU cache

Q: Implement an LRU cache

This question evaluates a candidate's ability to design and implement efficient cache eviction policies while managing time and space complexity guarantees for mutable key-value stores.

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

Design and implement an LRU (Least Recently Used) cache that supports the following operations in average O(1) time:

get(key) -> value : Return the value associated with key if it exists in the cache; otherwise return -1 . Accessing a key makes it most recently used .
put(key, value) : Insert or update the value for key . If inserting causes the number of keys to exceed the cache capacity , evict the least recently used key.

Input/Output

You will implement a class (or module) with:

Constructor: LRUCache(capacity)
Methods: get(key) and put(key, value)

Constraints (typical)

1 <= capacity <= 10^5
Keys and values are integers (or comparable scalar types)
Must achieve O(1) average time for both operations and O(capacity) space

Notes

“Most recently used” means most recently accessed via get or updated via put .
Updating an existing key counts as a recent use.

Implement an LRU cache

Overview

Problem

Input/Output

Constraints (typical)

Notes

Comments (0)