Implement a size-bounded LRU cache
Company: Snapchat
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Onsite
Design and implement an LRU (Least Recently Used) cache where the cache capacity is measured by **total size**, not by item count.
Each cached item has a variable `size` (positive integer). The cache has a maximum capacity `maxSize`.
## Operations
Implement the following operations:
1. `get(key) -> value | null`
- Return the value if `key` exists, else return `null`.
- If the key exists, mark it as **most recently used**.
2. `put(key, value, size)`
- Insert or update an item with the given `size`.
- Mark the item as **most recently used**.
- If inserting/updating causes total cached size to exceed `maxSize`, evict **one or more** least-recently-used items until `totalSize <= maxSize`.
## Requirements / Clarifications
- `size` is a positive integer.
- If `size > maxSize`, define and document expected behavior (commonly: do not store the item at all).
- Updating an existing key may change its size; eviction may be needed.
- Target time complexity: `O(1)` average time for `get` and `put` (excluding time spent evicting multiple items).
## Example
`maxSize = 10`
- `put(A, ..., size=6)` → total=6
- `put(B, ..., size=5)` → total would be 11, so evict LRU items until total<=10 (likely evict `A` if it is LRU)
Describe data structures and invariants you would maintain.
Quick Answer: This question evaluates a candidate's ability to design and implement efficient data structures for capacity-bound caching, focusing on handling variable-sized items, eviction policies, and maintaining O(1) average get/put invariants.
Simulate an LRU cache bounded by total item size. Oversized items are not stored. Return outputs for operations.
Constraints
- Inputs are Python literals matching the function signature.
- Return a deterministic exact-match value.
Examples
Input: (10, [['put','A','a',6],['put','B','b',5],['get','A'],['get','B']])
Expected Output: [None, None, None, 'b']
Explanation: Evicts A after B insertion.
Input: (5, [['put','A','a',10],['get','A']])
Expected Output: [None, None]
Explanation: Oversized item not stored.
Input: (6, [['put','A','a',3],['put','A','b',5],['get','A']])
Expected Output: [None, None, 'b']
Explanation: Update size and value.
Hints
- Use deterministic tie-breaking for prompts with multiple valid outputs.
- For design-style APIs, simulate operations with explicit inputs.