PracHub
QuestionsPremiumCoachesLearningGuidesInterview Prep

Quick Overview

This question evaluates competency in interval reasoning, managing overlapping time ranges across distributed resources, designing online data structures for streaming task arrivals, and performing algorithmic time/space complexity analysis.

  • medium
  • Fireworks Ai
  • Coding & Algorithms
  • Software Engineer

Find global GPU idle intervals

Company: Fireworks Ai

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

You are given a set of GPU tasks. Each task is a tuple `(start, end, node_id)` where: - `start` and `end` are timestamps (e.g., integers, with `start < end`). - The task runs on a single GPU identified by `node_id`. - Multiple tasks may overlap in time (possibly on different nodes). Define the **GPU fleet idle time** as any time interval during which **no tasks are running on any node** (i.e., across the entire fleet, the number of active tasks is 0). ### Part 1 (batch) Given an unsorted list of tasks, return all maximal **idle time intervals** as a list of disjoint intervals `(idle_start, idle_end)`. Clarifications/assumptions to make explicit in your solution: - You should infer the overall time range from the tasks themselves (i.e., consider idle gaps only **between** the earliest task start and the latest task end). - If tasks touch (e.g., one ends at `t` and another starts at `t`), there is **no** idle time at `t`. ### Part 2 (streaming) Now tasks arrive one at a time in a stream. Design an efficient approach/data structure that supports: - `addTask(start, end, node_id)` - `getIdleIntervals()` → returns the current set of maximal idle intervals based on all tasks seen so far Discuss expected time/space complexity per operation. (You may assume timestamps are integers and tasks may arrive out of order.)

Quick Answer: This question evaluates competency in interval reasoning, managing overlapping time ranges across distributed resources, designing online data structures for streaming task arrivals, and performing algorithmic time/space complexity analysis.

Find Global GPU Idle Intervals (Batch)

You are given a set of GPU tasks. Each task is a tuple `(start, end, node_id)` where `start` and `end` are integer timestamps with `start < end`, and the task runs on a single GPU identified by `node_id`. Multiple tasks may overlap in time, possibly on different nodes. Define the **GPU fleet idle time** as any interval during which **no task is running on any node** (the number of active tasks across the entire fleet is 0). Given an unsorted list of tasks, return all maximal **idle intervals** as a list of disjoint intervals `(idle_start, idle_end)`, sorted by start time. Rules: - Infer the overall time range from the tasks: only consider idle gaps **between** the earliest task start and the latest task end. - If tasks touch (one ends at `t` and another starts at `t`), there is **no** idle time at `t`. - If the task list is empty, return an empty list. **Input:** `tasks` — a list of `(start, end, node_id)` tuples. **Output:** a list of `(idle_start, idle_end)` tuples.

Constraints

  • 1 <= number of tasks <= 10^5 (or 0 for an empty list)
  • start < end for every task
  • Timestamps are integers and may be negative
  • Tasks may overlap on the same or different nodes and arrive unsorted

Examples

Input: ([(1, 3, 0), (5, 8, 1)],)

Expected Output: [(3, 5)]

Explanation: Fleet busy on [1,3] and [5,8]; idle on the gap (3,5).

Input: ([(1, 3, 0), (2, 6, 1), (8, 10, 0)],)

Expected Output: [(6, 8)]

Explanation: Overlapping tasks 1-3 and 2-6 merge to cover [1,6]; then 8-10. The only idle gap is (6,8).

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

Expected Output: []

Explanation: One task ends at 5 exactly as the next starts; touching intervals leave no idle time.

Input: ([(0, 10, 0)],)

Expected Output: []

Explanation: A single task covers the whole inferred range, so there is no idle time.

Input: ([],)

Expected Output: []

Explanation: No tasks means no inferred time range and no idle intervals.

Input: ([(1, 2, 0), (4, 5, 1), (7, 9, 2)],)

Expected Output: [(2, 4), (5, 7)]

Explanation: Three separated tasks produce two idle gaps: (2,4) and (5,7).

Input: ([(-5, -2, 0), (0, 3, 1)],)

Expected Output: [(-2, 0)]

Explanation: Negative timestamps are handled the same way; idle gap is (-2,0).

Hints

  1. Idle time is a global property: collapse all nodes into one fleet-wide count of active tasks. The node_id does not affect whether the fleet is idle.
  2. Convert each task into two events: +1 at start, -1 at end. Sweep timestamps in order while maintaining a running count of active tasks.
  3. When sorting ties, process end events (-1) before start events (+1) at the same timestamp so touching intervals don't create a spurious idle gap.
  4. Whenever the count is 0 between two consecutive distinct event timestamps, that span is a maximal idle interval.

Find Global GPU Idle Intervals (Streaming)

Same setup as the batch version: GPU tasks `(start, end, node_id)` define fleet-wide busy time, and **idle time** is any interval with zero active tasks across all nodes. Now tasks arrive one at a time in a stream (possibly out of order), and you must support repeated idle-interval queries efficiently. Design a stateful structure that supports: - `addTask(start, end, node_id)` — record a task. - `getIdleIntervals()` — return the current maximal idle intervals based on all tasks seen so far. To make this executable, you are given a list of **operations** and must return the result of each query in order. Each operation is one of: - `["add", start, end, node_id]` — perform `addTask`. - `["get"]` — perform `getIdleIntervals`; append its result (a list of `(idle_start, idle_end)` tuples sorted by start) to the output list. Return a list whose i-th element is the result of the i-th `"get"` operation. Rules match the batch version: touching busy intervals leave no idle time; idle gaps are only those strictly between merged busy intervals.

Constraints

  • 1 <= number of operations <= 10^5
  • For add ops: start < end; timestamps are integers and may be negative
  • Tasks may arrive out of order and may overlap
  • node_id does not affect idle computation (fleet-wide busy union)

Examples

Input: ([["add", 1, 3, 0], ["add", 5, 8, 1], ["get"]],)

Expected Output: [[(3, 5)]]

Explanation: After adding both tasks, the single idle gap between busy [1,3] and [5,8] is (3,5).

Input: ([["add", 5, 8, 1], ["add", 1, 3, 0], ["get"]],)

Expected Output: [[(3, 5)]]

Explanation: Tasks arrive out of order but the merged busy set is the same; idle is still (3,5).

Input: ([["add", 1, 3, 0], ["get"], ["add", 2, 6, 1], ["get"], ["add", 8, 10, 0], ["get"]],)

Expected Output: [[], [], [(6, 8)]]

Explanation: First get: only one interval, no gap. Second get: 1-3 and 2-6 merge to [1,6], still no gap. Third get: adding 8-10 creates idle gap (6,8).

Input: ([["add", 1, 5, 0], ["add", 5, 9, 1], ["get"]],)

Expected Output: [[]]

Explanation: Touching intervals [1,5] and [5,9] merge into [1,9] with no idle time.

Input: ([["get"]],)

Expected Output: [[]]

Explanation: Querying an empty stream yields no idle intervals.

Input: ([["add", 1, 2, 0], ["add", 7, 9, 2], ["add", 4, 5, 1], ["get"]],)

Expected Output: [[(2, 4), (5, 7)]]

Explanation: Three disjoint tasks (added out of order) leave two idle gaps: (2,4) and (5,7).

Input: ([["add", 1, 4, 0], ["add", 6, 9, 1], ["add", 3, 7, 2], ["get"]],)

Expected Output: [[]]

Explanation: The third task 3-7 bridges the gap between [1,4] and [6,9], merging everything into [1,9] with no idle time.

Hints

  1. Idle intervals are the complement of the union of all busy intervals, so maintain the merged set of busy intervals incrementally rather than recomputing from scratch.
  2. On addTask, find every existing interval that overlaps or touches the new one, absorb them into a single interval, and replace them — classic merge-interval insertion.
  3. Keep busy intervals sorted and disjoint (merge touching ones too). Then getIdleIntervals is just the strict gaps between consecutive busy intervals.
  4. For best per-op complexity use an ordered map keyed by start; locate the insertion point in O(log k) and remove swallowed intervals in O(m).
Last updated: Jun 21, 2026

Loading coding console...

PracHub

Master your tech interviews with 8,000+ real questions from top companies.

Product

  • Questions
  • Learning Tracks
  • Interview Guides
  • Resources
  • Premium
  • For Universities
  • Student Access

Browse

  • By Company
  • By Role
  • By Category
  • Topic Hubs
  • SQL Questions
  • Compare Platforms
  • Discord Community

Support

  • support@prachub.com
  • (916) 541-4762

Legal

  • Privacy Policy
  • Terms of Service
  • About Us

© 2026 PracHub. All rights reserved.