Design a Recency-Eviction Cache
Company: Pinduoduo
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Implement a fixed-capacity key-value cache that removes the least recently used entry when it becomes full.
Support the following operations:
- `get(key)`: Return the value associated with `key` if it exists; otherwise return `-1`. Accessing a key marks it as recently used.
- `put(key, value)`: Insert or update the value for `key`. If the cache is already at capacity and the key does not exist, evict the least recently used key before inserting the new one. Updating an existing key should also mark it as recently used.
Requirements:
- Cache capacity is a positive integer provided at initialization.
- Both `get` and `put` should run in average `O(1)` time.
- You may assume keys are unique integers and values are integers.
Example:
- Capacity = 2
- `put(1, 10)`
- `put(2, 20)`
- `get(1)` returns `10`
- `put(3, 30)` evicts key `2`
- `get(2)` returns `-1`
- `put(4, 40)` evicts key `1`
- `get(1)` returns `-1`
- `get(3)` returns `30`
- `get(4)` returns `40`
Quick Answer: This question evaluates proficiency with data structures and algorithmic design for implementing a fixed-capacity key-value cache that enforces recency-based eviction while meeting average O(1) get and put performance.
Simulate a fixed-capacity LRU cache and return get outputs.
Constraints
- Inputs are Python literals matching the function signature.
- Return a deterministic exact-match value.
Examples
Input: (2, [["put",1,10],["put",2,20],["get",1],["put",3,30],["get",2],["put",4,40],["get",1],["get",3],["get",4]])
Expected Output: [10, -1, -1, 30, 40]
Explanation: Standard LRU example.
Input: (1, [["put",1,1],["put",2,2],["get",1],["get",2]])
Expected Output: [-1, 2]
Explanation: Capacity one evicts previous key.
Hints
- Clarify edge cases before coding.
- Keep the return value deterministic.