Design an O(1) eviction cache
Company: Palo Alto Networks
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Onsite
Implement an in-memory key–value cache with fixed capacity that evicts the least recently used entry when full. Support get(key) -> value or -1 if missing, and put(key, value) to insert or update. Both operations must be average O(
1). Describe your data structures, sketch them on a whiteboard, and perform a dry run on the sequence: put(1,
10), put(2,
20), get
(
1), put(3,
30), get
(
2), put(4,
40), get
(
1), get
(
3), get
(
4). Explain time/space complexity and how you would handle edge cases (capacity=0, updates, frequent accesses).
Quick Answer: This question evaluates data structure and algorithmic design skills within the Coding & Algorithms domain, focusing on cache eviction policies and techniques for achieving average O(1) get/put operations. It is commonly asked to test reasoning about time and space complexity, handling of capacity and edge cases, and demonstrates a blend of conceptual understanding and practical application.
Implement a fixed-capacity least-recently-used (LRU) cache simulator. Given an integer capacity and a list of operations, process each operation in order. Supported operations are: ["get", key] which returns the value associated with key if present, otherwise -1, and marks the key as most recently used; and ["put", key, value] which inserts or updates the key with value and marks it most recently used. If inserting into a full cache, evict the least recently used key. Return a list of outputs for the get operations in the order they occur. Both operations must run in average O(1) time. If capacity is 0, puts have no effect and all gets return -1.
Constraints
- 0 <= capacity <= 100000
- 0 <= len(ops) <= 200000
- Each op is either ["put", key, value] or ["get", key]
- Keys and values are 32-bit signed integers (e.g., -1e9 <= key,value <= 1e9)
- Average O(1) time for get and put
- Updates to existing keys must refresh recency
Solution
def lru_process(capacity: int, ops: list) -> list:
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, cap: int):
self.cap = max(0, 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_front(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, n = node.prev, 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_front(node)
def _pop_tail(self) -> Node:
if self.tail.prev is self.head:
return None
node = self.tail.prev
self._remove(node)
return node
def get(self, key: int) -> int:
if self.cap == 0:
return -1
node = self.map.get(key)
if node is None:
return -1
self._move_to_front(node)
return node.value
def put(self, key: int, value: int) -> None:
if self.cap == 0:
return
node = self.map.get(key)
if node is not None:
node.value = value
self._move_to_front(node)
return
node = Node(key, value)
self.map[key] = node
self._add_front(node)
if len(self.map) > self.cap:
evicted = self._pop_tail()
if evicted is not None:
del self.map[evicted.key]
cache = LRUCache(capacity)
out = []
for op in ops:
if not op:
continue
cmd = op[0]
if cmd == "get":
key = op[1]
out.append(cache.get(key))
elif cmd == "put":
key, value = op[1], op[2]
cache.put(key, value)
else:
# Unknown operation; ignore
pass
return out
Explanation
Maintain a hash map from key to node and a doubly linked list to track recency. The list head represents the most recently used (MRU) position and the tail the least recently used (LRU). On get, if the key exists, move its node to the head and return its value; otherwise return -1. On put, if the key exists, update its value and move it to the head; if it is new, insert a node at the head and, if the size exceeds capacity, remove the tail node and delete it from the map. Using a hash map gives O(1) access by key, and constant-time node operations on the doubly linked list maintain recency in O(1). For capacity=0, puts do nothing and gets always return -1.
Time complexity: O(1) per operation on average; O(m) total for m operations. Space complexity: O(capacity).
Hints
- Use a hash map from key to a node in a doubly linked list to achieve O(1) access and updates.
- Maintain a doubly linked list ordered by recency: most recent at the head, least recent at the tail.
- On get: if found, move the node to the head before returning its value.
- On put: if key exists, update value and move to head; else insert a new node at head. If size exceeds capacity, remove the tail node and delete it from the map.
- Sentinel head/tail nodes simplify insert/remove operations. Handle capacity=0 as a special case.