How should I practice Weighted LRU Cache?

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

Is Weighted LRU Cache associated with xAI?

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

Problem · Hash Table

Weighted LRU Cache

Learn this problem

● Medium

xAIFULLTIMEONSITE INTERVIEW

Problem statement

Process operations against an initially empty cache with total weight capacity capacity.

["PUT", key, value, weight] inserts or replaces an item and makes it most recently used.
["GET", key] returns the value and makes a present item most recently used; a miss returns NULL.

After every PUT, while the sum of resident item weights exceeds capacity, evict the least recently used item. Replacing a key removes its previous weight before adding the new item. A single insertion may therefore evict multiple items.

Return the outputs of GET operations in order.

Function

weightedLru(capacity: int, operations: String[][]) → String[]

Examples

Example 1

capacity = 5operations = [["PUT","a","A","3"],["PUT","b","B","2"],["GET","a"],["PUT","c","C","4"],["GET","a"],["GET","c"]]return = ["A","NULL","C"]

The hit on a makes b least recent. Adding weight-4 c first evicts b, then still exceeds capacity and evicts a.

Example 2

capacity = 5operations = [["PUT","a","old","2"],["PUT","b","B","3"],["PUT","a","new","1"],["PUT","c","C","2"],["GET","b"],["GET","a"],["GET","c"]]return = ["NULL","new","C"]

Replacing a changes its weight from 2 to 1 and refreshes its recency. Adding c then evicts b.

Constraints

1 <= capacity <= 10^9.
1 <= operations.length <= 200000.
Each weight is an integer in [1, capacity].
Keys and values are non-empty ASCII strings; values are never NULL.
The sum of all operation-string lengths is at most 2000000.