Implement LRU, Extend to LFU, Analyze Complexity
Company: Intuit
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Technical Screen
Quick Answer: 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.
LRU Cache Simulator
Constraints
- Inputs are Python literals matching the function signature.
- Return a deterministic exact-match value.
Examples
Input: (2, [["put",1,1],["put",2,2],["get",1],["put",3,3],["get",2]])
Expected Output: [1, -1]
Explanation: LRU evicts key 2.
Input: (1, [["put",1,1],["put",2,2],["get",1]])
Expected Output: [-1]
Explanation: Capacity one evicts previous key.
Hints
- Clarify edge cases before coding.
- Keep the return value deterministic.
LFU Cache Simulator
Constraints
- Inputs are Python literals matching the function signature.
- Return a deterministic exact-match value.
Examples
Input: (2, [["put",1,1],["put",2,2],["get",1],["put",3,3],["get",2],["get",3]])
Expected Output: [1, -1, 3]
Explanation: LFU evicts lower-frequency key; ties by recency.
Input: (0, [["put",1,1],["get",1]])
Expected Output: [-1]
Explanation: Zero capacity stores nothing.
Hints
- Clarify edge cases before coding.
- Keep the return value deterministic.