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

What role is this question designed for?

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

Implement an LRU Cache | Bytedance Coding Question

Implement an LRU Cache

Company: Bytedance

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

Design and implement a fixed-capacity key-value cache that evicts the least recently used item when it becomes full. Support the following operations: - `get(key)`: Return the value associated with `key` if it exists; otherwise return `-1`. - `put(key, value)`: Insert or update the value for `key`. If inserting a new key causes the cache to exceed its capacity, remove the least recently used entry. A key becomes most recently used whenever it is accessed by `get` or updated/inserted by `put`. Requirements: - The cache capacity is given in the constructor. - Both `get` and `put` should run in average `O(1)` time. - You may choose any reasonable class or function interface.

Quick Answer: This question evaluates competency in designing efficient stateful data structures, understanding cache eviction policies (least recently used), and meeting average O(1) time complexity requirements for get and put operations.

Design an LRU (Least Recently Used) cache and simulate a sequence of cache operations. The cache has a fixed capacity and stores integer key-value pairs. Implement a function `solution(capacity, operations)` where: - `capacity` is the maximum number of entries the cache can hold. - `operations` is a list of operations, where each operation is either: - `("get", key)` -> return the value for `key` if it exists, otherwise `-1` - `("put", key, value)` -> insert or update the value for `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 full, evict the least recently used key. Return a list containing the results of all `get` operations in order. Your implementation should achieve average `O(1)` time for both `get` and `put`.

Constraints

0 <= capacity <= 10^5
0 <= len(operations) <= 2 * 10^5
Each operation is either ("get", key) or ("put", key, value)
-10^9 <= key, value <= 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: [1, -1, -1, 3, 4]

Explanation: After accessing key 1, key 2 becomes least recently used and is evicted by put(3,3). Later key 1 is evicted by put(4,4).

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

Expected Output: [2, -1]

Explanation: Updating key 2 changes its value and makes it most recently used. When key 4 is inserted, key 2 is the least recently used and gets evicted.

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

Expected Output: [-1, 20, 25]

Explanation: With capacity 1, inserting key 2 evicts key 1. Updating key 2 later changes its stored value to 25.

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

Expected Output: [-1, -1]

Explanation: A cache with capacity 0 can never store anything, so every get returns -1.

Input: (3, [])

Expected Output: []

Explanation: No operations means there are no get results to return.

Hints

You need one structure for fast lookup by key and another structure for fast reordering when a key becomes most recently used.
A doubly linked list with dummy head and tail nodes makes O(1) insertion, removal, and eviction much easier.

Quick Overview

This question evaluates competency in designing efficient stateful data structures, understanding cache eviction policies (least recently used), and meeting average O(1) time complexity requirements for get and put operations.