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.

Solution

def solution(capacity, operations):
    class Node:
        __slots__ = ('key', 'value', 'prev', 'next')

        def __init__(self, key=0, value=0):
            self.key = key
            self.value = value
            self.prev = None
            self.next = None

    class LRUCache:
        def __init__(self, capacity):
            self.capacity = capacity
            self.nodes = {}
            self.head = Node()
            self.tail = Node()
            self.head.next = self.tail
            self.tail.prev = self.head

        def _add_to_front(self, node):
            node.prev = self.head
            node.next = self.head.next
            self.head.next.prev = node
            self.head.next = node

        def _remove(self, node):
            prev_node = node.prev
            next_node = node.next
            prev_node.next = next_node
            next_node.prev = prev_node

        def _move_to_front(self, node):
            self._remove(node)
            self._add_to_front(node)

        def get(self, key):
            node = self.nodes.get(key)
            if node is None:
                return -1
            self._move_to_front(node)
            return node.value

        def put(self, key, value):
            if self.capacity == 0:
                return

            if key in self.nodes:
                node = self.nodes[key]
                node.value = value
                self._move_to_front(node)
                return

            if len(self.nodes) == self.capacity:
                lru = self.tail.prev
                self._remove(lru)
                del self.nodes[lru.key]

            node = Node(key, value)
            self.nodes[key] = node
            self._add_to_front(node)

    cache = LRUCache(capacity)
    result = []

    for op in operations:
        if op[0] == 'put':
            cache.put(op[1], op[2])
            result.append(None)
        elif op[0] == 'get':
            result.append(cache.get(op[1]))
        else:
            raise ValueError('Unknown operation: {}'.format(op[0]))

    return result

Time complexity: O(1) average per operation, O(q) total for q operations. Space complexity: O(capacity).

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.