How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

What difficulty level is this interview question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Fireworks Ai.

What role is this question designed for?

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

Find global GPU idle intervals | Fireworks Ai Interview Question

Q: Find global GPU idle intervals

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.

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.)

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.)

Find global GPU idle intervals

Quick Overview

Find global GPU idle intervals

Part 1 (batch)

Part 2 (streaming)

Submit Your Answer to Earn 20XP

Find global GPU idle intervals

Quick Overview

Find global GPU idle intervals

Part 1 (batch)

Part 2 (streaming)

Submit Your Answer to Earn 20XP