MediumHash TableLinked ListDesignDoubly-Linked ListUpdated Sep 2026

1797. Design Authentication Manager

Asked at Atlassian, OpenAI

Difficulty

Medium

Time

O(1) amortized per call

Space

O(n)

Pattern

Hash Table

Companies

2

Problem

Design a class called AuthenticationManager that manages login tokens. Each token has an id (a short lowercase string) and an expiry time. A token created at time t expires at t + timeToLive. The class is built once with a fixed timeToLive, and then receives a stream of calls.

You must support three operations. generate(tokenId, currentTime) creates a new token that expires timeToLive seconds after currentTime. renew(tokenId, currentTime) pushes the expiry of an existing, still-valid token out to currentTime + timeToLive; if no live token has that id, the call does nothing. countUnexpiredTokens(currentTime) returns how many tokens are still alive at currentTime.

One timing rule matters: a token that expires at time t is already dead at time t. So if a token expires at 7 and you call renew or countUnexpiredTokens at time 7, the token is treated as gone. Also, currentTime is strictly increasing across all calls, and every generate uses a brand-new id.

Tokens live for timeToLive seconds

timealive2345678generate("aaa", 2) with ttl 5 → alive on times 2..6, deadat 7
A token created at time 2 with ttl 5 is alive until time 7, and dead from time 7 onward.

Constraints

  • ●1 <= timeToLive <= 10^8
  • ●1 <= currentTime <= 10^8
  • ●1 <= tokenId.length <= 5
  • ●tokenId consists only of lowercase letters
  • ●All calls to generate use unique tokenId values
  • ●currentTime values across all calls are strictly increasing
  • ●At most 2000 calls are made to all functions combined

Examples

Example 1
Input["AuthenticationManager", "renew", "generate", "countUnexpiredTokens", "generate", "renew", "renew", "countUnexpiredTokens"] [[5], ["aaa", 1], ["aaa", 2], [6], ["bbb", 7], ["aaa", 8], ["bbb", 10], [15
Output[null, null, null, 1, null, null, null, 0]
WhyWith ttl = 5: renew at time 1 finds no "aaa", so nothing happens. generate "aaa" at 2 gives it expiry 7. At time 6 it is still alive (6 < 7), so the count is 1. generate "bbb" at 7 gives expiry 12. renew "aaa" at 8 fails because "aaa" died at 7. renew "bbb" at 10 succeeds and moves its expiry to 15.
Example 2
Input["AuthenticationManager", "generate", "countUnexpiredTokens", "generate", "countUnexpiredTokens"] [[10], ["a", 1], [5], ["b", 6], [20]]
Output[null, null, 1, null, 0]
Whyttl = 10. "a" is created at 1 and expires at 11, so at time 5 the count is 1. "b" is created at 6 and expires at 16. At time 20 both are past their expiry, so the count is 0.

Asked At

2 companies
CompanyDifficulty
AtlassianMediumView all Atlassian questions →
OpenAIMediumView all OpenAI questions →

How to Think About It

1

Key insight: you need three operations — generate (create token), renew (extend expiry), revoke (remove token). A hash map from token to expiry time gives O(1) lookups. But expiry removal requires scanning all tokens, which is O(n).

2

To get O(1) expiry removal, use a doubly linked list ordered by expiry time. The oldest token is always at the head. When you need to clean expired tokens, pop from the head until you find a valid one.

3

For the doubly linked list: maintain a dummy head and dummy tail sentinel. Insert new tokens at the tail (most recent). To remove a node, you need direct access — the hash map should store (expiry, node) pairs so you can remove in O(1).

4

Edge cases: renewing an expired token should fail (return immediately). Revoking a non-existent token should be a no-op. Multiple generates with the same token id: the second overwrites the first.

5

Alternative without linked list: just use the hash map and clean expired tokens lazily during each operation. This is O(n) worst case for cleanup but O(1) amortized if tokens expire infrequently.

Optimal Approach

Maintain a hash map mapping token to expiry time. Maintain a doubly linked list of tokens ordered by insertion time.

  • generate(tokenId, currentTime, timeToLive): create token with expiry = currentTime + timeToLive. Add to map and list tail.
  • renew(tokenId, currentTime, timeToLive): if token exists and not expired (expiry > currentTime), update expiry = currentTime + timeToLive. Move to list tail. Otherwise, do nothing.
  • revoke(tokenId, currentTime): if token exists, remove from map and list.
  • Before each operation, clean expired tokens from the list head.

The doubly linked list ensures that expired tokens are always at the head, so cleanup is O(k) where k is the number of expired tokens. Using a sentinel head and tail simplifies edge cases.

Time: O(1) for generate/renew/revoke (with lazy cleanup). Space: O(n) where n is the number of active tokens.

Hash map plus expiry-ordered list

expiry orderaaa@7bbb@12nulloldestAfter generate("aaa",2) and generate("bbb",7): aaaexpires firstafter renew("bbb",10)aaa@7bbb@15nullrenew moves bbb to the back with a later expiry of 15expiry = currentTime + timeToLivetoken is dead when currentTime >= expirypop dead tokens from the front
The map finds a token fast; the list keeps the soonest-to-expire token at the front so cleanup is cheap.
ComplexityTime O(1) amortized per callSpace O(n)Each token is inserted and removed from the hash map and the linked list once, so cleanup work is spread across calls; n is the number of live tokens.

What Trips People Up in Real Interviews

1

Forgetting to clean expired tokens before each operation. Without lazy cleanup, expired tokens accumulate and the hash map grows unbounded. Always clean at the start of generate, renew, and revoke.

2

Off-by-one in expiry comparison. A token expires at time expiry, so it is valid while currentTime < expiry. If currentTime == expiry, the token is expired. Use strict less-than: expiry > currentTime.

3

Trying to remove from the linked list while iterating. Never iterate and remove simultaneously. Clean only from the head, one direction, and stop as soon as you find a valid token.

4

Not handling the case where renew is called on an expired token. The token exists in the map but its expiry is in the past. You must check expiry > currentTime before renewing, not just whether the token exists in the map.

5

Using a singly linked list instead of doubly linked. With a singly linked list, you can't remove a node from the middle in O(1) — you need the previous pointer. A doubly linked list or an iterator in the map is required.

Solution Code

O(1) amortized per call time
class Node:
    def __init__(self, token_id='', expiry=0):
        self.token_id = token_id
        self.expiry = expiry
        self.prev = None
        self.next = None

class AuthenticationManager:
    def __init__(self, timeToLive):
        self.ttl = timeToLive
        self.tokens = {}
        self.head = Node()
        self.tail = Node()
        self.head.next = self.tail
        self.tail.prev = self.head

    def _add_to_tail(self, node):
        prev_node = self.tail.prev
        prev_node.next = node
        node.prev = prev_node
        node.next = self.tail
        self.tail.prev = node

    def _remove(self, node):
        node.prev.next = node.next
        node.next.prev = node.prev

    def _clean_expired(self, currentTime):
        while self.head.next != self.tail and self.head.next.expiry <= currentTime:
            expired = self.head.next
            self._remove(expired)
            del self.tokens[expired.token_id]

    def generate(self, tokenId, currentTime):
        self._clean_expired(currentTime)
        node = Node(tokenId, currentTime + self.ttl)
        self.tokens[tokenId] = node
        self._add_to_tail(node)

    def renew(self, tokenId, currentTime):
        self._clean_expired(currentTime)
        if tokenId in self.tokens and self.tokens[tokenId].expiry > currentTime:
            node = self.tokens[tokenId]
            self._remove(node)
            node.expiry = currentTime + self.ttl
            self._add_to_tail(node)

    def revoke(self, tokenId, currentTime):
        self._clean_expired(currentTime)
        if tokenId in self.tokens:
            self._remove(self.tokens[tokenId])
            del self.tokens[tokenId]

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

Frequently Asked Questions

What is the Design Authentication Manager problem?

Design an authentication manager that issues, renews, and expires tokens. Each token has a `timeToLive` and must be removed after expiry. Use a `hash map` for `O(1)` lookups and a doubly linked list for `O(1)` eviction ordering.

How do you solve Design Authentication Manager?

The optimal approach runs in O(1) amortized per call time and O(n) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

What companies ask Design Authentication Manager?

Design Authentication Manager is asked at Atlassian, OpenAI. It is a medium difficulty problem.

What are common mistakes on Design Authentication Manager?
  • Forgetting to clean expired tokens before each operation. Without lazy cleanup, expired tokens accumulate and the `hash map` grows unbounded. Always clean at the start of generate, renew, and revoke.
  • Off-by-one in expiry comparison. A token expires at time `expiry`, so it is valid while `currentTime < expiry`. If `currentTime == expiry`, the token is expired. Use strict less-than: `expiry > currentTime`.
  • Trying to remove from the linked list while iterating. Never iterate and remove simultaneously. Clean only from the head, one direction, and stop as soon as you find a valid token.
  • Not handling the case where `renew` is called on an expired token. The token exists in the map but its expiry is in the past. You must check expiry > currentTime before renewing, not just whether the token exists in the map.
  • Using a singly linked list instead of doubly linked. With a singly linked list, you can't remove a node from the middle in `O(1)` — you need the previous pointer. A doubly linked list or an iterator in the map is required.