Implement an LRU cache

Q: Implement an LRU cache

This question evaluates a candidate's ability to design and implement efficient data structures that meet strict O(1) time constraints while managing access-based eviction policies, testing competencies in algorithmic reasoning, state management, and performance trade-offs.

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

Design and implement an in-memory cache that evicts entries using the Least Recently Used (LRU) policy.

The cache should store key–value pairs and support the following operations:

LRUCache(int capacity) : Initialize the cache with a positive integer capacity representing the maximum number of key–value pairs it can hold.
int get(int key) :
- If the key exists in the cache, return its value and mark this key as most recently used .
- If the key does not exist, return -1 .
void put(int key, int value) :
- Insert or update the value of the given key.
- When inserting a new key causes the number of items to exceed capacity , you must evict exactly one key–value pair: the one that has been least recently used (i.e., the one whose get or put was accessed furthest in the past).
- Updating an existing key should also mark it as most recently used .

Requirements:

All get and put operations must run in O(1) average time.
You may assume:
- Keys and values are integers.
- capacity >= 1 .

Describe the data structures you would use and then implement the LRU cache in a language of your choice.

Implement an LRU cache

Overview

Comments (0)