fireworks ai·Software Engineer·Technical Phone Screen
- Design a data structure that tracks busy time intervals for a GPU as tasks arrive in a stream. Each task adds a busy interval, and you need to support efficient insertion with merging of overlapping or adjacent intervals, plus a query that returns the current idle intervals. Target O(log n) insertion using a sorted structure.
“I knew the merge intervals problem but doing it online, as a stream, is a different beast.”