Coding questions · Intuit
Implement LRU, Extend to LFU, Analyze Complexity
This question evaluates understanding of cache eviction policies (LRU and LFU), frequency tracking, and the design of data structures that support efficient get/put operations while meeting time and space complexity constraints.
Implement an in-memory Least Recently Used (LRU) cache with capacity N that supports get(key) -> value and put(key, value). Achieve O(1) average time per operation using appropriate data structures; justify your choices and analyze time and space complexity. Follow-up: Modify the design to implement a Least Frequently Used (LFU) cache with O(1) or amortized O(1) operations; explain the eviction policy, how you track and update frequencies on get/put, and how you break ties by recency.
LRU Cache Simulator
Simulate an LRU cache and return get outputs.
Examples
Example 1
Input: (2, [["put",1,1],["put",2,2],["get",1],["put",3,3],["get",2]])
Output: [1, -1]
Explanation: LRU evicts key 2.
Example 2
Input: (1, [["put",1,1],["put",2,2],["get",1]])
Output: [-1]
Explanation: Capacity one evicts previous key.
Hints
- Clarify edge cases before coding.
- Keep the return value deterministic.
LFU Cache Simulator
Simulate an LFU cache; evict lowest frequency and break ties by least recent access. Return get outputs.
Examples
Example 1
Input: (2, [["put",1,1],["put",2,2],["get",1],["put",3,3],["get",2],["get",3]])
Output: [1, -1, 3]
Explanation: LFU evicts lower-frequency key; ties by recency.
Example 2
Input: (0, [["put",1,1],["get",1]])
Output: [-1]
Explanation: Zero capacity stores nothing.
Hints
- Clarify edge cases before coding.
- Keep the return value deterministic.