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 hard difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Salesforce.

What role is this question designed for?

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

Implement an LFU cache | Salesforce Coding Question

Implement an LFU cache

Company: Salesforce

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Onsite

## Problem: LFU Cache Design and implement a **Least Frequently Used (LFU) cache** with a fixed capacity. The cache supports the following operations: - `get(key) -> value` - Return the value of `key` if it exists in the cache. - Otherwise return `-1`. - If the key exists, its **usage frequency** increases by 1. - `put(key, value) -> void` - Insert or update the value of `key`. - If the cache reaches capacity, it must evict one key before inserting. ### Eviction Policy 1. Evict the key with the **lowest frequency** (LFU). 2. If multiple keys have the same (lowest) frequency, evict the **least recently used** (LRU) among them. ### Requirements / Constraints - Capacity is a non-negative integer. - Aim for **O(1)** average time per operation. - If `capacity == 0`, `put` does nothing and `get` always returns `-1`. ### Example If capacity = 2: - `put(1, 1)` - `put(2, 2)` - `get(1)` returns `1` (freq(1)=2) - `put(3, 3)` evicts key `2` (freq(2)=1 is lowest) - `get(2)` returns `-1` - `get(3)` returns `3`

Quick Answer: This question evaluates understanding of data structures and cache eviction policies, specifically frequency tracking for LFU caches and LRU tie-breaking among equal-frequency items.

Design and implement a **Least Frequently Used (LFU) cache** with a fixed capacity. The cache supports two operations: - `get(key)` — return the value of `key` if present, else `-1`. A successful `get` increases the key's usage frequency by 1. - `put(key, value)` — insert or update the value of `key`. If the cache is at capacity, evict one key *before* inserting. **Eviction policy:** evict the key with the **lowest frequency**; if several keys tie for the lowest frequency, evict the **least recently used** among them. Aim for **O(1)** average time per operation. If `capacity == 0`, `put` does nothing and `get` always returns `-1`. **Executable format (for this console):** because an LFU cache is stateful, you implement a single function that *replays a command sequence*. You are given two parallel lists, `operations` (e.g. `"LFUCache"`, `"put"`, `"get"`) and `arguments` (the args for each op). Return a list with one entry per operation: `None` for the constructor and for `put`, and the returned value (or `-1`) for each `get`. **Example** (capacity = 2): ``` operations = ["LFUCache", "put", "put", "get", "put", "get", "get"] arguments = [[2], [1,1], [2,2], [1], [3,3], [2], [3]] -> [None, None, None, 1, None, -1, 3] ``` After `get(1)`, key 1 has frequency 2 and key 2 has frequency 1, so `put(3,3)` evicts key 2 (lowest frequency). Hence `get(2) == -1` and `get(3) == 3`.

Constraints

0 <= capacity
0 <= key, value (keys/values are non-negative integers in the tests)
Total number of get/put operations fits comfortably in memory (designed for O(1)/op)
If capacity == 0: put is a no-op and get always returns -1

Examples

Input: (["LFUCache", "put", "put", "get", "put", "get", "get", "put", "get", "get", "get"], [[2], [1, 1], [2, 2], [1], [3, 3], [2], [3], [4, 4], [1], [3], [4]])

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

Explanation: Canonical LeetCode trace, capacity 2. get(1) makes freq(1)=2, so put(3,3) evicts key 2 (freq 1). Later put(4,4) must evict among the lowest frequency: keys 1 and 3 both have freq 1 after the previous step's gets, key 1 is least recently used, so key 1 is evicted -> get(1)=-1, get(3)=3, get(4)=4.

Input: (["LFUCache", "put", "get"], [[0], [0, 0], [0]])

Expected Output: [None, None, -1]

Explanation: Capacity 0 edge case: put does nothing and get always returns -1.

Input: (["LFUCache", "put", "put", "get", "get"], [[2], [1, 10], [2, 20], [1], [2]])

Expected Output: [None, None, None, 10, 20]

Explanation: Both keys fit in capacity 2, so both gets return their stored values; no eviction occurs.

Input: (["LFUCache", "put", "put", "put", "get", "get"], [[2], [1, 1], [2, 2], [3, 3], [1], [3]])

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

Explanation: Keys 1 and 2 both have freq 1; inserting key 3 evicts the least-recently-used among them (key 1). So get(1)=-1, get(3)=3.

Input: (["LFUCache", "put", "put", "get"], [[1], [1, 1], [2, 2], [1]])

Expected Output: [None, None, None, -1]

Explanation: Capacity 1: putting key 2 evicts key 1 (the only resident), so get(1) returns -1.

Input: (["LFUCache", "put", "put", "put", "get", "get", "get"], [[3], [1, 1], [2, 2], [1, 100], [1], [2], [1]])

Expected Output: [None, None, None, None, 100, 2, 100]

Explanation: put(1,100) updates key 1's value and bumps its frequency. With capacity 3 nothing is evicted; get(1) returns the updated 100, get(2) returns 2.

Hints

Maintain three maps: key -> value, key -> frequency, and frequency -> an ordered collection of keys at that frequency (insertion order = recency).
Track min_freq so eviction is O(1): evict the least-recently-used key in the freq_to_keys[min_freq] bucket.
On a successful get (or an update via put), move the key from its current frequency bucket to the next; if you emptied the min_freq bucket, increment min_freq.
When inserting a brand-new key, its frequency is 1, so set min_freq = 1 after inserting.

Quick Overview

This question evaluates understanding of data structures and cache eviction policies, specifically frequency tracking for LFU caches and LRU tie-breaking among equal-frequency items.