Design data structure similar to LRU cache
Company: Google
Role: Machine Learning Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Onsite
You are asked to design and implement a data structure that behaves similarly to an LRU (Least Recently Used) cache, but with a small variation:
- The data structure stores key–value pairs.
- It has a fixed capacity `capacity`.
- When inserting a new key and the cache is full, it should evict an existing key according to a modified eviction rule (a variant of LRU). For example, assume the rule is:
- Normally evict the least recently used key, **except** that keys explicitly "pinned" by the user should not be evicted until they are unpinned.
Your data structure must support the following operations in average O(1) time:
- `get(key) -> value or -1`
Return the value associated with `key` if it exists; otherwise return `-1`. Accessing a key counts as using it recently.
- `put(key, value)`
Insert or update the value of `key`. If inserting and the number of stored keys exceeds `capacity`, evict one key according to the modified eviction rule described above.
- `pin(key)`
Mark an existing key as pinned so that it cannot be evicted while pinned.
- `unpin(key)`
Remove the pinned status from a key so that it can again be evicted according to the LRU policy.
Assume:
- `1 <= capacity <= 10^5`
- Keys and values are integers.
- The total number of operations is up to `10^5`.
Describe the data structure you would use and implement the four operations with the required time complexity.
Overview: This question evaluates understanding of data structures and algorithmic design for cache eviction policies, specifically the ability to implement an LRU-like cache with support for pinned entries while preserving average O(1) operations for get, put, pin, and unpin.
Read the full Google Machine Learning Engineer interview experience this question came from
Design a cache that behaves like an LRU cache with a pin/unpin feature. The cache stores integer key-value pairs and has a fixed capacity.
To make the behavior precise, use these rules:
- Only unpinned keys participate in the LRU eviction order.
- `get(key)` returns the value for `key`, or `-1` if it does not exist. If the key exists and is unpinned, it becomes the most recently used unpinned key.
- `put(key, value)` inserts or updates a key.
- If the key already exists, update its value. If it is unpinned, it becomes the most recently used unpinned key.
- If the key is new and the cache is full, evict the least recently used unpinned key.
- If the cache is full and every stored key is pinned, ignore the insertion.
- `pin(key)` marks an existing key as pinned and removes it from the eviction order.
- `unpin(key)` removes the pinned status from an existing key and makes it the most recently used unpinned key.
- Calling `pin` or `unpin` on a missing key does nothing.
You are given `capacity` and a list of operations. Return the results of all `get` operations in order.
Constraints
- 1 <= capacity <= 10^5
- 1 <= len(operations) <= 10^5
- Keys and values are integers
- Each operation should run in O(1) average time
Examples
Input: (2, [('put', 1, 10), ('put', 2, 20), ('get', 1), ('put', 3, 30), ('get', 2), ('get', 1), ('get', 3)])
Expected Output: [10, -1, 10, 30]
Explanation: After `get(1)`, key 1 becomes most recent, so inserting key 3 evicts key 2. The outputs come from the four `get` calls.
Input: (2, [('put', 1, 1), ('put', 2, 2), ('pin', 1), ('put', 3, 3), ('get', 1), ('get', 2), ('get', 3)])
Expected Output: [1, -1, 3]
Explanation: Key 1 is pinned, so when key 3 is inserted, key 2 is the least recently used unpinned key and gets evicted.
Hints
- A hash map gives O(1) access to a key, but you also need a way to update recency in O(1).
- Keep only unpinned keys in the LRU order. When a key is pinned, remove it from that order; when it is unpinned, append it as most recent.
Community answers
Answer by selenewang941015
from typing import List, Tuple, Union
class Node:
def init(self, key: int, value: int, pinned: bool = False):
self.key = key
self.value = value
self.pinned = pinned
self.prev = None
self.next = None
class PinnedLRUCache:
def init(self, capacity: int):
self.capacity = capacity
self.nodes = {} # key -> Node
# Dummy/sentinel nodes.
# head.next is the LRU unpinned node.
# tail.prev is the MRU unpinned node.
self.head = Node(-1, -1)
self.tail = Node(-1, -1)
self.head.next = self.tail
self.tail.prev = self.head
def _remove_from_lru(self, node: Node) -> None:
"""Remove an unpinned node from the linked list."""
prev_node = node.prev
next_node = node.next
prev_node.next = next_node
next_node.prev = prev_node
node.prev = None
node.next = None
def _add_as_mru(self, node: Node) -> None:
"""Append an unpinned node right before tail."""
last = self.tail.prev
last.next = node
node.prev = last
node.next = self.tail
self.tail.prev = node
def _touch_unpinned(self, node: Node) -> None:
"""Move an existing unpinned node to MRU."""
self._remove_from_lru(node)
self._add_as_mru(node)
def get(self, key: int) -> int:
node = self.nodes.get(key)
if node is None:
return -1
# Only unpinned keys participate in LRU order.
if not node.pinned:
self._touch_unpinned(node)
return node.value
def put(self, key: int, value: int) -> None:
node = self.nodes.get(key)
# Update existing key.
if node is not None:
node.value = value
if not node.pinned:
self._touch_unpinned(node)
return
# New key with zero capacity cannot