Quick Overview

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 LRU, Extend to LFU, Analyze Complexity

Company: Intuit

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

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.

Overview: 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

Simulate an 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,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

  1. Clarify edge cases before coding.
  2. 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.

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

  1. Clarify edge cases before coding.
  2. Keep the return value deterministic.

LRU Cache Simulator

Part 1: MediumIntuitSoftware Engineer

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]
Notes
LRU evicts key 2.
Example 2
Input
(1, [["put",1,1],["put",2,2],["get",1]])
Output
[-1]
Notes
Capacity one evicts previous key.

Constraints

  • •Inputs are Python literals matching the function signature.
  • •Return a deterministic exact-match value.

Comments (0)

No comments yet. Be the first to comment!

Submit your answer

Approved first answer today earns 30 XP
Bold⌘BItalic⌘IInline code⌘`Bullet listTab to nest (○ ■)Numbered listTab to nest (a. i.)QuoteCode block
Formatting help
Sample call
solution(2, [["put",1,1],["put",2,2],["get",1],["put",3,3],["get",2]])
Language
Case 1
Input
(2, [["put",1,1],["put",2,2],["get",1],["put",3,3],["get",2]])
Expected
[1, -1]
Case 2
Input
(1, [["put",1,1],["put",2,2],["get",1]])
Expected
[-1]

Browse More Questions