How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a easy difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Microsoft.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Microsoft during technical interviews.

Implement interval room counter and token manager

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.

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.

Input: ([[1, 5], [2, 6], [3, 7], [4, 8]],)

Expected Output:

Explanation: All four meetings overlap at time 4, so four rooms are required.

Input: ([],)

Expected Output:

Explanation: No meetings means no rooms are needed.

Input: ([[5, 9]],)

Expected Output:

Explanation: A single meeting always needs exactly one room.

Solution

def solution(intervals):
    if not intervals:
        return 0

    starts = sorted(interval[0] for interval in intervals)
    ends = sorted(interval[1] for interval in intervals)

    rooms = 0
    end_ptr = 0

    for start in starts:
        if start < ends[end_ptr]:
            rooms += 1
        else:
            end_ptr += 1

    return rooms

Time complexity: O(n log n). Space complexity: O(n).

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.

Input: (4, [('generate', 'x', 1), ('count', 4), ('renew', 'x', 5), ('count', 5)])

Expected Output:

Explanation: The token expires at time 5. Renewing at time 5 does nothing because it is already expired at that moment.

Input: (3, [('generate', 'a', 1), ('generate', 'a', 2), ('count', 3), ('count', 4), ('count', 5)])

Expected Output:

Explanation: The second generate overwrites the first expiration, so the token survives through time 4 and expires at time 5.

Input: (10, [])

Expected Output:

Explanation: With no queries, there are no count results.

Solution

def solution(timeToLive, queries):
    import heapq

    expirations = {}
    heap = []
    result = []

    def cleanup(currentTime):
        while heap and heap[0][0] <= currentTime:
            expiry, tokenId = heapq.heappop(heap)
            if expirations.get(tokenId) == expiry:
                del expirations[tokenId]

    for query in queries:
        op = query[0]

        if op == 'count':
            currentTime = query[1]
            cleanup(currentTime)
            result.append(len(expirations))
        elif op == 'generate':
            tokenId, currentTime = query[1], query[2]
            cleanup(currentTime)
            expiry = currentTime + timeToLive
            expirations[tokenId] = expiry
            heapq.heappush(heap, (expiry, tokenId))
        elif op == 'renew':
            tokenId, currentTime = query[1], query[2]
            cleanup(currentTime)
            if tokenId in expirations:
                expiry = currentTime + timeToLive
                expirations[tokenId] = expiry
                heapq.heappush(heap, (expiry, tokenId))
        else:
            raise ValueError('Unknown operation: {}'.format(op))

    return result

Time complexity: O(q log q). Space complexity: O(q).

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.

Quick Overview