Quick Overview

This question evaluates proficiency in data structures, algorithmic complexity analysis, and system-level concerns such as concurrency, eviction semantics, and optional per-key TTL behavior when implementing an efficient cache.

Implement an LRU cache with O(1) ops

Company: OneMain Financial

Role: Data Scientist

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

Design and code an LRU cache supporting get(key) and put(key, value) in O(1) average time with capacity N. Specify your data structures, handle updates to existing keys, and define precise eviction behavior when capacity is exceeded. Discuss thread-safety concerns and how you would add an optional per-key TTL without violating big-O guarantees. Provide complexity analysis for time and space, and identify edge cases (e.g., N=1, repeated gets, large values).

Quick Answer: This question evaluates proficiency in data structures, algorithmic complexity analysis, and system-level concerns such as concurrency, eviction semantics, and optional per-key TTL behavior when implementing an efficient cache.

Design a Least Recently Used (LRU) cache that supports `get` and `put` in O(1) average time, given a fixed `capacity`. Rules: - `get(key)` returns the value if the key exists, otherwise `-1`. A successful `get` marks the key as the most recently used. - `put(key, value)` inserts or updates the value for `key`. Updating an existing key also marks it most recently used. If inserting a new key would exceed `capacity`, evict the least recently used key first. To make the cache executable here, implement a single driver function that replays a sequence of operations: `solution(capacity, operations)` - `capacity` (int): the cache capacity (>= 1). - `operations` (list): each element is either `['get', key]` or `['put', key, value]`, applied in order. Return the list of results from the `get` operations only (in order), where a miss returns `-1`. `put` operations produce no output. Classic implementation: a hash map for O(1) lookup plus a doubly linked list (or an ordered map / `OrderedDict`) to maintain recency order so that eviction and re-ordering are also O(1).

Constraints

  • 1 <= capacity
  • Keys and values are integers.
  • Each operation is ['get', key] or ['put', key, value].
  • A miss on get returns -1.
  • Both a successful get and a put (insert or update) mark the key most recently used.
  • Eviction removes the least recently used key when a new insert would exceed capacity.

Examples

Input: (2, [['put', 1, 1], ['put', 2, 2], ['get', 1], ['put', 3, 3], ['get', 2], ['put', 4, 4], ['get', 1], ['get', 3], ['get', 4]])

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

Explanation: Capacity 2. After put(1),put(2): {1,2}. get(1)=1 makes 1 MRU. put(3) evicts LRU key 2 -> {1,3}. get(2)=-1 (evicted). put(4) evicts LRU key 1 -> {3,4}. get(1)=-1, get(3)=3, get(4)=4.

Input: (1, [['put', 2, 1], ['get', 2], ['put', 3, 2], ['get', 2], ['get', 3]])

Expected Output: [1, -1, 2]

Explanation: Capacity 1 edge case. put(2,1) -> {2}. get(2)=1. put(3,2) evicts 2 -> {3}. get(2)=-1, get(3)=2.

Hints

  1. Combine a hash map (O(1) key lookup) with a structure that preserves recency order, such as a doubly linked list or an ordered map.
  2. On a successful get, move the key to the most-recently-used end. On put, insert/update then move-to-end.
  3. Evict only when inserting a NEW key pushes the size beyond capacity — updating an existing key never triggers eviction.
  4. Python's collections.OrderedDict gives O(1) move_to_end and popitem(last=False), making the whole thing O(1) per op.

Loading coding console...