Interview Prepchallenge-problemshardAmazonGoogleFacebook

LFU Cache

Choose your preparation mode4 modes available

Try It Solution Trace

📋

Problem

Imagine designing a caching system for a high-traffic website where you want to keep the most frequently accessed items readily available to minimize latency and server load.

Design and implement a data structure for Least Frequently Used (LFU) cache. It should support the following operations: get(key) and put(key, value). get(key) - Get the value of the key if it exists in the cache, otherwise return -1. put(key, value) - Update or insert the value if the key is not already present. When the cache reaches its capacity, it should invalidate and remove the least frequently used key before inserting a new item. If there is a tie in frequency, the least recently used key should be evicted.

0 ≤ capacity ≤ 10^50 ≤ key, value ≤ 10^9At most 2 * 10^5 calls will be made to get and put.

Edge cases: capacity = 0 → all puts should not store anything, all gets return -1put with existing key → should update value and frequencymultiple keys with same frequency → evict least recently used among them

</>

IDE

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

class LFUCache:
    def __init__(self, capacity: int):
        # Write your solution here
        pass
    def get(self, key: int) -> int:
        pass
    def put(self, key: int, value: int) -> None:
        pass

public class LFUCache {
    public LFUCache(int capacity) {
        // Write your solution here
    }
    public int get(int key) {
        return -1;
    }
    public void put(int key, int value) {
        // Write your solution here
    }
}

class LFUCache {
public:
    LFUCache(int capacity) {
        // Write your solution here
    }
    int get(int key) {
        return -1;
    }
    void put(int key, int value) {
        // Write your solution here
    }
};

class LFUCache {
    constructor(capacity) {
        // Write your solution here
    }
    get(key) {
        return -1;
    }
    put(key, value) {
        // Write your solution here
    }
}

0/9

Common Bugs to Avoid

Wrong: Evicts wrong key when multiple keys have same frequencyEviction logic ignores recency tie-break and evicts any LFU key arbitrarily✅ Maintain recency order within each frequency bucket using a linked list and evict the least recently used key among LFU keys

Wrong: get returns outdated value after put updates existing keyput does not update value or frequency for existing keys✅ In put, if key exists, update its value and increment frequency and recency accordingly

Wrong: Cache stores items despite zero capacity, get returns values instead of -1No explicit check for zero capacity in put and get✅ Return immediately in put if capacity == 0 and always return -1 in get if capacity == 0

Wrong: Solution times out on large inputEviction implemented by scanning all keys or sorting on each put✅ Use frequency buckets and doubly linked lists to achieve O(1) average time per operation

Wrong: Frequency updates off by one causing wrong eviction or get resultsFrequency increment logic is incorrect or missing on get or put✅ Increment frequency exactly once per get or put for existing keys

✓

Test Cases

t1_01basic

Input

{"capacity":2,"operations":["put","put","get","put","get","get","put","get","get","get"],"arguments":[[1,1],[2,2],[1],[3,3],[2],[3],[4,4],[1],[3],[4]]}

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

Initially cache is empty. After put(1,1) and put(2,2), cache has keys 1 and 2 with frequency 1. get(1) returns 1 and increases frequency of key 1 to 2. put(3,3) evicts key 2 because it has frequency 1 which is least. get(2) returns -1 because key 2 was evicted. get(3) returns 3 and increases frequency of key 3 to 2. put(4,4) evicts key 1 because keys 1 and 3 have frequency 2 but key 1 is least recently used. get(1) returns -1. get(3) returns 3. get(4) returns 4.

t1_02basic

Input

{"capacity":3,"operations":["put","put","put","get","put","get","get","get"],"arguments":[[2,2],[1,1],[3,3],[2],[4,4],[1],[3],[4]]}

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

Cache capacity 3. After put(2,2), put(1,1), put(3,3), all keys have freq=1. get(2) returns 2 and freq(2)=2. put(4,4) evicts key 1 (freq=1, least recently used among freq=1). get(1) returns -1 (evicted). get(3) returns 3 freq=2. get(4) returns 4 freq=2.

Practice

(1/5)

1. You need to design a system that tracks passengers checking in and out of stations, and efficiently calculates average travel times between stations. Which approach best balances time and space efficiency for frequent queries?

easy

A. Use hash maps to store running totals of travel times and counts per route.

B. Store all trips explicitly and scan them to compute averages on demand.

C. Use dynamic programming to precompute all possible route averages.

D. Use a priority queue to keep track of the shortest travel times per route.

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

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

LFU Cache

Practice

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: Understand skiplist structure

Step 2: Analyze average operation cost

Final Answer:

Quick Check:

Solution

Step 1: Understand cycle implications

Step 2: Identify safe approach

Final Answer:

Quick Check:

Solution

Step 1: Understand impact of negative heights

Step 2: Modify merge logic accordingly

Step 3: Evaluate other options

Final Answer:

Quick Check:

Ready to prove it?