Implement interval room counter and token manager
Company: Microsoft
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: easy
Interview Round: Onsite
You are given two coding questions.
## 1) Minimum number of rooms for time intervals
You are given a list of meetings, where each meeting is an interval `[start, end)` with integer times (start < end). A single room can host multiple meetings as long as their time intervals do not overlap.
**Task:** Return the minimum number of rooms required to schedule all meetings.
**Input:** `intervals: List[List[int]]` where `intervals[i] = [start_i, end_i]`
**Output:** `int` = minimum number of rooms
**Notes/constraints (reasonable interview assumptions):**
- `1 <= len(intervals) <= 2e5`
- `0 <= start_i < end_i <= 1e9`
- Intervals that end at time `t` do not overlap with intervals that start at time `t` (i.e., treat as `[start, end)`).
---
## 2) Token manager with generate/renew/count
Design a token system with a fixed lifetime `timeToLive` (TTL).
Each token has an expiration time. A token generated at `currentTime` expires at `currentTime + timeToLive`.
Implement a class (or module) supporting the following operations:
- `generate(tokenId: string, currentTime: int) -> void`
- Creates a new token with id `tokenId` that expires at `currentTime + timeToLive`.
- If a token with the same `tokenId` already exists, you may assume it is overwritten with the new expiration (state your assumption).
- `renew(tokenId: string, currentTime: int) -> void`
- If `tokenId` exists and is **unexpired** at `currentTime`, update its expiration to `currentTime + timeToLive`.
- If it does not exist or is already expired at `currentTime`, do nothing.
- `countUnexpiredTokens(currentTime: int) -> int`
- Return the number of tokens whose expiration time is **strictly greater than** `currentTime`.
**Constraints (reasonable interview assumptions):**
- Up to `2e5` total operations
- `currentTime` values are non-decreasing across calls
Provide the required outputs with efficient time complexity.
Quick Answer: This pair of problems evaluates algorithmic problem-solving and data-structure design skills, specifically interval scheduling for minimum room allocation and time-based token lifecycle management, and is commonly asked to measure ability to reason about resource allocation, temporal invariants, and scalability under constraints.
Part 1: Minimum Number of Rooms for Meetings
You are given a list of meeting intervals [start, end), possibly unsorted. A single room can host multiple meetings as long as their time ranges do not overlap. Meetings that end at time t do not overlap with meetings that start at time t. Return the minimum number of rooms needed to schedule all meetings.
Constraints
- 0 <= len(intervals) <= 2 * 10^5
- 0 <= start_i < end_i <= 10^9
- Intervals that end at time t can share a room with intervals that start at time t
- Intervals may be given in any order
Examples
Input: ([[0, 30], [5, 10], [15, 20]],)
Expected Output:
Explanation: The meeting [0, 30) overlaps with both other meetings, but [5, 10) and [15, 20) do not overlap with each other.
Input: ([[1, 2], [2, 3], [3, 4]],)
Expected Output:
Explanation: Each meeting starts exactly when the previous one ends, so one room is enough.
Hints
- Sort all start times separately from all end times.
- Walk through start times in order. If the next meeting starts before the earliest current meeting ends, you need a new room; otherwise, you can reuse a room.
Part 2: Token Manager Query Simulator
You are given a token lifetime timeToLive and a sequence of queries to simulate a token manager. A token generated or renewed at time t expires at t + timeToLive, and it is considered unexpired only while expirationTime > currentTime. Support generate, renew, and count operations efficiently. For this problem, assume generate overwrites any existing token with the same tokenId.
Constraints
- 1 <= timeToLive <= 10^9
- 0 <= len(queries) <= 2 * 10^5
- currentTime values are non-decreasing across the query list
- A token is unexpired at time t only if its expiration time is strictly greater than t
- If generate is called with an existing tokenId, overwrite its expiration time
Examples
Input: (5, [('generate', 'aaa', 1), ('renew', 'aaa', 2), ('count', 6), ('count', 7)])
Expected Output:
Explanation: The token is first set to expire at 6, then renewed to expire at 7. It is alive at time 6, but not at time 7.
Input: (1, [('generate', 'a', 1), ('generate', 'b', 1), ('count', 1), ('count', 2)])
Expected Output:
Explanation: Both tokens expire at time 2. They count as unexpired at time 1 but not at time 2.
Hints
- Use a dictionary to store the latest expiration time for each token.
- A min-heap of (expirationTime, tokenId) lets you remove expired tokens lazily before each operation.