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 medium 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 with O(1) operations | Salesforce Coding Question

Quick Overview

This question evaluates a candidate's ability to design and implement efficient data structures for caching, including understanding frequency-based eviction policies, maintaining recency ordering for tie-breaking, and meeting strict time-complexity guarantees.

Implement an LFU cache with O(1) operations

Company: Salesforce

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

Design and implement an **LFU (Least Frequently Used) cache**. The cache supports: - `get(key)`: return the value for `key` if present, else return `-1`. - `put(key, value)`: insert or update the key with `value`. Rules: 1. When the cache reaches capacity, it should evict the entry with the **lowest access frequency**. 2. If multiple entries share the same lowest frequency, evict the **least recently used** among them. 3. A successful `get` increments that key’s frequency. 4. A `put` on an existing key updates the value and increments frequency. 5. If capacity is `0`, all operations should be no-ops and `get` always returns `-1`. ### Performance requirement - `get` and `put` should run in **amortized O(1)** time. ### Input/Output style (for interview) You may be given a sequence of operations and must output results of `get` operations.

Quick Answer: This question evaluates a candidate's ability to design and implement efficient data structures for caching, including understanding frequency-based eviction policies, maintaining recency ordering for tie-breaking, and meeting strict time-complexity guarantees.

Design and implement an LFU (Least Frequently Used) cache. You are given a cache capacity and a sequence of operations. Each operation is represented as a string in one of these forms: - "put key value" - "get key" Process the operations in order and return a list containing the results of every `get` operation. Rules: 1. If a key exists, `get(key)` returns its value and increases its access frequency by 1. 2. If a key does not exist, `get(key)` returns `-1`. 3. `put(key, value)` inserts a new key or updates an existing key. 4. If `put` updates an existing key, that also increases its frequency by 1. 5. When the cache is full and a new key must be inserted, evict the key with the lowest frequency. 6. If multiple keys have the same lowest frequency, evict the least recently used among them. 7. If capacity is 0, all `put` operations do nothing and every `get` returns `-1`. Your implementation should achieve amortized O(1) time for both `get` and `put`.

Constraints

0 <= capacity <= 10^5
0 <= len(operations) <= 2 * 10^5
Each operation is either "put key value" or "get key"
-10^9 <= key, value <= 10^9

Examples

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

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

Explanation: After `get 1`, key 1 has frequency 2 while key 2 has frequency 1. Inserting key 3 evicts key 2. The later gets return -1, 3, and 1.

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

Expected Output: [-1, 20, 30]

Explanation: Keys 1 and 2 both have frequency 1 when key 3 is inserted, so the least recently used among them, key 1, is evicted.

Input: (2, ["put 1 10", "put 2 20", "put 1 15", "put 3 30", "get 1", "get 2", "get 3"])

Expected Output: [15, -1, 30]

Explanation: Updating key 1 changes its value to 15 and increases its frequency. When key 3 is inserted, key 2 is evicted because it has the lower frequency.

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

Expected Output: [-1, -1]

Explanation: With capacity 0, nothing can be stored, so every get returns -1.

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

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

Explanation: Before inserting key 4, key 3 is the only key with frequency 1, so it is evicted. The remaining gets reflect the updated values and frequencies.

Hints

Use one hash map to store each key's current value and frequency.
To break ties by recency in O(1), keep an ordered structure for each frequency and track the current minimum frequency.

Quick Overview