How should I practice LFU Cache with LRU Tie-Breaking?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Rippling phone screen and onsite interview problems in FastPrep.

Is LFU Cache with LRU Tie-Breaking associated with Rippling?

FastPrep tags this as a Rippling phone screen and onsite interview coding practice problem when the problem catalog has that company and stage context.

LFU Cache with LRU Tie-Breaking

Rippling● HardINTERNFULLTIMEPHONE SCREENONSITE INTERVIEW

Learn

Problem statement

Implement a least-frequently-used cache with positive capacity. Process operations in order:

[0, key, value] inserts or updates a key.
[1, key] reads a key and appends its value to the answer, or -1 if absent.

A newly inserted key has frequency 1. A successful read and an update of an existing key each increase its frequency by one and make it most recently used within the new frequency. A failed read changes nothing.

Before inserting a new key into a full cache, evict the key with the smallest frequency. If frequencies tie, evict the least recently used key among them. Return only the read results, in order. Each operation should take expected O(1) time.

Function

lfuCache(capacity: int, operations: int[][]) → int[]

Examples

Example 1

capacity = 2operations = [[0,7,70],[0,8,80],[1,7],[0,9,90],[1,8],[1,9]]return = [70,-1,90]

Reading key 7 raises its frequency. Inserting key 9 therefore evicts key 8, whose next read misses.

Example 2

capacity = 1operations = [[0,4,10],[0,4,20],[1,4],[0,5,30],[1,4],[1,5]]return = [20,-1,30]

Updating key 4 changes its value without using another slot. Capacity one still requires evicting it when key 5 arrives.

Constraints

1 <= capacity <= 1000.
0 <= operations.length <= 1000.
Every row has one of the two stated forms.
0 <= key <= 100000 and 0 <= value <= 10^9.