Multi-Level Warehouse Storage with Weighted Retrieval

Multi-Level Warehouse Storage with Weighted Retrieval

You are building the in-memory engine for an automated warehouse. The warehouse is a stack of horizontal levels (shelves), indexed from 0 at the top to num_levels - 1 at the bottom. Each level can hold at most capacity items.

Every item has an integer weight and is placed at an integer timestamp (a logical clock). An item expires once ttl time units have elapsed since it was stored: an item stored at time t is valid for a query at time q while q < t + ttl, and is expired (and must never be returned) once q >= t + ttl.

Implement a class Storage with the methods below.

Methods

__init__(self, num_levels, capacity, ttl) Initialize an empty warehouse with num_levels levels, each able to hold capacity items, and the given item ttl. Assume num_levels >= 1, capacity >= 1, and ttl >= 1.

store(self, item_id, weight, timestamp) -> int Place one item into the warehouse.

• The item must be placed on the topmost level (smallest index) that currently has at least one free slot, counting only items that have not yet expired at this timestamp.
• Return the index of the level on which the item was placed.
• If every level is full of non-expired items, do not store the item and return -1.
• You may assume each item_id passed to store is unique across the lifetime of the object, and that timestamp values are non-decreasing across successive calls.

retrieve(self, timestamp) -> Optional[int] Select and remove exactly one item, returning its item_id. Apply these rules in order:

1. Expire first. On every level, remove all items that are expired at this timestamp (timestamp >= stored_time + ttl). Their slots become free and they can never be retrieved.
2. Scan top to bottom. Consider levels from index 0 downward. A level is a candidate only if, after step 1, it is still at least half full — that is, the number of valid items currently on it is at least ceil(capacity / 2).
3. Pick within the first candidate level. From the topmost candidate level, choose the item with the greatest weight; break ties by the smallest item_id. Remove it from that level and return its item_id.
4. If no level qualifies, return None.

Constraints & Notes

• Levels are the primary ordering for retrieval (topmost eligible level wins); weight is only the selector within the chosen level.
• "Half full" uses the level's capacity, not how many items it has ever held: a level with c valid items qualifies iff c >= ceil(capacity / 2).
• All weight, timestamp, and ttl values are non-negative integers; weight may repeat across items.
• Expiration is evaluated lazily at the start of each retrieve (and when counting free slots in store); you are not required to evict expired items at any other time.

Example

s = Storage(num_levels=2, capacity=2, ttl=10)

s.store(1, weight=5, timestamp=0) # -> 0 (level 0 has space)
s.store(2, weight=8, timestamp=0) # -> 0 (level 0 still has space)
s.store(3, weight=3, timestamp=1) # -> 1 (level 0 now full)

s.retrieve(timestamp=2) # -> 2
 # No expirations (ttl=10). Level 0 has 2 valid items; ceil(2/2)=1, so it is a
 # candidate and is topmost. Highest weight on level 0 is item 2 (weight 8).

s.retrieve(timestamp=2) # -> 1
 # Level 0 now has 1 valid item; 1 >= ceil(2/2)=1, still a candidate.
 # Only item 1 remains there, so it is returned.

s.retrieve(timestamp=2) # -> 3
 # Level 0 has 0 items (0 < 1), not a candidate. Level 1 has 1 item
 # (1 >= 1), so item 3 is returned.

s.retrieve(timestamp=2) # -> None (warehouse empty)

An expiry example: with ttl=10, an item stored at timestamp=0 is still valid at retrieve(timestamp=9) but is treated as expired (removed, never returned) at retrieve(timestamp=10).