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.

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

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.

Loading coding console...