Katkat
Back

Process Tokens with Explicit Expiration Times

OracleSoftware Engineer · Onsite
EasySoftware EngineerOnsiteCoding & Algorithms

Last updated

This problem tests your ability to manage temporal data using efficient data structures, specifically focusing on handling expiration logic and range-based queries.

Token Expiration Manager

Design a service to manage authentication tokens where each token has a specific expiration time. Your service must support three operations:

  1. generate(token_id, expiry_time): Register a token that expires at expiry_time.
  2. renew(token_id, new_expiry_time): If a token exists and has not yet expired (relative to new_expiry_time), update its expiration. If the token is already expired or does not exist, ignore the request.
  3. count(current_time): Return the number of tokens that are still active at current_time. A token is active if its expiry_time > current_time.

Constraints

  • token_id is a unique string.
  • expiry_time and current_time are integers.
  • The current_time in count calls will be non-decreasing.

Implementation

Implement the TokenManager class:

class TokenManager:
    def generate(self, token_id: str, expiry_time: int) -> None:
        pass

    def renew(self, token_id: str, new_expiry_time: int) -> None:
        pass

    def count(self, current_time: int) -> int:
        pass

Examples

Example 1:

  • generate("A", 10)
  • generate("B", 20)
  • count(15) -> Returns 1 (Only "B" is active)
  • renew("A", 25) -> Fails (A expired at 10)
  • count(25) -> Returns 0

Example 2:

  • generate("C", 50)
  • renew("C", 60)
  • count(55) -> Returns 1 ("C" is still active)

Edge Cases

  • Renewing a token exactly at its expiration time.
  • Calling count when multiple tokens expire at the same timestamp.
  • Handling multiple renew calls for the same token.

Hints

Hint 1

Use a hash map to keep track of the current expiration time for each token_id.

Hint 2

Since count queries arrive with non-decreasing times, consider using a min-priority queue (min-heap) to store expiration events, allowing you to discard expired tokens efficiently.

Hint 3

When a token is renewed, it is difficult to remove the old entry from a heap; consider using a lazy removal strategy or an auxiliary data structure to verify if the heap's top entry is still the current active expiration.

Follow-up questions

  • How would you modify the system if `current_time` for `count` calls was not guaranteed to be non-decreasing?
  • If the number of tokens is in the millions, how would you optimize the `count` operation to perform in better than O(N) time?
  • How would you handle high-concurrency scenarios where multiple threads are calling `generate` and `renew` simultaneously?