Design a Key-Value Store with Hit Counting

Problem Statement

Design and implement an in-memory key-value store that maintains a sliding-window hit counter for every key. Every successful get operation increments the key's read hit counter. The system must support querying the hit count for any key over an arbitrary lookback window up to a configured maximum duration max_window_seconds.

Your solution should emphasize thread safety, bounded memory usage per key (preventing unbounded growth under high read throughput), and low latency for both reads and writes.

Class Interface

class HitCountingKVStore:
    def __init__(self, max_window_seconds: int):
        """
        Initialize the store with a maximum trackable window size in seconds.
        """
        pass

    def put(self, key: str, value: str) -> None:
        """
        Insert or update a key-value pair.
        """
        pass

    def get(self, key: str, timestamp: int) -> Optional[str]:
        """
        Retrieve the value for key. If key exists, record a hit at the given epoch timestamp (in seconds).
        Returns None if the key does not exist.
        """
        pass

    def get_hit_count(self, key: str, window_seconds: int, timestamp: int) -> int:
        """
        Return the number of successful hits for key in the interval:
        [timestamp - window_seconds + 1, timestamp]
        Constraints: 1  bool:
        """
        Remove the key and its hit-counting history. Returns True if deleted, False if not found.
        """
        pass

Requirements

1. Counting Semantics: Only successful get calls (where the key is present) register as hits. Failed lookups must not register hits.
2. Bounded Memory: Memory overhead per key for tracking hits must be O(max_window_seconds) regardless of how many millions of hits occur within that window.
3. Concurrency: Multiple threads may call put, get, delete, and get_hit_count concurrently. Ensure linearizable reads/writes per key while avoiding a single global lock across the entire store.
4. Time Monotonicity: Timestamps passed to get and get_hit_count are non-decreasing per thread, but concurrent calls across threads may arrive slightly out of order within a small delta.

Example

store = HitCountingKVStore(max_window_seconds=300)

store.put("alpha", "data1")
store.get("alpha", timestamp=100) # returns "data1", hit recorded at t=100
store.get("alpha", timestamp=102) # returns "data1", hit recorded at t=102
store.get("beta", timestamp=103)  # returns None, no hit recorded

# Query window: [105 - 5 + 1, 105] = [101, 105]
store.get_hit_count("alpha", window_seconds=5, timestamp=105) # returns 1 (only t=102)

# Query window: [105 - 10 + 1, 105] = [96, 105]
store.get_hit_count("alpha", window_seconds=10, timestamp=105) # returns 2 (t=100 and t=102)

Constraints

• 1 <= max_window_seconds <= 86400 (up to 24 hours).
• 1 <= len(key), len(value) <= 1024.
• Read throughput is expected to be orders of magnitude higher than write throughput.