Quick Overview

This question evaluates a candidate's ability to design and implement efficient cache eviction policies while managing time and space complexity guarantees for mutable key-value stores.

Implement an LRU cache

Company: Affirm

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: easy

Interview Round: Onsite

## Problem Design and implement an **LRU (Least Recently Used) cache** that supports the following operations in **average O(1)** time: - `get(key) -> value`: Return the value associated with `key` if it exists in the cache; otherwise return `-1`. Accessing a key makes it **most recently used**. - `put(key, value)`: Insert or update the value for `key`. If inserting causes the number of keys to exceed the cache `capacity`, evict the **least recently used** key. ## Input/Output You will implement a class (or module) with: - Constructor: `LRUCache(capacity)` - Methods: `get(key)` and `put(key, value)` ## Constraints (typical) - `1 <= capacity <= 10^5` - Keys and values are integers (or comparable scalar types) - Must achieve **O(1)** average time for both operations and **O(capacity)** space ## Notes - “Most recently used” means most recently accessed via `get` or updated via `put`. - Updating an existing key counts as a recent use.

Quick Answer: This question evaluates a candidate's ability to design and implement efficient cache eviction policies while managing time and space complexity guarantees for mutable key-value stores.

Design an LRU (Least Recently Used) cache that supports get and put in average O(1) time. In this function-based version, you are given the cache capacity and a sequence of operations to execute. A get operation returns the value for a key if present, otherwise -1, and makes that key the most recently used. A put operation inserts or updates a key-value pair, and updating an existing key also makes it the most recently used. If inserting a new key causes the cache to exceed capacity, evict the least recently used key.

Constraints

  • 1 <= capacity <= 10^5
  • 0 <= len(operations) <= 2 * 10^5
  • operations[i] is either [0, key] or [1, key, value]
  • -10^9 <= key, value <= 10^9
  • Both get and put must run in average O(1) time

Examples

Input: (2, [[1,1,1], [1,2,2], [0,1], [1,3,3], [0,2], [1,4,4], [0,1], [0,3], [0,4]])

Expected Output: [1, -1, -1, 3, 4]

Explanation: After get(1), key 1 becomes most recent. put(3,3) evicts key 2. Later put(4,4) evicts key 1. The get results are 1, -1, -1, 3, and 4.

Input: (2, [[1,1,1], [1,2,2], [1,1,10], [0,1], [1,3,3], [0,2], [0,1], [0,3]])

Expected Output: [10, -1, 10, 3]

Explanation: Updating key 1 changes its value to 10 and makes it most recent. When key 3 is inserted, key 2 is least recently used and is evicted.

Hints

  1. Use a hash map to find cache entries by key in O(1) average time.
  2. Use a doubly linked list to track recency: move accessed or updated nodes to the front, and evict from the back.

Loading coding console...