FastPrep
Problem · Design

Multi-Level Inventory Storage System

Learn this problem
● HardOptiverINTERNOA

Problem statement

Design an inventory storage system with multiple storage levels. The system receives capacities for each level and a list of operations, then returns one output string per operation.

There are n levels numbered from 0 to n - 1. Level 0 is the top level. Each level i has total capacity capacities[i].

Each stored item has an item_id, a positive integer weight, a timestamp, and a positive ttl. An item expires when the current time t >= timestamp + ttl. Expired items cannot be retrieved and should release their occupied capacity.

Operations

  • STORE item_id weight timestamp ttl: before storing, remove expired items using the operation timestamp. Scan levels from top to bottom and place the item in the first level whose remaining capacity is at least weight. Return the level number, or -1 if no level can store it.
  • RETRIEVE timestamp: before retrieving, remove expired items using the operation timestamp. Scan levels from top to bottom. A level is eligible only if its remaining capacity is at least half of its total capacity. From the first eligible level that contains at least one unexpired item, retrieve the item with the largest weight. If weights tie, retrieve the earlier stored item. If there is still a tie, retrieve the lexicographically smaller item_id. Return the retrieved item_id, or EMPTY if no item can be retrieved.

Input timestamps are non-decreasing, and each item_id in a STORE command is unique.

Function

processStorageOperations(capacities: int[], operations: String[]) → String[]

Examples

Example 1

capacities = [10]operations = ["STORE a 3 0 10", "STORE b 2 1 10", "RETRIEVE 2", "RETRIEVE 3"]return = ["0", "0", "a", "b"]

Both items fit in level 0. At time 2, remaining capacity is 5, which is at least half of 10, so retrieval is allowed. Item a has larger weight than b, so it is retrieved first.

Example 2

capacities = [5]operations = ["STORE heavy 4 0 10", "RETRIEVE 1", "STORE light 1 2 10", "RETRIEVE 11"]return = ["0", "EMPTY", "0", "light"]

After storing heavy, level 0 has only 1 remaining capacity, which is less than half of 5, so the retrieval at time 1 returns EMPTY. At time 11, heavy has expired and releases capacity, so light can be retrieved.

Constraints

  • 1 <= capacities.length <= 100
  • 1 <= operations.length <= 2 * 10^5
  • 1 <= capacities[i], weight <= 10^9
  • 0 <= timestamp <= 10^18
  • 1 <= ttl <= 10^18
  • item_id contains letters, digits, and underscores, and has length at most 30.
  • Operation timestamps are non-decreasing.
  • STORE commands use globally unique item_id values.

More Optiver problems

drafts saved locally
public String[] processStorageOperations(int[] capacities, String[] operations) {
  // write your code here
}
capacities[10]
operations["STORE a 3 0 10", "STORE b 2 1 10", "RETRIEVE 2", "RETRIEVE 3"]
expected["0", "0", "a", "b"]
checking account