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.

What difficulty level is this coding question?

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

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Affirm during technical interviews.

Implement an LRU cache | Affirm Coding Question

Q: Implement an LRU cache

This question evaluates a candidate's ability to design and implement efficient cache eviction policies while managing time and space complexity guarantees for mutable key-value stores.

Implement an LRU cache

Company: Affirm

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: easy

Interview Round: Onsite

## Problem Design and implement an **LRU (Least Recently Used) cache** that supports the following operations in **average O(1)** time: - `get(key) -> value`: Return the value associated with `key` if it exists in the cache; otherwise return `-1`. Accessing a key makes it **most recently used**. - `put(key, value)`: Insert or update the value for `key`. If inserting causes the number of keys to exceed the cache `capacity`, evict the **least recently used** key. ## Input/Output You will implement a class (or module) with: - Constructor: `LRUCache(capacity)` - Methods: `get(key)` and `put(key, value)` ## Constraints (typical) - `1 <= capacity <= 10^5` - Keys and values are integers (or comparable scalar types) - Must achieve **O(1)** average time for both operations and **O(capacity)** space ## Notes - “Most recently used” means most recently accessed via `get` or updated via `put`. - Updating an existing key counts as a recent use.

Quick Answer: This question evaluates a candidate's ability to design and implement efficient cache eviction policies while managing time and space complexity guarantees for mutable key-value stores.

Design an LRU (Least Recently Used) cache that supports get and put in average O(1) time. In this function-based version, you are given the cache capacity and a sequence of operations to execute. A get operation returns the value for a key if present, otherwise -1, and makes that key the most recently used. A put operation inserts or updates a key-value pair, and updating an existing key also makes it the most recently used. If inserting a new key causes the cache to exceed capacity, evict the least recently used key.

Constraints

1 <= capacity <= 10^5
0 <= len(operations) <= 2 * 10^5
operations[i] is either [0, key] or [1, key, value]
-10^9 <= key, value <= 10^9
Both get and put must run in average O(1) time

Examples

Input: (2, [[1,1,1], [1,2,2], [0,1], [1,3,3], [0,2], [1,4,4], [0,1], [0,3], [0,4]])

Expected Output: [1, -1, -1, 3, 4]

Explanation: After get(1), key 1 becomes most recent. put(3,3) evicts key 2. Later put(4,4) evicts key 1. The get results are 1, -1, -1, 3, and 4.

Input: (2, [[1,1,1], [1,2,2], [1,1,10], [0,1], [1,3,3], [0,2], [0,1], [0,3]])

Expected Output: [10, -1, 10, 3]

Explanation: Updating key 1 changes its value to 10 and makes it most recent. When key 3 is inserted, key 2 is least recently used and is evicted.

Input: (1, [[1,5,5], [0,5], [1,6,6], [0,5], [0,6], [1,6,60], [0,6]])

Expected Output: [5, -1, 6, 60]

Explanation: With capacity 1, inserting key 6 evicts key 5. Updating key 6 changes its value from 6 to 60.

Input: (3, [])

Expected Output: []

Explanation: There are no operations, so there are no get results.

Input: (3, [[1,1,1], [1,2,2], [1,3,3], [0,1], [0,2], [1,4,4], [0,3], [0,1], [0,2], [0,4]])

Expected Output: [1, 2, -1, 1, 2, 4]

Explanation: get(1) and get(2) update recency, making key 3 the least recently used. Therefore put(4,4) evicts key 3.

Input: (2, [[1,-1,-10], [1,2,20], [0,-1], [1,3,30], [0,2], [0,-1], [0,3]])

Expected Output: [-10, -1, -10, 30]

Explanation: Negative keys and values are supported. Accessing key -1 makes it recent, so inserting key 3 evicts key 2.

Solution

def solution(capacity, operations):
    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

    if capacity <= 0:
        return [-1 for op in operations if op[0] == 0]

    cache = {}

    # Dummy sentinels: head.next is most recently used, tail.prev is least recently used.
    head = Node()
    tail = Node()
    head.next = tail
    tail.prev = head

    def remove(node):
        before = node.prev
        after = node.next
        before.next = after
        after.prev = before

    def insert_at_front(node):
        first = head.next
        node.prev = head
        node.next = first
        head.next = node
        first.prev = node

    def move_to_front(node):
        remove(node)
        insert_at_front(node)

    def evict_lru():
        lru = tail.prev
        if lru is head:
            return
        remove(lru)
        del cache[lru.key]

    result = []

    for op in operations:
        if op[0] == 0:
            key = op[1]
            node = cache.get(key)
            if node is None:
                result.append(-1)
            else:
                move_to_front(node)
                result.append(node.value)
        else:
            key = op[1]
            value = op[2]
            node = cache.get(key)

            if node is not None:
                node.value = value
                move_to_front(node)
            else:
                if len(cache) >= capacity:
                    evict_lru()
                new_node = Node(key, value)
                cache[key] = new_node
                insert_at_front(new_node)

    return result

Time complexity: O(n), where n is the number of operations. Each get and put runs in average O(1) time.. Space complexity: O(capacity).

Hints

Use a hash map to find cache entries by key in O(1) average time.
Use a doubly linked list to track recency: move accessed or updated nodes to the front, and evict from the back.

Quick Overview

This question evaluates a candidate's ability to design and implement efficient cache eviction policies while managing time and space complexity guarantees for mutable key-value stores.