Interview Prepcustom-data-structuresmediumAmazonFacebookGoogleMicrosoftBloomberg

LRU Cache

Choose your preparation mode4 modes available

Try It Solution Trace

Start learning this pattern below

Jump into concepts and practice - no test required

Recommended

Test this pattern10 questions across easy, medium, and hard to know if this pattern is strong

</>

IDE

class LRUCache:
    def __init__(self, capacity: int):
        pass
    def get(self, key: int) -> int:
        pass
    def put(self, key: int, value: int) -> None:
        pass

class LRUCache:
    def __init__(self, capacity: int):
        pass
    def get(self, key: int) -> int:
        pass
    def put(self, key: int, value: int) -> None:
        pass

public class LRUCache {
    public LRUCache(int capacity) {
    }
    public int get(int key) {
        return -1;
    }
    public void put(int key, int value) {
    }
}

class LRUCache {
public:
    LRUCache(int capacity) {
    }
    int get(int key) {
        return -1;
    }
    void put(int key, int value) {
    }
};

class LRUCache {
    constructor(capacity) {
    }
    get(key) {
        return -1;
    }
    put(key, value) {
    }
}

0/10

Common Bugs to Avoid

Wrong: get returns stale value or -1 incorrectly after put of existing keyput does not update value or usage order for existing keys✅ In put, if key exists, update value and move node to front of usage list

Wrong: Evicted wrong key after get operationget does not update usage order, so eviction removes wrong key✅ In get, move accessed node to front of usage list before returning value

Wrong: Cache size exceeds capacity or no eviction occursEviction logic missing or incorrect when capacity exceeded✅ Before inserting new key, remove tail node of usage list and delete from map if capacity reached

Wrong: TLE on large inputUsing list removal or linear scans in get/put causing O(n) per operation✅ Use doubly linked list with hash map to achieve O(1) get and put

✓

Test Cases

t1_01basic

Input

["LRUCache cache = new LRUCache(2);","cache.put(1, 1);","cache.put(2, 2);","cache.get(1);","cache.put(3, 3);","cache.get(2);","cache.put(4, 4);","cache.get(1);","cache.get(3);","cache.get(4);"]

Expected[null,null,null,1,null,-1,null,-1,3,4]

Cache capacity is 2. After putting keys 1 and 2, get(1) returns 1 and makes key 1 most recently used. Putting key 3 evicts key 2. get(2) returns -1 because key 2 was evicted. Putting key 4 evicts key 1. get(1) returns -1, get(3) returns 3, get(4) returns 4.

t1_02basic

Input

["LRUCache cache = new LRUCache(3);","cache.put(1, 10);","cache.put(2, 20);","cache.put(3, 30);","cache.get(2);","cache.put(4, 40);","cache.get(1);","cache.get(3);","cache.get(4);"]

Expected[null,null,null,null,20,null,-1,30,40]

Capacity 3 cache stores keys 1,2,3. get(2) returns 20 and makes key 2 most recently used. put(4,40) evicts least recently used key 1. get(1) returns -1, get(3) returns 30, get(4) returns 40.

Practice

(1/5)

1. Given the following code snippet for the optimal UndergroundSystem implementation, what is the value of travel_time when checkOut(1, "Leyton", 20) is called after checkIn(1, "Paradise", 3) and checkIn(2, "Leyton", 10)?

class Node:
    def __init__(self, id, station, time):
        self.id = id
        self.station = station
        self.time = time
        self.next = None

class UndergroundSystem:
    def __init__(self):
        self.head = None
        self.route_data = {}

    def checkIn(self, id: int, stationName: str, t: int) -> None:
        new_node = Node(id, stationName, t)
        new_node.next = self.head
        self.head = new_node

    def checkOut(self, id: int, stationName: str, t: int) -> None:
        prev = None
        curr = self.head
        while curr:
            if curr.id == id:
                travel_time = t - curr.time
                route = (curr.station, stationName)
                if route not in self.route_data:
                    self.route_data[route] = [0, 0]
                self.route_data[route][0] += travel_time
                self.route_data[route][1] += 1
                if prev:
                    prev.next = curr.next
                else:
                    self.head = curr.next
                return
            prev = curr
            curr = curr.next

easy

A. 10

B. 17

C. 7

D. 20

3. The following code attempts to copy a linked list with random pointers using the optimal weaving approach. Identify the line that contains a subtle bug that can cause incorrect random pointer assignment or list corruption.

def copyRandomList(head):
    if not head:
        return None
    curr = head
    # Step 1: Insert copied nodes
    while curr:
        new_node = Node(curr.val, curr.next)
        curr.next = new_node
        curr = new_node.next
    # Step 2: Assign random pointers
    curr = head
    while curr:
        if curr.random:
            curr.next.random = curr.random  # Bug here
        curr = curr.next.next
    # Step 3: Separate lists
    curr = head
    copy_head = head.next
    copy_curr = copy_head
    while curr:
        curr.next = curr.next.next
        if copy_curr.next:
            copy_curr.next = copy_curr.next.next
        curr = curr.next
        copy_curr = copy_curr.next
    return copy_head

medium

A. Line assigning curr.next.random = curr.random

B. Line inserting copied nodes: curr.next = new_node

C. Line advancing curr in Step 1: curr = new_node.next

D. Line separating original and copied lists: curr.next = curr.next.next

LRU Cache

Start learning this pattern below

Practice

Solution

Step 1: Trace checkIn calls

Step 2: Trace checkOut(1, "Leyton", 20)

Final Answer:

Quick Check:

Solution

Step 1: Understand the problem requirements

Step 2: Evaluate approaches

Final Answer:

Quick Check:

Solution

Step 1: Analyze random pointer assignment

Step 2: Correct assignment

Final Answer:

Quick Check:

Solution

Step 1: Identify linked list traversal

Step 2: Analyze route data update

Final Answer:

Quick Check:

Solution

Step 1: Analyze addNum complexity

Step 2: Analyze findMedian complexity

Final Answer:

Quick Check: