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

What role is this question designed for?

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

Design LRU cache with O(1) operations | TikTok Coding Question

Design LRU cache with O(1) operations

Company: TikTok

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

Design and implement an in-memory cache that evicts the least recently used entry when capacity is reached. Support get(key) and put(key, value) in O( 1) average time. Describe the data structures you would use, how you maintain and update access order, and how you handle updates to existing keys. Discuss edge cases (e.g., capacity = 0), thread-safety considerations, and how you would test the implementation.

Quick Answer: This question evaluates a candidate's understanding of data structures and algorithm design, specifically skills in implementing constant-time cache operations, eviction policies, update handling, and concurrency/thread-safety considerations.

Implement an in-memory Least Recently Used (LRU) cache. The cache has a fixed capacity and supports two operations: - put(key, value): Insert or update a key-value pair. - get(key): Return the value for the key, or -1 if the key does not exist. When the cache is full and a new key must be inserted, evict the least recently used entry. Any successful get, and any put on an existing key, makes that key the most recently used. For this coding task, write a function that processes a sequence of cache operations and returns the result of each operation. Use a design that achieves O(1) average time per get and put. In an interview, you should also be ready to explain the data structures used, how access order is maintained, how updates are handled, what happens when capacity = 0, and what thread-safety concerns would exist in a real multi-threaded system.

Constraints

0 <= capacity <= 100000
0 <= len(operations) <= 200000
-1000000000 <= key, value <= 1000000000
Average time complexity for each get and put should be O(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: After get(1), key 1 becomes most recently used, so inserting key 3 evicts key 2. Later inserting key 4 evicts key 1.

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

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

Explanation: Updating key 1 changes its value to 10 and makes it most recently used. Then key 2 is the one evicted when key 3 is inserted.

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

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

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

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

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

Explanation: The cache can hold only one item. Inserting key 2 evicts key -1.

Input: (3, [])

Expected Output: []

Explanation: No operations means no results.

Hints

A hash map can tell you in O(1) where a key currently lives in the cache.
Use a doubly linked list with dummy head and tail nodes so you can remove the least recently used item and move accessed items to the front in O(1).

Quick Overview

This question evaluates a candidate's understanding of data structures and algorithm design, specifically skills in implementing constant-time cache operations, eviction policies, update handling, and concurrency/thread-safety considerations.