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 easy difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Citadel.

What role is this question designed for?

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

Implement LRU/LFU cache with custom eviction

Quick Overview

This question evaluates proficiency in cache design and data-structure implementation, focusing on eviction policies (LRU, LFU), metadata tracking for recency and frequency, and the ability to support an extensible eviction interface in the Coding & Algorithms domain.

Company: Citadel

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: easy

Interview Round: Technical Screen

You are asked to implement an in-memory key-value cache with a fixed capacity. When the cache is full and a new item must be inserted, an eviction policy decides which existing item to remove. ## Part A — LRU Cache Implement an **LRU (Least Recently Used)** cache supporting the operations below in **O(1)** average time: - `get(key) -> value | -1` : Return the value for `key` if present, otherwise `-1`. A successful `get` counts as a “use”. - `put(key, value) -> void` : Insert or update the key. A `put` of an existing key counts as a “use”. If insertion causes the cache to exceed `capacity`, evict the **least recently used** key. ## Part B — LFU Cache Implement an **LFU (Least Frequently Used)** cache supporting the same `get/put` operations. Eviction rules: - Evict the key with the **lowest access frequency**. - If multiple keys tie on frequency, evict the **least recently used among those tied keys**. - Target **O(1)** average time for `get/put`. ## Part C — Custom Eviction Function Extend the cache design so that eviction behavior can be customized. For example, the cache may be constructed with something like: - `evict_fn(keys, metadata) -> key_to_evict` Requirements: - The cache must still support `get/put`. - When full, it must call the provided eviction function (or policy object) to select a key to remove. - Clearly define what metadata is tracked (e.g., recency, frequency, timestamps) and how it is updated. ## Clarifications / Constraints - Keys are hashable (e.g., integers or strings) and values are arbitrary objects. - `capacity` is a positive integer. - If `capacity == 0`, all `put` operations store nothing and all `get` return `-1`. - State any additional assumptions you need.

Quick Answer: This question evaluates proficiency in cache design and data-structure implementation, focusing on eviction policies (LRU, LFU), metadata tracking for recency and frequency, and the ability to support an extensible eviction interface in the Coding & Algorithms domain.

Part 1: LRU Cache Simulator

Implement an LRU (Least Recently Used) cache simulator. You are given a cache capacity and a list of operations. Each operation is either `put k v` or `get k`. Return the results of all `get` operations in order. A successful `get` counts as a use, and `put` on an existing key also counts as a use, so that key becomes the most recently used. If inserting a new key would exceed capacity, evict the least recently used key. For this problem, keys and values are integers.

Constraints

0 <= capacity <= 100000
1 <= len(operations) <= 200000
0 <= k, v <= 10^9
If `capacity == 0`, all puts are ignored and every get returns -1.
Aim for O(1) average time per operation.

Examples

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

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

Explanation: After `get 1`, key 1 becomes most recent, so key 2 is evicted by `put 3 3`. Later, key 1 is the least recent and is evicted by `put 4 4`.

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 counts as a use, so key 2 becomes the least recently used and is evicted when key 3 is inserted.

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

Expected Output: [-1, 2]

Explanation: With capacity 1, inserting key 2 evicts key 1.

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

Expected Output: [-1, -1]

Explanation: A cache of size 0 never stores anything.

Hints

Use a hash map for key lookup and a structure that can move a key to the 'most recent' position in O(1).
When a key is read or updated, make it the most recently used item before continuing.

Part 2: LFU Cache Simulator

Implement an LFU (Least Frequently Used) cache simulator. You are given a cache capacity and a list of operations. Each operation is either `put k v` or `get k`. Return the results of all `get` operations in order. Eviction rules: remove the key with the lowest access frequency; if multiple keys tie, remove the least recently used among those tied keys. A successful `get` counts as an access, and `put` on an existing key also counts as an access. A newly inserted key starts with frequency 1.

Constraints

0 <= capacity <= 100000
1 <= len(operations) <= 200000
0 <= k, v <= 10^9
If `capacity == 0`, all puts are ignored and every get returns -1.
Target O(1) average time per operation.

Examples

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

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

Explanation: Key 2 is evicted first because it has lower frequency than key 1. Later, keys 1 and 3 tie on frequency, so the least recently used of them, key 1, is evicted.

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

Expected Output: [-1, 2, 3]

Explanation: Before inserting key 3, keys 1 and 2 both have frequency 1, so the older one, key 1, is evicted.

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

Expected Output: [-1, 20, 3]

Explanation: Updating key 2 increases its frequency, so key 1 becomes the LFU item and is evicted.

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

Expected Output: [-1]

Explanation: A cache of size 0 never stores anything.

Hints

You need two layers of organization: one map from key to its value/frequency, and another map from frequency to keys with that frequency.
Track the current minimum frequency so you can evict in O(1) average time.

Part 3: Configurable Eviction Cache

Implement a cache simulator with a customizable eviction policy. The cache tracks, for each key, three metadata fields: `freq`, `last_used`, and `created_at`. A successful `get` increments `freq` and updates `last_used`. A `put` on an existing key also increments `freq` and updates `last_used`. A new key starts with `freq = 1`, and both `created_at` and `last_used` equal the current logical time. When a new key must be inserted into a full cache, choose the key to evict by applying the provided ordered list of eviction rules. Each rule has the form `field order`, where `field` is one of `freq`, `last_used`, `created_at`, or `key`, and `order` is `asc` or `desc`. Compare rules lexicographically in the given order; if keys are still tied after all rules, evict the smaller key. Logical time increases by 1 for every operation processed.

Constraints

0 <= capacity <= 2000
1 <= len(eviction_rules) <= 4
1 <= len(operations) <= 10000
Supported fields are `freq`, `last_used`, `created_at`, and `key`.
0 <= k, v <= 10^9
If `capacity == 0`, all puts are ignored and every get returns -1.

Examples

Input: (2, ['last_used asc'], ['put 1 1', 'put 2 2', 'get 1', 'put 3 3', 'get 2', 'put 4 4', 'get 1', 'get 3', 'get 4'])

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

Explanation: Using only `last_used asc` makes the policy behave like LRU.

Input: (2, ['freq asc', 'last_used asc'], ['put 1 1', 'put 2 2', 'put 2 20', 'put 3 3', 'get 1', 'get 2', 'get 3'])

Expected Output: [-1, 20, 3]

Explanation: Using `freq asc` then `last_used asc` behaves like LFU with LRU tie-breaking, so key 1 is evicted.

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

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

Explanation: Using `created_at asc` behaves like FIFO. Even though key 1 was recently accessed, it is still the oldest inserted key and is evicted.

Input: (0, ['last_used asc'], ['put 1 1', 'get 1'])

Expected Output: [-1]

Explanation: A cache of size 0 never stores anything.

Hints

Keep cache data separate from metadata. Updating `freq`, `last_used`, and `created_at` consistently is the core of the problem.
Think of the rule list as building a lexicographic sort key for each cached key at eviction time.

Quick Overview