Pass a Clock and a Store into a Rate Limiter

Build a rate limiter that allows at most limit requests per key in any window of window_seconds seconds. It takes a clock and a store as arguments, so the tests replay timestamps instead of waiting. Requests arrive one at a time, and everything runs in memory.

The starter defines these Protocols and classes:

class Clock(Protocol):
    def now(self) -> float: ...


class RateLimitStore(Protocol):
    def get(self, key: str) -> list[float] | None: ...
    def set(self, key: str, hits: list[float]) -> None: ...


class RateLimiter:
    def __init__(self, clock: Clock, store: RateLimitStore) -> None: ...
    def allow(self, key: str, limit: int, window_seconds: float) -> bool: ...

The starter's allow keeps every old hit forever and records denied requests, and its solve ignores times. Fix both.

How allow decides

1. Read the clock once to get now. Then load the key's timestamps from the store. None means the key has no hits yet.
2. Keep only the timestamps strictly greater than now - window_seconds. A timestamp exactly on that boundary has expired.
3. If fewer than limit timestamps remain, append now and return True. Otherwise return False, and leave the request out of the list.
4. Write the kept list back to the store in both cases. Build a new list, and leave the list that get returned as it was.

With limit=1 and a 10-second window:

• Only allowed requests count toward the limit.
• Each key has its own history.
• Two requests at the same time are two requests.
• A limit of zero or less denies every request, and allow still writes the kept list back.
• With a window of zero, every earlier request has already expired.

The driver

def solve(
    times: list[float], keys: list[str], limit: int, window_seconds: float
) -> list[bool]: ...

Create one FakeClock, one MemoryStore and one RateLimiter for each call to solve. For each (time, key) pair, set the clock to that time, call allow, and collect the results in order. Use zip(times, keys, strict=True), so lists of different lengths raise ValueError instead of dropping requests. Empty lists return []. Do not change the input lists.

Times are in seconds, and each one is equal to or later than the one before it. The window is zero or more seconds.

Constraints

• Do not call the system clock, sleep, or patch anything. Move time forward with the fake clock.
• FakeClock and MemoryStore must fit the Protocols without inheriting from them.
• Your solution must pass mypy --strict.