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 Onsite rounds at Google.

What role is this question designed for?

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

Implement an LRU cache | Google Coding Question

Implement an LRU cache

Company: Google

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

Design a key-value cache with a fixed capacity. It must support: - `get(key)`: return the value for the key if it exists, otherwise return `-1`. - `put(key, value)`: insert or update the key. If the cache is full, evict the least recently used key before inserting the new one. Both operations should run in O(1) average time.

Quick Answer: This question evaluates competency in data structure design and algorithmic complexity by requiring a bounded key-value cache with O(1) average-time get and put operations.

Design and simulate a key-value cache with a fixed capacity using Least Recently Used (LRU) eviction. The cache stores integer keys and values and must support two operations: get(key), which returns the value for the key if it exists or -1 otherwise, and put(key, value), which inserts or updates a key. Whenever a key is accessed by get or inserted/updated by put, it becomes the most recently used key. If a new key is inserted when the cache is already full, evict the least recently used key first. Both operations should run in O(1) average time.

Constraints

0 <= capacity <= 10^5
0 <= len(operations) <= 2 * 10^5
Each operation is either ('get', key) or ('put', key, value)
Keys and values are integers in the range [-10^9, 10^9]

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: After inserting 1 and 2, get(1) makes key 1 most recent. Putting 3 evicts key 2. Putting 4 later evicts key 1. Final gets return -1, 3, and 4.

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

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

Explanation: With capacity 1, updating key 2 changes its value to 2. Inserting key 3 then evicts key 2.

Input: (2, [("get", 5), ("put", 5, 50), ("put", 6, 60), ("get", 5), ("put", 7, 70), ("get", 6), ("put", 5, 55), ("get", 5), ("get", 7)])

Expected Output: [-1, None, None, 50, None, -1, None, 55, 70]

Explanation: The first get misses. After get(5), key 5 becomes most recent, so inserting 7 evicts key 6. Updating key 5 keeps it in the cache with its new value.

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

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

Explanation: A cache with capacity 0 cannot store any items, so every get returns -1.

Hints

You need one structure for O(1) key lookup and another structure that can remove and reinsert nodes in O(1) when recency changes.
A doubly linked list with dummy head and tail nodes makes it easy to move a key to the most recently used position and evict the least recently used key.

Quick Overview

This question evaluates competency in data structure design and algorithmic complexity by requiring a bounded key-value cache with O(1) average-time get and put operations.