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

What role is this question designed for?

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

Implement LRU and LFU caches | Verkada Coding Question

Implement LRU and LFU caches

Company: Verkada

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

Implement two in-memory cache classes with fixed capacity: 1. **Recent-use cache** - `get(key)`: return the value for `key`, or `-1` if the key does not exist. - `put(key, value)`: insert or update the key. - When the cache is full, evict the **least recently used** entry. - Target time complexity: **O(1)** average for both operations. 2. **Frequency-based cache** - Support the same `get` and `put` API. - When the cache is full, evict the entry with the **lowest access frequency**. - If multiple entries have the same frequency, evict the **least recently used** among them. - Target time complexity: **O(1)** average for both operations. Be prepared to explain the data structures you choose and how you would test edge cases such as updates, repeated reads, and eviction order.

Quick Answer: This question evaluates understanding of cache eviction policies and data structure design, focusing on LRU and LFU semantics and the ability to support O(1) average-time get/put operations.

Part 1: Implement Recent-use cache (LRU cache)

Design a fixed-capacity cache and simulate a sequence of operations. The cache supports 'get(key)' and 'put(key, value)'. A 'get' returns the stored value for the key, or -1 if the key is missing. A 'put' inserts a new key or updates an existing key. Any successful access or update makes that key the most recently used. If inserting a new key would exceed capacity, evict the least recently used key. Return the results of all 'get' operations in the order they appear.

Constraints

0 <= capacity <= 100000
1 <= len(operations) == len(arguments) <= 200000
Each key and value is an integer in the range [-10^9, 10^9]
If operations[i] == 'get', then len(arguments[i]) == 1
If operations[i] == 'put', then len(arguments[i]) == 2
Target complexity: O(1) average time per operation

Examples

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

Expected Output: [1, -1, 3]

Explanation: After 'get(1)', key 1 becomes most recent. Inserting key 3 evicts key 2, which is the least recently used.

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

Expected Output: [10, -1, 3]

Explanation: Updating key 1 changes its value to 10 and makes it most recent, so key 2 is evicted when key 3 is inserted.

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

Expected Output: [-1, -1]

Explanation: A cache with capacity 0 cannot store anything.

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

Expected Output: [7, -1, 8]

Explanation: With capacity 1, inserting key 2 evicts key 1.

Hints

A hash map gives fast lookup by key, but you also need to remove the oldest item and move a used item to the newest position quickly.
Think about combining a dictionary with a data structure that supports O(1) removal and insertion at both ends.

Part 2: Implement Frequency-based cache (LFU cache)

Design a fixed-capacity cache and simulate a sequence of operations. The cache supports 'get(key)' and 'put(key, value)'. A 'get' returns the value for the key, or -1 if the key is missing. A 'put' inserts a new key or updates an existing key. In this cache, every successful 'get' and every 'put' on an existing key counts as an access and increases that key's frequency by 1. New keys start with frequency 1. When the cache is full and a new key must be inserted, evict the key with the lowest frequency. If multiple keys share that lowest frequency, evict the least recently used among them. Return the results of all 'get' operations in the order they appear.

Constraints

0 <= capacity <= 100000
1 <= len(operations) == len(arguments) <= 200000
Each key and value is an integer in the range [-10^9, 10^9]
If operations[i] == 'get', then len(arguments[i]) == 1
If operations[i] == 'put', then len(arguments[i]) == 2
A 'put' on an existing key updates its value and increases its frequency by 1
Target complexity: O(1) average time per operation

Examples

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

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

Explanation: Key 2 is evicted first because it has lower frequency than key 1. Later, keys 1 and 3 have the same frequency, so the less recently used one, key 1, is evicted.

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

Expected Output: [-1, 20, 3]

Explanation: Updating key 2 increases its frequency, so key 1 becomes the eviction target when key 3 is inserted.

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

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

Explanation: After both keys reach the same frequency, key 1 is the least recently used within that frequency bucket, so it is evicted.

Input: (0, ['put', 'get'], [[1, 1], [1]])

Expected Output: [-1]

Explanation: A cache with capacity 0 cannot store anything.

Hints

You need fast lookup by key, but also fast access to the current minimum frequency.
Within each frequency level, keep keys in recency order so you can break ties by least recent use without scanning all keys.

Quick Overview

This question evaluates understanding of cache eviction policies and data structure design, focusing on LRU and LFU semantics and the ability to support O(1) average-time get/put operations.