Implement an LRU cache

Q: Implement an LRU cache

This question evaluates understanding of data structures and algorithmic optimization for constant-time cache operations, with emphasis on cache eviction policies and state management.

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

Loading...

LRU Cache

Design and implement a fixed-capacity Least Recently Used (LRU) cache.

Operations

get(key) -> value | -1/null : Return the value if present; otherwise indicate missing. Accessing a key makes it most recently used .
put(key, value) : Insert or update the value. Updating also makes it most recently used .

Eviction rule

When inserting causes the cache to exceed capacity, evict the least recently used item.

Requirements

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

Input/Output format

You may choose an interface/class-based implementation (common in interviews). Clearly define how missing keys are represented (e.g., -1 for integers).