Design variable-size LRU cache

Q: Design variable-size LRU cache

This question evaluates understanding of cache design and eviction policies (LRU), management of variable-sized entries and memory budgeting, and the implementation of efficient data structures that support amortized O(1) access, updates and correct capacity accounting.

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 cache with least-recently-used eviction where each entry has a variable size in bytes. The cache exposes set(key, value, size), get(key), delete(key), and resize(newCapacity). The cache capacity is a byte budget; inserting or resizing must evict least-recently-used entries until the total size is <= capacity. Accessing or updating an entry refreshes its recency. Updates to an existing key replace the value and size atomically. Reject inserts whose single entry size exceeds the capacity. Aim for O(

amortized time for get, set (excluding evictions) and O(n) space. Provide unit tests covering: updates that shrink/expand size, eviction order after mixed gets/sets, deletion of head/tail, and behavior when capacity is reduced below current usage.

Design variable-size LRU cache

Overview

Comments (0)