Design a Multi-Level Expiring Item Store

Problem Statement

In low-latency trading infrastructure, caches are frequently partitioned into multiple hierarchical tiers (levels), where each tier has distinct latency, priority, or persistence characteristics. Items stored in these tiers expire after a set time.

Implement the MultiLevelStore class that manages items across num_levels ordered tiers (indexed from 0 to num_levels - 1, where level 0 has the highest priority).

Class Interface

class MultiLevelStore:
    def __init__(self, num_levels: int):
        """
        Initializes the store with the given number of storage levels.
        Levels are indexed 0 to num_levels - 1.
        """
        pass

    def store(self, key: str, value: int, level: int, expires_at: int) -> None:
        """
        Stores or updates an item at the specified level with an absolute
        expiration timestamp (expires_at). If the key already exists at this
        level, overwrite its value and expires_at.
        """
        pass

    def retrieve(self, key: str, current_time: int) -> int | None:
        """
        Searches for key from level 0 up to level num_levels - 1.
        Returns the value from the lowest-indexed level where key is present
        and not expired (expires_at > current_time).
        Expired entries encountered during the lookup should be removed.
        Returns None if key is not found or is expired at all levels.
        """
        pass

    def purge_expired(self, current_time: int) -> int:
        """
        Removes all expired items (expires_at <= current_time) across all levels.
        Returns the total number of items removed.
        """
        pass

Constraints

• 1 <= num_levels <= 16
• 0 <= level < num_levels
• 1 <= len(key) <= 64, consisting of alphanumeric characters
• 0 <= current_time, expires_at <= 2 * 10^9
• Values are standard signed 32-bit integers.
• Total number of method calls does not exceed 10^5.

Example

store = MultiLevelStore(3)

# Store key "bid" at level 1 and level 0 with different expirations
store.store("bid", 100, 1, 50)   # Level 1: "bid" expires at 50
store.store("bid", 105, 0, 30)   # Level 0: "bid" expires at 30
store.store("ask", 110, 2, 40)   # Level 2: "ask" expires at 40

# At time 20, both level 0 and level 1 have "bid". Level 0 takes priority.
assert store.retrieve("bid", 20) == 105

# At time 35, level 0 "bid" has expired (30 <= 35), falls back to level 1
assert store.retrieve("bid", 35) == 100

# At time 45, level 2 "ask" has expired (40 <= 45)
assert store.retrieve("ask", 45) is None

# Purge expired items at time 60
# Level 1 "bid" is now expired (50 <= 60). Level 0 "bid" and level 2 "ask"
# were already lazily evicted by retrieve(). Only 1 item remains to be purged.
assert store.purge_expired(60) == 1

Edge Cases to Consider

• Overwriting a key at a given level before it expires with a new value and earlier/later expiration timestamp.
• Calling retrieve when an item is expired at level 0 but valid at level 1; ensure the expired item at level 0 is properly cleaned up and does not mask the valid item at level 1.
• Invocations where expires_at == current_time should be treated as expired.