Design and implement an LRU cache

Q: Design and implement an LRU cache

This question evaluates knowledge of data structures, algorithmic design, API design, and memory/resource management required to implement an efficient eviction-based cache (LRU) that supports constant-time operations.

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...

Problem

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

get(key) → returns the value associated with key if present; otherwise returns a sentinel (e.g., -1 ). Accessing a key counts as making it most recently used .
put(key, value) → inserts or updates the value for key . If the cache exceeds its capacity, it must evict the least recently used item.

Requirements

The prompt may describe data structures in C; you may implement in C or C++ (clarify your choice).
Define the cache API (constructor/init, get , put , cleanup/free if needed).
Handle edge cases:
- Updating an existing key
- Capacity = 0
- Repeated get calls

Input/Output (for testing)

You may assume the interviewer will test by calling your API methods in sequence (typical library-design style), rather than via stdin/stdout.

Design and implement an LRU cache

Quick Overview

Problem

Requirements

Input/Output (for testing)

Comments (0)