How should I practice LRU Cache?

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

Is LRU Cache associated with Salesforce?

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

Problem · Hash Table

LRU Cache

Learn this problem

● Medium

SalesforceFULLTIMEONSITE INTERVIEW

See Salesforce hiring insights

Problem statement

Process operations on a least recently used cache with fixed positive capacity. The cache starts empty.

put has arguments [key, value]. Insert or update the key and make it most recently used. If a new key makes the cache exceed capacity, evict the least recently used key. A put produces no result.
get has arguments [key]. Return its value and make the key most recently used, or return -1 when the key is absent.

Return the results of all get operations in operation order.

Function

runLruCache(capacity: int, operations: String[], arguments: int[][]) → int[]

Examples

Example 1

capacity = 2operations = ["put","put","get","put","get","get"]arguments = [[1,1],[2,2],[1],[3,3],[2],[3]]return = [1,-1,3]

Reading key 1 makes it recent. Inserting key 3 then evicts key 2.

Example 2

capacity = 1operations = ["put","put","get","put","get"]arguments = [[5,10],[5,20],[5],[6,30],[5]]return = [20,-1]

Updating key 5 changes its value without eviction. Inserting key 6 later evicts key 5.

Example 3

capacity = 2operations = ["get","put","get","get"]arguments = [[7],[7,70],[7],[7]]return = [-1,70,70]

The first read misses. After insertion, repeated successful reads return 70 and preserve recency.

Constraints

1 <= capacity <= 10^5
1 <= operations.length = arguments.length <= 2 * 10^5
Each operation is exactly get or put.
A get row has one integer; a put row has two integers.
0 <= key, value <= 10^9
Every operation must run in average O(1) time.