Quick Overview

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.

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

  1. Sort all start times separately from all end times.
  2. 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

  1. Use a dictionary to store the latest expiration time for each token.
  2. A min-heap of (expirationTime, tokenId) lets you remove expired tokens lazily before each operation.

Loading coding console...