Design an O(1) eviction cache

Q: Design an O(1) eviction cache

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.

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 Palo Alto Networks.

Q: What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Palo Alto Networks during technical interviews.

Question

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

PracHub · Accepted Answer

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

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.

Quick Overview

Explanation

Hints

Quick Overview