Design Authentication Manager
Asked at Atlassian, OpenAI
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.
Asked At
| Company | Difficulty | |
|---|---|---|
| Atlassian | Medium | View all Atlassian questions → |
| OpenAI | Medium | View all OpenAI questions → |
How to Think About It
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).
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.
Visual walkthrough:
- generate("aaa", 5): map = {aaa: 5}, list = [aaa@5]
- generate("bbb", 15): map = {aaa:5, bbb:15}, list = [aaa@5, bbb@15]
- renew("aaa", 6): current time=2. aaa was at 5, expired at time 5. 5 + 5 = 10. Since 2 < 10, it is valid. Renew: aaa expires at 2+6=8. Update map = {aaa:8, bbb:15}. Move aaa to tail.
`- At time 11: clean expired. aaa at 8, expired (11 > 8). Remove. list = [bbb@15]. bbb valid (11 < 15). Stop.
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).
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.
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.
What Trips People Up in Real Interviews
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.
Solution Code
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]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 is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
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.