Authentication Manager - TTL

PracticalmediumPremium

45:00

Desktop only

Coding Challenges are optimized for Desktop

Come back on a wider screen - the live editor needs room to breathe. You can still read the problem brief above.

Problem

API keys and OAuth tokens expire by design: a client that never renews its credential eventually loses access without any user action. You will implement the token store: issue tokens with a fixed TTL, let clients renew before expiry, and count how many are currently live.

Token expires at t if expires_at <= t - equality counts as expired (LeetCode 1797 contract). Tokens are not actively cleaned up; methods filter on access.

This problem is often paired in OpenAI loops with the Sessions variant - see Authentication Manager - Sessions.

Level 1 - basic generate / renew / count

Implement the three methods naively. O(N) count is fine for this level.

generate(tid, t) issues tid with expires_at = t + ttl. Re-generating an expired id is allowed (it's a fresh token).
renew(tid, t) only extends a token that's still live at t. If unknown or already expired, no-op - don't resurrect.
count_unexpired_tokens(t) returns how many tokens have expires_at > t.

Example:

manager = AuthenticationManager(5)
manager.generate("token-a", 1)     # expires_at = 6
manager.count_unexpired_tokens(5)  # -> 1  (still live at 5)
manager.count_unexpired_tokens(6)  # -> 0  (expired at exactly 6)

Level 2 - amortized O(1) cleanup

count_unexpired_tokens must not scan every issued token on every call. Introduce a secondary structure that lets you purge stale entries incrementally on each access rather than at a separate sweep.

Note: a renewed token leaves behind a stale entry in the secondary structure as well as an expired one - both kinds of staleness must be handled.

Example:

manager = AuthenticationManager(5)
manager.generate("token-a", 1)     # expires_at = 6
manager.renew("token-a", 2)        # new expires_at = 7
manager.count_unexpired_tokens(6)  # -> 1  (would have been 0 without renew)
manager.count_unexpired_tokens(7)  # -> 0  (now expired at 7)
manager.renew("token-a", 8)        # no-op: already expired at 8
manager.count_unexpired_tokens(9)  # -> 0  (not resurrected)

Level 3 - thread safety

Wrap generate, renew, and count_unexpired_tokens in a single threading.Lock. Concurrent calls should produce a consistent count.

Pyodide's threading.Thread runs cooperatively (single-threaded under the hood) so these tests verify correctness of the locking discipline, not real parallelism.

Example:

manager = AuthenticationManager(5)
# Each public method must hold the lock for its entire body
manager.generate("token-a", 1)          # lock acquired and released
manager.renew("token-a", 2)             # lock acquired and released
manager.count_unexpired_tokens(3)       # -> 1; lock acquired and released

Mastery checklist

Check	Why it matters
`exp <= current_time` means expired, not `<`	LC 1797 contract; off-by-one on equality is the classic bug
Renew on expired token is a no-op	Don't resurrect; lazy expiry's whole point is that expired tokens stay gone
Deque entries can be stale because of renew, not just because of expiry	Compare deque's stored exp to `self._expiry[tid]` before treating it as live
`count_unexpired_tokens` mutates the deque	Pop stale entries on every call; otherwise the deque grows without bound

Patterns used

Foundations primers this challenge draws on.

Loading editor…

Premium content

The live editor for this challenge unlocks with Premium.

0/0 passed