How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Bloomberg.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Bloomberg during technical interviews.

Design variable-size LRU cache | Bloomberg Coding Question

Quick Overview

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.

Design variable-size LRU cache

Company: Bloomberg

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Technical Screen

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( 1) 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.

Quick Answer: 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.

Implement an in-memory cache with least-recently-used (LRU) eviction where **each entry carries its own size in bytes**. Unlike a classic LRU cache that counts entries, this cache is bounded by a **byte budget** (`capacity`). Implement a `VLRUCache` supporting: - `set(key, value, size)` — insert or update `key`. Updating an existing key replaces its value and size **atomically** and refreshes its recency. If a single entry's `size` exceeds the cache `capacity`, the insert is **rejected** (return `false`) and any previously stored entry for that key is removed. Otherwise insert/update, then evict least-recently-used entries until total used bytes `<= capacity`, and return `true`. - `get(key)` — return the value (refreshing recency), or `-1` if absent. - `delete(key)` — remove `key`; return `true` if it existed, else `false`. - `resize(newCapacity)` — change the byte budget, then evict least-recently-used entries until total used bytes `<= newCapacity`. Accessing (`get`) or updating (`set`) an entry makes it most-recently-used. Eviction always removes the least-recently-used entry first. **Driver format.** Because this is a stateful design, your `solution` is driven by a list of operations and returns a list of results, one per operation: - `['init', capacity]` → returns `None` (creates a fresh cache; always the first op) - `['set', key, value, size]` → returns `true`/`false` - `['get', key]` → returns the value or `-1` - `['delete', key]` → returns `true`/`false` - `['resize', newCapacity]` → returns `None` - `['keys']` → returns the keys in most-recently-used → least-recently-used order (for inspection) - `['used']` → returns the current total used bytes (for inspection) Return the list of per-operation results.

Constraints

The first operation is always ['init', capacity] with capacity >= 0.
size >= 0 for every set; an entry with size > capacity is rejected (set returns false).
Keys are hashable/comparable; values are arbitrary (compared by equality in tests).
Eviction always removes the least-recently-used entry first until used <= capacity.
get/set must be O(1) amortized (excluding the eviction work).

Examples

Input: ([['init', 10], ['set', 'a', 'A', 3], ['set', 'b', 'B', 3], ['set', 'c', 'C', 3], ['used'], ['keys'], ['set', 'd', 'D', 3], ['keys'], ['get', 'a']],)

Expected Output: [None, True, True, True, 9, ['c', 'b', 'a'], True, ['d', 'c', 'b'], -1]

Explanation: After inserting a,b,c (3 bytes each) used=9<=10 and MRU->LRU is c,b,a. Inserting d (3 bytes) pushes used to 12>10, so the LRU 'a' is evicted, leaving d,c,b. get('a') then returns -1 because a was evicted.

Input: ([['init', 10], ['set', 'a', 'A', 4], ['set', 'b', 'B', 4], ['get', 'a'], ['set', 'c', 'C', 4], ['keys']],)

Expected Output: [None, True, True, 'A', True, ['c', 'a']]

Explanation: a and b each use 4 bytes (used=8). get('a') refreshes a to MRU, making b the LRU. Inserting c (used would be 12>10) evicts the LRU 'b', leaving c (MRU) then a.

Input: ([['init', 10], ['set', 'a', 'A', 3], ['set', 'b', 'B', 3], ['set', 'a', 'AA', 8], ['keys'], ['used']],)

Expected Output: [None, True, True, True, ['a'], 8]

Explanation: Updating 'a' to size 8 raises used from 6 to 11 (>10), so eviction runs. 'a' was just refreshed to MRU, so the LRU 'b' (3 bytes) is evicted, dropping used to 8 with only 'a' remaining.

Input: ([['init', 10], ['set', 'a', 'A', 6], ['set', 'b', 'B', 2], ['set', 'a', 'AA', 3], ['used'], ['keys']],)

Expected Output: [None, True, True, True, 5, ['a', 'b']]

Explanation: Shrink update: 'a' goes from 6 to 3 bytes, so used = 8 - 3 = 5 (<=10, no eviction). The update also refreshes 'a' to MRU, giving order a, b.

Input: ([['init', 5], ['set', 'big', 'X', 6], ['get', 'big'], ['used']],)

Expected Output: [None, False, -1, 0]

Explanation: An entry of size 6 exceeds capacity 5, so set returns False and nothing is stored. get('big') returns -1 and used stays 0.

Input: ([['init', 12], ['set', 'a', 'A', 4], ['set', 'b', 'B', 4], ['set', 'c', 'C', 4], ['delete', 'a'], ['keys'], ['delete', 'c'], ['keys'], ['delete', 'zzz']],)

Expected Output: [None, True, True, True, True, ['c', 'b'], True, ['b'], False]

Explanation: With a,b,c stored (MRU->LRU c,b,a), deleting the tail 'a' leaves c,b; deleting the head 'c' leaves b; deleting a missing key 'zzz' returns False.

Input: ([['init', 12], ['set', 'a', 'A', 4], ['set', 'b', 'B', 4], ['set', 'c', 'C', 4], ['get', 'a'], ['resize', 5], ['keys'], ['used']],)

Expected Output: [None, True, True, True, 'A', None, ['a'], 4]

Explanation: used=12 with order c,b,a; get('a') makes a the MRU (order a,c,b). Resizing capacity to 5 evicts LRU entries until used<=5: 'b' then 'c' are evicted (used 12->8->4), leaving only 'a' (4 bytes).

Input: ([['init', 0], ['set', 'a', 'A', 1], ['used'], ['keys']],)

Expected Output: [None, False, 0, []]

Explanation: Capacity 0 rejects any entry of positive size, so set returns False, used stays 0, and the cache is empty.

Hints

Pair a hashmap (key -> node) with a doubly linked list ordered most-recently-used (head) to least-recently-used (tail). The map gives O(1) lookup; the list gives O(1) move-to-front and O(1) tail eviction.
Track a running `used` byte total. On an in-place update, adjust `used += newSize - oldSize` BEFORE touching recency, so shrink and expand are handled by the same code path.
Centralize eviction in one helper: `while used > capacity and list is non-empty: evict tail`. Call it after every insert/update and inside resize — that single helper makes resize-below-usage fall out for free.
Reject an oversized insert (size > capacity) early, but still remove any existing entry for that key first so the cache never holds a stale value the caller intended to overwrite.

Quick Overview