How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Citadel.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Citadel during technical interviews.

Design a token manager with lazy expiration

Quick Overview

This question evaluates time-based data structure design and algorithmic reasoning for managing expiring items, focusing on hashing, timestamp ordering and lazy deletion semantics. It is commonly asked in Coding & Algorithms interviews to assess practical application skills in designing efficient, scalable token/TTL managers under performance constraints rather than purely conceptual theory.

Design a token manager with lazy expiration

Company: Citadel

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

## Problem Design a token manager that tracks authentication tokens with a fixed time-to-live (TTL). Each token is valid in the half-open time interval `[createdTime, createdTime + timeToLive)`. You must support the following operations: - `TokenManager(timeToLive)`: initialize the manager with a positive integer TTL. - `generate(tokenId, currentTime)`: create a new token with id `tokenId` at `currentTime`. If `tokenId` already exists, overwrite it with the new creation time. - `renew(tokenId, currentTime)`: if `tokenId` exists and is **unexpired** at `currentTime`, update its creation time to `currentTime` (thus extending its expiry). If it does not exist or is expired, do nothing. - `countUnexpiredTokens(currentTime)`: return the number of tokens that are unexpired at `currentTime`. **Requirement:** implement efficiently using a *lazy deletion* strategy for expired tokens (i.e., remove expired entries only when needed, rather than scanning all tokens each time). ## Constraints - `1 <= timeToLive <= 10^8` - Up to `2 * 10^5` total operations - `1 <= currentTime <= 10^9` - `tokenId` is a string of length `1..20` containing letters/digits ## Example Assume `timeToLive = 5`. - `generate("abc", 1)` → token `abc` valid until time `6` - `renew("abc", 5)` → token `abc` valid until time `10` - `countUnexpiredTokens(6)` → returns `1` - `countUnexpiredTokens(10)` → returns `0` (expires at `10`)

Quick Answer: This question evaluates time-based data structure design and algorithmic reasoning for managing expiring items, focusing on hashing, timestamp ordering and lazy deletion semantics. It is commonly asked in Coding & Algorithms interviews to assess practical application skills in designing efficient, scalable token/TTL managers under performance constraints rather than purely conceptual theory.

Implement a function that simulates an authentication token manager with a fixed time-to-live (TTL). A token created at time `t` is valid in the half-open interval `[t, t + timeToLive)`, so it is expired exactly at time `t + timeToLive`. You are given `timeToLive` and a list of operations in chronological order. Support these operations: - `("generate", tokenId, currentTime)`: create a token with id `tokenId` at `currentTime`. If the token already exists, overwrite it with the new creation time. - `("renew", tokenId, currentTime)`: if `tokenId` exists and is still unexpired at `currentTime`, renew it so that its new expiry becomes `currentTime + timeToLive`. If it does not exist or is already expired, do nothing. - `("count", currentTime)`: return how many tokens are unexpired at `currentTime`. Return a list containing the results of all `count` operations, in order. Your implementation should be efficient and use a lazy expiration strategy: do not scan all tokens whenever time advances.

Constraints

1 <= timeToLive <= 10^8
0 <= len(operations) <= 2 * 10^5
1 <= currentTime <= 10^9
Operation times are given in non-decreasing order of currentTime
1 <= len(tokenId) <= 20, and tokenId contains only letters and digits

Examples

Input: (5, [("generate", "abc", 1), ("renew", "abc", 5), ("count", 6), ("count", 10)])

Expected Output: [1, 0]

Explanation: The token `abc` is first valid until 6, then renewed at time 5 so it becomes valid until 10. It is still valid at time 6, but expired at time 10 because the interval is half-open.

Input: (3, [("generate", "a", 1), ("generate", "a", 2), ("count", 3), ("count", 4), ("count", 5)])

Expected Output: [1, 1, 0]

Explanation: The second generate overwrites token `a` with a later expiry. The old heap entry becomes stale and must be ignored during lazy cleanup.

Input: (4, [("generate", "x", 1), ("generate", "y", 2), ("renew", "x", 5), ("renew", "y", 5), ("count", 5), ("count", 6), ("count", 9)])

Expected Output: [1, 1, 0]

Explanation: `x` expires exactly at time 5, so renewing it at time 5 does nothing. `y` is still valid at time 5 and gets renewed to expire at time 9.

Input: (10, [])

Expected Output: []

Explanation: No operations means there are no count results.

Input: (2, [("generate", "z", 1), ("renew", "z", 2), ("renew", "z", 3), ("count", 3), ("count", 4), ("count", 5)])

Expected Output: [1, 1, 0]

Explanation: The same token is renewed multiple times, creating multiple stale expiry records in the heap. Only the newest expiry should be considered valid.

Hints

Store the latest expiry time for each token in a hash map.
A min-heap of `(expiryTime, tokenId)` lets you lazily discard expired tokens. When popping from the heap, ignore entries that are stale because the token was renewed or overwritten later.

Last updated: May 4, 2026

Loading coding console...

Quick Overview

Design a token manager with lazy expiration

Company: Citadel

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

Constraints

1 <= timeToLive <= 10^8
0 <= len(operations) <= 2 * 10^5
1 <= currentTime <= 10^9
Operation times are given in non-decreasing order of currentTime
1 <= len(tokenId) <= 20, and tokenId contains only letters and digits

Examples

Input: (5, [("generate", "abc", 1), ("renew", "abc", 5), ("count", 6), ("count", 10)])

Expected Output: [1, 0]

Explanation: The token `abc` is first valid until 6, then renewed at time 5 so it becomes valid until 10. It is still valid at time 6, but expired at time 10 because the interval is half-open.

Input: (3, [("generate", "a", 1), ("generate", "a", 2), ("count", 3), ("count", 4), ("count", 5)])

Expected Output: [1, 1, 0]

Explanation: The second generate overwrites token `a` with a later expiry. The old heap entry becomes stale and must be ignored during lazy cleanup.

Input: (4, [("generate", "x", 1), ("generate", "y", 2), ("renew", "x", 5), ("renew", "y", 5), ("count", 5), ("count", 6), ("count", 9)])

Expected Output: [1, 1, 0]

Explanation: `x` expires exactly at time 5, so renewing it at time 5 does nothing. `y` is still valid at time 5 and gets renewed to expire at time 9.

Input: (10, [])

Expected Output: []

Explanation: No operations means there are no count results.

Input: (2, [("generate", "z", 1), ("renew", "z", 2), ("renew", "z", 3), ("count", 3), ("count", 4), ("count", 5)])

Expected Output: [1, 1, 0]

Explanation: The same token is renewed multiple times, creating multiple stale expiry records in the heap. Only the newest expiry should be considered valid.

Hints

Store the latest expiry time for each token in a hash map.
A min-heap of `(expiryTime, tokenId)` lets you lazily discard expired tokens. When popping from the heap, ignore entries that are stale because the token was renewed or overwritten later.

Last updated: May 4, 2026

Loading coding console...