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.

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.

Hints

  1. A hash map can tell you in O(1) where a key currently lives in the cache.
  2. 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).

Loading coding console...