Implement LRUCache with O(1) Operations and Thread Safety

Q: Implement LRUCache with O(1) Operations and Thread Safety

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.

Q: 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.

Q: What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Pinterest.

Q: What role is this question designed for?

This question is commonly asked for Data Scientist candidates at Pinterest during technical interviews.

Question

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

PracHub · Accepted Answer

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

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.

Quick Overview

Explanation

Hints

Quick Overview