Interview Prepcustom-data-structuresmediumAmazonFacebookGoogleMicrosoftBloomberg

LRU Cache

Choose your preparation mode4 modes available

Try It Solution Trace

</>

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. You need to design a data structure that supports incrementing and decrementing string keys, and retrieving a key with the maximum or minimum count, all in constant time. Which approach best guarantees O(1) time complexity for all these operations?

easy

A. Using a balanced binary search tree keyed by counts to maintain order of keys

B. Using a hash map to store counts and scanning all keys to find max/min when requested

C. Maintaining a doubly linked list of buckets, each bucket holding keys with the same count, plus hash maps for quick access

D. Using a priority queue to track max and min keys with lazy updates

2. Consider the following Python code implementing the optimal CustomStack with lazy increments. After executing the sequence of operations below, what is the output of the last pop() call?

cs = CustomStack(3)
cs.push(1)
cs.push(2)
cs.increment(2, 5)
print(cs.pop())

easy

A. 2

B. 7

C. 6

D. 1

5. Given the following code snippet for SnapshotArray, what is the output of snapshotArr.get(0, 0) after executing all lines shown?

snapshotArr = SnapshotArray(3)
snapshotArr.set(0, 5)
snap_id = snapshotArr.snap()
snapshotArr.set(0, 6)
print(snapshotArr.get(0, 0))

easy

A. 5

B. 6

C. 0

D. Error due to invalid snap_id

Recommended

Ready to prove it?

Pass the test and this pattern moves unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard

LRU Cache

Practice

Solution

Step 1: Understand operation requirements

Step 2: Evaluate approaches

Final Answer:

Quick Check:

Solution

Step 1: Trace the increment operation

Step 2: Trace the pop operation

Final Answer:

Quick Check:

Solution

Step 1: Trace outer loop from highest to lowest level

Step 2: Move curr to forward[0]

Final Answer:

Quick Check:

Solution

Step 1: Insert 1

Step 2: Insert 5

Step 3: Insert 3

Step 4: Find median

Step 5: Re-examine median calculation

Final Answer:

Quick Check:

Solution

Step 1: Trace set and snap operations

Step 2: Trace get(0,0)

Final Answer:

Quick Check:

Ready to prove it?