Implement LRUCache with O(1) Operations and Thread Safety
Company: Pinterest
Role: Data Scientist
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Onsite
##### Scenario
High-traffic API needs constant-time eviction cache.
##### Question
Implement an LRUCache supporting get(key) and put(key,val) in O(
1). Describe thread-safety considerations for concurrent access.
##### Hints
Combine hash map with doubly-linked list; lock striping or concurrent linked hash map for threads.
Quick Answer: This question evaluates a candidate's ability to implement a constant-time LRU cache and reason about thread-safety and concurrent access, testing data structure design and concurrency competencies in the Coding & Algorithms domain.
Implement lru_ops(ops, capacity) to simulate an LRU cache with the given capacity. Each operation is either ["put", key, value] or ["get", key]. get(key) returns the value for key or -1 if absent, and marks the key as most-recently-used. put(key, value) inserts or updates key, marking it most-recently-used; if capacity is exceeded, evict the least-recently-used key. Return a list of integers containing the results of get operations in order. Assume single-threaded execution for testing.
Constraints
- 1 <= capacity <= 100000
- 0 <= len(ops) <= 200000
- Each op is ["get", key] or ["put", key, value]
- Keys and values are 32-bit signed integers
- Average O(1) time per operation
- Space O(capacity)
Solution
from typing import List
def lru_ops(ops: list, capacity: int) -> list:
# LRU cache implementation: hash map + doubly linked list for O(1) ops.
# Thread-safety (not tested here): wrap public methods with a mutex.
# For higher concurrency, consider RW-lock or sharded caches with a global recency policy if required.
class _Node:
__slots__ = ("k", "v", "prev", "next")
def __init__(self, k: int = 0, v: int = 0):
self.k = k
self.v = v
self.prev = None
self.next = None
class _LRU:
def __init__(self, cap: int):
self.cap = cap
self.map = {}
self.head = _Node() # sentinel head (MRU side)
self.tail = _Node() # sentinel tail (LRU side)
self.head.next = self.tail
self.tail.prev = self.head
def _add_first(self, node: _Node) -> None:
node.prev = self.head
node.next = self.head.next
self.head.next.prev = node
self.head.next = node
def _remove(self, node: _Node) -> None:
p = node.prev
n = node.next
p.next = n
n.prev = p
node.prev = node.next = None
def _move_to_front(self, node: _Node) -> None:
self._remove(node)
self._add_first(node)
def _pop_last(self) -> _Node:
lru = self.tail.prev
if lru is self.head:
return None
self._remove(lru)
return lru
def get(self, key: int) -> int:
node = self.map.get(key)
if node is None:
return -1
self._move_to_front(node)
return node.v
def put(self, key: int, value: int) -> None:
node = self.map.get(key)
if node is not None:
node.v = value
self._move_to_front(node)
return
node = _Node(key, value)
self.map[key] = node
self._add_first(node)
if len(self.map) > self.cap:
evicted = self._pop_last()
if evicted is not None:
self.map.pop(evicted.k, None)
lru = _LRU(capacity)
out: List[int] = []
for op in ops:
if not op:
continue
t = op[0]
if t == "get":
key = op[1]
out.append(lru.get(key))
elif t == "put":
key = op[1]
val = op[2]
lru.put(key, val)
else:
# Unknown operation; ignore for robustness
pass
return out
Explanation
Use a doubly linked list to maintain recency and a hash map to locate nodes in O(1). On get(key), if present, move the node to the list head (MRU) and return its value; otherwise return -1. On put(key, value), if the key exists, update and move it to the head; if it does not exist, create a new node at the head and, if capacity is exceeded, remove the tail's previous node (LRU) and delete it from the map. Thread-safety (not enforced in tests): protect get/put with a single mutex to maintain list and map consistency. For higher concurrency, consider a read-write lock (many readers, exclusive writers) or sharding the cache (lock striping) across multiple segments while ensuring that updates to list and map remain atomic within each shard.
Time complexity: O(1) average per operation. Space complexity: O(capacity).
Hints
- Combine a hash map (key -> node) with a doubly linked list to track recency.
- Move a node to the list head on every get/put; evict from the tail.
- For thread-safety in real systems, guard the cache with a single mutex; for higher concurrency, consider a read-write lock or segmenting (lock striping) while keeping list and map updates atomic.