Per-user token bucket limiter with interval refills

Build a per-user token rate limiter for an AI API. Every user has their own policy, and one user's traffic never affects another's.

A policy has three positive integers:

• max_tokens: the bucket's capacity. A new user starts with a full bucket.
• refill_amount: how many tokens one refill adds.
• interval: seconds between refills. Refills happen in whole steps: after each full interval since the user's last refill, refill_amount tokens are added, never exceeding max_tokens.

Requests arrive at irregular times, and a user may go idle for a long time. Do not use a background timer.

Implement TokenLimiter:

• set_policy(user_id, max_tokens, refill_amount, interval, timestamp) creates or replaces a user's policy. Replacing a policy must not give the user extra tokens.
• consume(user_id, tokens, timestamp) -> bool spends tokens if the user has at least that many at timestamp and returns True. Otherwise it spends nothing and returns False.
• get_tokens(user_id, timestamp) -> int returns the user's balance at timestamp.

Timestamps are integer seconds and are usually non-decreasing. A late (smaller) timestamp must never add tokens. Calling consume or get_tokens for a user without a policy is an error.

Example

Policy for alice: max_tokens=10, refill_amount=3, interval=5, set at t=0.

Example 2

Policy for bob: max_tokens=4, refill_amount=1, interval=2 at t=0. consume("bob", 4, 0) returns True, consume("bob", 1, 1) returns False, and consume("bob", 1, 2) returns True.

Aim for O(1) time per call.

Reconstructed from the reported question; details may differ from what interviewers ask.