Time-to-Live Token Manager With Renewal and a Heavy Concurrent Read/Write Follow-up

The interviewer opened with some background about an application built on a large language model (LLM) before getting to the code. That framing was not reported in detail. The part you implement is self-contained: a manager for tokens that expire a fixed amount of time after they are issued or last renewed. The interviewer then pushed the design toward heavy concurrent use. Assume a class shaped like this (names are illustrative; keep the semantics): ```python class TokenManager: def __init__(self, time_to_live: int): ... def generate(self, token_id: str, current_time: int) -> None: ... def renew(self, token_id: str, current_time: int) -> None: ... def count_unexpired(self, current_time: int) -> int: ... ``` ### Constraints and Clarifications - `time_to_live` is a positive integer number of seconds, fixed at construction. All times are integer seconds. - A token generated or renewed at time `t` expires at time `t + time_to_live`. - If a token expires at time `t` and another call also happens at time `t`, the expiration takes effect first. At its expiry time a token can no longer be renewed and is no longer counted. - Every call to `generate` uses a token id that has never been generated before. - In Part 1, calls arrive one at a time and `current_time` strictly increases from one call to the next. ### Clarifying Questions - What do the tokens stand for in the LLM application (for example, user sessions or issued credentials), and does that change how long they should live or who may renew them? - How many tokens can be live at once, and how often is `count_unexpired` called compared with `generate` and `renew`? - Must expired tokens be removed from memory, or is it enough that they are no longer counted? ### Part 1 — Generate, renew, and count unexpired tokens Implement: - `generate(token_id, current_time)`: issues a new token that expires at `current_time + time_to_live`. - `renew(token_id, current_time)`: if the token exists and has not expired at `current_time`, resets its expiry to `current_time + time_to_live`. Otherwise the call is ignored. - `count_unexpired(current_time)`: returns the number of tokens that have not expired at `current_time`. Example with `time_to_live = 10`: | call | returns | effect | |---|---|---| | `generate("x", 1)` | nothing | `x` expires at 11 | | `generate("y", 4)` | nothing | `y` expires at 14 | | `count_unexpired(10)` | `2` | both tokens are live | | `renew("x", 11)` | nothing | ignored: `x` expired at 11, before the renewal | | `renew("y", 12)` | nothing | `y` now expires at 22 | | `count_unexpired(14)` | `1` | only `y` is live | | `count_unexpired(22)` | `0` | `y` expired at 22 | ```hint One definition of live Write the single comparison that decides whether a token is live at time `t`, and make all three methods use it, including at the exact instant a token expires. ``` ```hint What a count has to visit Ask whether a count at time `t` needs to look at every token ever issued, or only at the tokens whose lifetimes ended since the last cleanup. ``` #### Clarifying Questions for this Part - Should `renew` report whether it renewed anything, or is silently ignoring a missing or expired token enough? - Could different tokens need different lifetimes later on? #### What This Part Should Cover - Expiry semantics that agree across all three methods, including the instant a token expires - Renewal that extends only live tokens and never revives an expired one - A data structure for counting and cleanup, with its per-operation time and memory cost ### Part 2 — Heavy concurrent reads and writes The manager is now shared by many threads that call `generate`, `renew` and `count_unexpired` at high rates at the same time, and both reads and writes are heavy. Make it correct under concurrent access, and explain how you would keep throughput high. ```hint Check, then act Look at what `renew` does between reading a token's expiry and writing a new one, and at what another thread could do in that gap. ``` ```hint Is a count really a read Check whether `count_unexpired` changes any shared state in your Part 1 design, and what that means for letting many counts run at once. ``` #### Clarifying Questions for this Part - Roughly how many threads and calls per second are expected, and what is the mix of `generate`, `renew` and `count_unexpired`? - Must `count_unexpired` reflect one exact instant, or is a slightly stale value acceptable? - Will callers keep passing `current_time`, or may the manager read its own clock? If callers pass it, can two calls arrive out of time order? - Does this run in one process, or do several servers share the same tokens? #### What This Part Should Cover - Which operations must be atomic, and which races appear without that, especially around `renew` - A locking or data-structure design that lets heavy reads and writes proceed in parallel, with its costs - The consistency a concurrent `count_unexpired` provides, and how time ordering stays consistent across threads - Removing expired tokens without stalling calls on the hot path ### What a Strong Answer Covers - One stated definition of a live token that every operation preserves in both Parts - How the Part 1 structure choice enables or limits the Part 2 concurrency design - Tests: timing-boundary sequences for Part 1, and concurrent stress tests that check the invariants for Part 2 - Per-operation time and memory cost, and how lock contention changes real throughput ### Follow-up Questions - Tokens must now be shared by several server instances. What changes, and where does the time used for expiry come from? - Add explicit revocation, such as a user logging out. How do you make sure a `renew` racing with the revocation cannot bring the token back? - One popular token is renewed far more often than any other, many times within the same second. How would you cut that write load, and what expiry precision would you give up? - How would you publish the live-token count as a metric without making `count_unexpired` a contention point?