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 Technical Screen rounds at Cisco.

What role is this question designed for?

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

Implement an LFU Cache | Cisco Coding Question

Implement an LFU Cache

Company: Cisco

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Technical Screen

Design and implement a Least Frequently Used cache. The cache has a fixed positive capacity and supports the following operations: - `get(key)`: Return the value associated with `key` if it exists in the cache; otherwise return `-1`. Accessing a key increases its usage frequency by `1`. - `put(key, value)`: Insert or update the value for `key`. If the key already exists, update its value and increase its usage frequency by `1`. If the key does not exist and the cache is full, evict one key before inserting the new key. Eviction rules: 1. Evict the key with the lowest usage frequency. 2. If multiple keys have the same lowest frequency, evict the least recently used key among them. Requirements: - Both `get` and `put` should run in average `O(1)` time. - You may assume keys and values are integers. - If the capacity is `0`, `put` should do nothing and `get` should always return `-1`. Define a class with constructor `LFUCache(capacity)`, method `get(key)`, and method `put(key, value)`.

Quick Answer: This question evaluates understanding of algorithmic design and data structure management for cache eviction policies, focusing on frequency- and recency-based bookkeeping and meeting average O(1) time constraints.

Design and implement a Least Frequently Used (LFU) cache with Least Recently Used (LRU) tie-breaking. The cache has a fixed capacity and supports these operations: - `get(key)`: Return the value for `key` if it exists, otherwise return `-1`. A successful `get` increases that key's frequency by 1. - `put(key, value)`: Insert or update a key. If the key already exists, update its value and increase its frequency by 1. If the key does not exist and the cache is full, evict one key first. Eviction rules: 1. Evict the key with the lowest frequency. 2. If multiple keys share the same lowest frequency, evict the least recently used among them. A newly inserted key starts with frequency 1. For automated testing, implement a function `solution(operations, arguments)` that simulates one `LFUCache` instance: - `operations[0]` will always be `"LFUCache"` and `arguments[0]` will be `[capacity]`. - Each later operation is either `"put"` or `"get"`. - Return a list of results aligned with the operations list: - `None` for `LFUCache` and `put` - the returned integer for `get` Your goal is to make both `get` and `put` run in average `O(1)` time.

Constraints

1 <= len(operations) == len(arguments) <= 200000
operations[0] == "LFUCache" and arguments[0] has exactly 1 integer
For i > 0, operations[i] is either "put" or "get"
0 <= capacity <= 100000
-10^9 <= key, value <= 10^9
Average time complexity of both get and put should be O(1)

Examples

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

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

Explanation: After `get(1)`, key 1 has frequency 2 while key 2 has frequency 1. Inserting key 3 evicts key 2.

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

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

Explanation: Before inserting key 3, keys 1 and 2 both have frequency 1. Key 1 is less recent, so it is evicted.

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

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

Explanation: Updating key 2 increases its frequency, so key 1 remains the least frequently used and is evicted when key 3 is inserted.

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

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

Explanation: With capacity 0, every put is ignored and every get returns -1.

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

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

Explanation: After `get(1)` and `get(2)`, both keys have frequency 2. Key 1 became frequency-2 earlier, so it is the LRU among that frequency and gets evicted.

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

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

Explanation: Negative keys and values are valid. With capacity 1, inserting key -2 evicts key -1.

Hints

You need one structure to find a key's current value and frequency quickly, and another structure to find the least frequently used key quickly.
Within each frequency bucket, you still need LRU behavior. Think about combining a hash map with an ordered structure per frequency.

Quick Overview

This question evaluates understanding of algorithmic design and data structure management for cache eviction policies, focusing on frequency- and recency-based bookkeeping and meeting average O(1) time constraints.