Implement a recency-eviction bounded cache

Q: Implement a recency-eviction bounded cache

This question evaluates understanding of recency-based eviction (LRU) cache design and proficiency with core data structures and algorithmic complexity, including achieving amortized O(1) operations and O(N) space.

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

Implement an in-memory key–value store with a fixed capacity N that uses recency-based eviction. Support: get(key) -> value or -1 if missing, and put(key, value) which inserts or updates the key. When capacity is exceeded, evict the least-recently-accessed entry. Target amortized O(

time per operation and O(N) space. Describe the data structures you would use, provide pseudocode for both operations, and explain how you would handle: updates to existing keys, N = 0, thread-safety considerations, and how to extend the design to support peek (read without affecting recency) and delete(key).

Implement a recency-eviction bounded cache

Overview

Comments (0)