How should I practice Tiered Expiring Item Store?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Akuna Capital phone screen problems in FastPrep.

Is Tiered Expiring Item Store associated with Akuna Capital?

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

Problem · Design

Tiered Expiring Item Store

Learn this problem

● Hard

Akuna CapitalFULLTIMEPHONE SCREEN

Problem statement

You manage a tiered item store whose levels are ordered from top to bottom. Level i has the fixed positive capacity levelCapacities[i].

Implement processTieredStore to process operations in order and return one string result for every operation.

Operations

STORE itemId weight expiresAt: If itemId is already stored, return "false". Otherwise, place the item in the first top-to-bottom level with a free slot and return "true". If every level is full, return "false".
RETRIEVE now:
1. Remove every stored item whose expiresAt is less than or equal to now.
2. Scan the levels from top to bottom. A level is eligible when it is nonempty and its number of free slots is at least half of its capacity. Equivalently, 2 * freeSlots >= capacity.
3. From the first eligible level, remove and return the ID of its heaviest live item. If several items have the same maximum weight, choose the lexicographically smallest ID.
4. If no level is eligible, return "null".

State Rules

A STORE operation does not purge expired items because it has no current-time argument.
An item ID remains unavailable while that item is stored, even if its expiration time has passed but no RETRIEVE operation has purged it.
An ID may be stored again after its prior item is retrieved or purged as expired.
Every operation contributes exactly one entry to the returned array.

Function

processTieredStore(levelCapacities: int[], operations: String[]) → String[]

Examples

Example 1

levelCapacities = [4,2]operations = ["STORE a 5 5","STORE b 9 5","STORE c 7 20","STORE d 6 20","STORE e 10 20","RETRIEVE 5","RETRIEVE 5","RETRIEVE 5"]return = ["true","true","true","true","true","c","d","e"]

At time 5, items a and b expire. The top level then has two free slots out of four, so it is eligible exactly at the half-capacity boundary. It returns c, then d. Once that level is empty, the lower level returns e.

Example 2

levelCapacities = [2]operations = ["STORE x 8 3","RETRIEVE 3","STORE x 4 10","RETRIEVE 9","STORE x 6 12","STORE x 7 15","RETRIEVE 12"]return = ["true","null","true","x","true","false","null"]

The first x expires when now = 3, so retrieval returns "null" and the ID becomes reusable. The second x is live at time 9 and is retrieved. The next store succeeds, its active duplicate is rejected, and expiration at time 12 makes the final retrieval return "null".

Example 3

levelCapacities = [4,2]operations = ["STORE alpha 8 30","STORE beta 8 30","STORE old1 1 5","STORE old2 1 5","STORE gamma 9 6","STORE delta 9 30","RETRIEVE 5","RETRIEVE 5","RETRIEVE 6"]return = ["true","true","true","true","true","true","alpha","beta","delta"]

Purging old1 and old2 makes the top level eligible. Although the lower level holds heavier items, top-to-bottom level order wins first. The tie between alpha and beta is broken lexicographically. At time 6, gamma expires and the lower level returns delta.

Constraints

1 <= levelCapacities.length <= 50
1 <= levelCapacities[i] <= 10^5
The sum of all level capacities is at most 2 * 10^5.
1 <= operations.length <= 2 * 10^5.
Every operation has valid syntax and is either STORE itemId weight expiresAt or RETRIEVE now.
Each itemId has length from 1 through 20 and contains only letters, digits, underscores, or hyphens.
1 <= weight, expiresAt, now <= 10^9.