Implement Expiration-Aware Retrieval Across Storage Levels

Problem Statement

In high-frequency trading infrastructure, multi-tiered staging buffers store pending outbound messages or cached market-state snapshots across different memory tiers.

You are tasked with implementing an expiration-aware multi-level storage manager, MultiLevelStorage.

The system is initialized with an ordered list of storage levels. Levels defined earlier in the list have strictly higher priority than those defined later. Each level has a fixed maximum capacity representing the maximum number of items it can hold.

Implement the following methods:

• __init__(levels: list[tuple[int, int]]): Initializes the storage with a list of (level_id, capacity) pairs. Order in levels defines priority (index 0 is highest priority). All level_id values are unique and capacity >= 1.

• insert(level_id: int, item_id: str, weight: int, expiry: int) -> bool: Inserts an item with unique identifier item_id, positive integer weight, and expiration timestamp expiry into level_id. If level_id does not exist, or the level is currently at full capacity, the insertion fails and returns False. Otherwise, stores the item and returns True.

• retrieve(current_time: int) -> str | None: Executes a retrieval operation following these deterministic steps:

  1. Purge Expired: Across all levels, discard any item where expiry <= current_time.
  2. Filter Eligible Levels: A level is eligible if and only if it is at least half free after purging: current_item_count <= capacity / 2.
  3. Select Best Item: Among all items residing in eligible levels, select the item with the maximum weight.
     • Tie-breaker 1: Choose the item in the higher-priority level (smaller initial index in levels).
     • Tie-breaker 2: Choose the item inserted earlier (earliest insertion order).
  4. Remove and Return: Remove the selected item from its level and return its item_id. If no items exist in eligible levels, return None.

Example

storage = MultiLevelStorage([(1, 4), (2, 2)])
# Level 1: capacity 4, highest priority
# Level 2: capacity 2, lower priority

storage.insert(1, "A", weight=10, expiry=100) # count=1  4/2  (ineligible)
storage.insert(2, "D", weight=25, expiry=100) # count=1 <= 2/2 (eligible)

# At t=40, Level 1 has 3 items (ineligible). Level 2 has 1 item (eligible).
# Only Level 2 is eligible, so "D" is returned.
assert storage.retrieve(40) == "D"

# At t=60, Level 1 item "B" has expired (expiry=50  Level 1 is now eligible.
# Level 2 is empty.
# Heaviest item in Level 1 is "C".
assert storage.retrieve(60) == "C"

Constraints

• Number of levels L <= 100.
• Level capacity 1 <= capacity <= 1,000.
• 1 <= weight <= 10^9.
• Timestamps (expiry, current_time) are non-negative integers up to 10^9. current_time in calls to retrieve is non-decreasing.
• Total calls to insert and retrieve combined <= 50,000.