Design a Tiered Expiring Item Store

Problem Statement

In high-throughput trading systems, cached state must often be partitioned across memory tiers with differing performance and capacity profiles. Design an in-memory tiered store, TieredExpiringStore, that holds weighted items across L ordered tiers (Tier 0 has highest priority, Tier L - 1 has lowest priority).

Each tier i has a fixed weight capacity capacities[i]. Items consume integer weight and expire after a time-to-live (ttl). Expired items must be cleaned up to reclaim capacity.

Implement the following interface:

class TieredExpiringStore:
    def __init__(self, capacities: list[int]):
        """
        Initializes the store with L tiers, where capacities[i] is the maximum 
        weight capacity of tier i. Tier 0 is the highest priority tier.
        """
        pass

    def put(self, item_id: str, weight: int, score: int, ttl: int, timestamp: int) -> bool:
        """
        Inserts or replaces an item with given weight, score, and ttl (expires at timestamp + ttl).
        Returns True if the item was successfully placed, or False otherwise.
        """
        pass

    def get(self, item_id: str, timestamp: int) -> int | None:
        """
        Retrieves the score of item_id if present and not expired at timestamp.
        Returns None if not found or expired.
        """
        pass

    def poll_highest(self, timestamp: int) -> tuple[str, int] | None:
        """
        Finds and removes the highest-priority eligible item across the store.
        Returns (item_id, score), or None if the store is empty of valid items.
        """
        pass

Rules and Constraints

1. Expiration & Reclaiming: An item is considered expired if timestamp >= expiry_time (where expiry_time = timestamp + ttl). Expired items must not be returned and their weight must be reclaimed.
2. Placement Policy: When put is called:
   • If item_id already exists in any tier, the old record is completely removed first, reclaiming its weight.
   • Expired items should be cleaned up from candidate tiers before evaluating placement.
   • Iterate through tiers from 0 to L - 1:
     • For tiers 0 through L - 2, an item is placed in tier i only if it keeps the tier strictly at or above the 50% free-capacity boundary: used_weight + weight <= capacities[i] // 2.
     • For the final tier L - 1, the item can use up to 100% capacity: used_weight + weight <= capacities[L - 1].
   • The item is placed in the first tier that satisfies the capacity requirement. If no tier has space, put fails and returns False.
3. Retrieval Policy (poll_highest):
   • Selects from the lowest-index (highest-priority) tier that contains at least one unexpired item.
   • Within that tier, selects the item with the highest score.
   • Deterministic Tie-Breaking: If scores are equal, select the item with the lexicographically smallest item_id.
   • The selected item is removed from the store and its weight reclaimed.
4. Efficiency: put, get, and poll_highest should run in logarithmic time with respect to the number of items in a tier using dual-heap indexing with lazy deletion.

Example

store = TieredExpiringStore([100, 200]) # Tier 0 max = 100 (50% boundary = 50), Tier 1 max = 200 (100% boundary = 200)

# At timestamp 10, put 'A' (weight 40, score 10, ttl 10) -> expires at 20
# Tier 0 has 0 + 40  fits in Tier 0
assert store.put("A", 40, 10, 10, 10) == True

# At timestamp 12, put 'B' (weight 20, score 50, ttl 10) -> expires at 22
# Tier 0 has 40 + 20 = 60 > 50 -> spills to Tier 1 (0 + 20  fits)
assert store.put("B", 20, 50, 10, 12) == True

# Tier 0 has 'A' (score 10). Tier 1 has 'B' (score 50).
# poll_highest checks highest priority tier with valid items (Tier 0).
assert store.poll_highest(15) == ("A", 10)

# At timestamp 25, 'B' is expired (expiry 22 <= 25).
assert store.get("B", 25) is None
assert store.poll_highest(25) is None