How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at OneMain Financial.

What role is this question designed for?

This question is commonly asked for Data Scientist candidates at OneMain Financial during technical interviews.

Implement an LRU cache with O(1) ops | OneMain Financial Coding Question

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.

Input: (2, [['get', 0]])

Expected Output: [-1]

Explanation: Get on an empty cache returns -1 (miss).

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

Expected Output: [10]

Explanation: Updating an existing key overwrites the value and does not grow the cache; get(1)=10.

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

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

Explanation: Capacity 3. get(1) makes 1 MRU so the LRU is 2. put(4) evicts 2. get(2)=-1; 1,3,4 all present.

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

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

Explanation: Repeated gets on key 1 keep it MRU, so the eviction on put(3) removes the never-touched key 2. get(2)=-1.

Hints

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.
On a successful get, move the key to the most-recently-used end. On put, insert/update then move-to-end.
Evict only when inserting a NEW key pushes the size beyond capacity — updating an existing key never triggers eviction.
Python's collections.OrderedDict gives O(1) move_to_end and popitem(last=False), making the whole thing O(1) per op.

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.