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 NVIDIA.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at NVIDIA during technical interviews.

Design and implement an LRU cache | NVIDIA Coding Question

Design and implement an LRU cache

Company: NVIDIA

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

## Problem Design and implement an **LRU (Least Recently Used) Cache** that supports the following operations in **O(1)** average time: - `get(key)` → returns the value associated with `key` if present; otherwise returns a sentinel (e.g., `-1`). Accessing a key counts as making it **most recently used**. - `put(key, value)` → inserts or updates the value for `key`. If the cache exceeds its capacity, it must evict the **least recently used** item. ## Requirements - The prompt may describe data structures in C; you may implement in **C or C++** (clarify your choice). - Define the cache API (constructor/init, `get`, `put`, cleanup/free if needed). - Handle edge cases: - Updating an existing key - Capacity = 0 - Repeated `get` calls ## Input/Output (for testing) You may assume the interviewer will test by calling your API methods in sequence (typical library-design style), rather than via stdin/stdout.

Quick Answer: This question evaluates knowledge of data structures, algorithmic design, API design, and memory/resource management required to implement an efficient eviction-based cache (LRU) that supports constant-time operations.

Design a data structure that implements a **Least Recently Used (LRU) cache** supporting two operations in **O(1)** average time: - `get(key)` — return the value of `key` if it exists in the cache, otherwise return `-1`. A successful `get` marks the key as the **most recently used**. - `put(key, value)` — insert or update the value of `key`. If the cache is at capacity, evict the **least recently used** key before inserting. When `capacity == 0` the cache stores nothing, so every `put` is a no-op and every `get` returns `-1`. Updating an existing key with `put` also counts as a use and refreshes its recency. **Testing harness.** Because the cache is stateful, implement a single driver method `lruCache(capacity, operations)` that constructs a cache of the given `capacity`, replays the list of `operations` in order, and returns a list of results — one entry per operation. Each operation is either `["put", key, value]` or `["get", key]`. For a `put`, append `null`/`None` to the result list; for a `get`, append the returned value (the stored value, or `-1` on a miss). **Example** ``` capacity = 2 operations = [["put",1,1],["put",2,2],["get",1],["put",3,3],["get",2],["put",4,4],["get",1],["get",3],["get",4]] -> [null, null, 1, null, -1, null, -1, 3, 4] ``` After `put(3,3)` the cache is full and key 2 was least recently used, so it is evicted (`get(2)` → -1). After `put(4,4)`, key 1 is evicted (`get(1)` → -1), leaving keys 3 and 4.

Constraints

0 <= capacity
Each operation is either ["put", key, value] or ["get", key]
Keys and values are integers
get and put must each run in O(1) average time
When capacity == 0, the cache stores nothing: every put is a no-op and every get returns -1

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: [None, None, 1, None, -1, None, -1, 3, 4]

Explanation: Canonical trace. put(3) evicts key 2 (LRU after get(1) touched key 1), so get(2) -> -1. put(4) evicts key 1, so get(1) -> -1; keys 3 and 4 remain.

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

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

Explanation: Updating key 2 then getting it returns the updated value 2. After put(1) and put(4) the cache is full and key 2 was least recently used, so it is evicted: get(2) -> -1.

Input: (0, [["put", 1, 1], ["get", 1], ["put", 2, 2], ["get", 2]])

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

Explanation: Capacity 0 edge case: the cache never stores anything, so every put is a no-op and every get returns -1.

Input: (1, [["put", 1, 1], ["get", 1], ["put", 2, 2], ["get", 1], ["get", 2]])

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

Explanation: Capacity 1: put(2) evicts key 1, so get(1) -> -1 and get(2) -> 2.

Input: (2, [["get", 5]])

Expected Output: [-1]

Explanation: get on an empty cache returns the sentinel -1.

Input: (3, [["put", 1, 10], ["put", 2, 20], ["put", 3, 30], ["get", 1], ["put", 4, 40], ["get", 2], ["get", 3], ["get", 4], ["get", 1]])

Expected Output: [None, None, None, 10, None, -1, 30, 40, 10]

Explanation: Capacity 3 fills with keys 1,2,3. get(1) promotes key 1. put(4) evicts the LRU key 2 -> get(2) -1; keys 3,4,1 survive.

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

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

Explanation: Re-putting key 1 updates and promotes it (get returns 5). After put(2) and put(3) the cache exceeds capacity; key 1 was least recently used relative to 2, so put(3) evicts key 1: get(1) -> -1.

Hints

Combine a hash map (for O(1) key lookup) with a doubly linked list (for O(1) reordering and eviction). The map points each key to its list node.
On get, if the key exists, move its node to the most-recently-used end and return its value; otherwise return -1.
On put, update-and-promote if the key exists; otherwise insert at the MRU end and, if size now exceeds capacity, evict the node at the LRU end.
Python's collections.OrderedDict gives you both behaviors for free: move_to_end(key) promotes, and popitem(last=False) evicts the least recently used entry.
Guard the capacity == 0 case so put never inserts and the cache stays empty.

Quick Overview

This question evaluates knowledge of data structures, algorithmic design, API design, and memory/resource management required to implement an efficient eviction-based cache (LRU) that supports constant-time operations.