Hi everyone,

In a FB interview I had a DS&A question:

"Imagine you have a file download manager with given file length that receives a stream of bits defined as intervals.
Every time it receives bits with add(), it returns true / false whether the file transfer has completed:.
Suggest an implementation."

dm = DownloadManager(11)
dm.add([10, 11]) -> false
dm.add([7, 8]) -> false
dm.add([2, 5]) -> false
dm.add([0, 3]) -> false
dm.add([6, 9]) -> true

I messed up the question and didn't get an offer. I have been thinking about the problem since then and wanted to get advice on the best approach.

At first I thought of maintaining a sorted linked list. I would traverse to find an intersecting interval, and traverse left and right to merge all intersecting neighbors. But worst case this would be O(N) to add intervals if the intervals kept increasing.

Then I discovered the idea of BST or interval tree. You store each interval as node in a BST. You use min element i.e. 2 in [2, 5] to traverse the tree. It seems to me add() would now be logN (log N to find an intersecting node). And you would know if tree was complete if there was only one node in tree and it had [0, file length].

But I'm confused about complexity of merging intervals. This tree should only store the "not touching" intervals (disjoint?). So that means that when a new interval overlaps an existing interval, I should merge them. Does this affect the complexity of add()?

E.g. Let's say I get a big interval and traverse to bottom of the left subtree of my tree and find an intersection. The new interval is so big that it covers many intervals in the root's right subtree as well. Does this mean I need to work backwards and merge all parents/children that overlap? Does this mean that an add() could potentially take O(N) (traversing a whole tree)? Do I say that this O(N) is "amortized" across multiple add() calls?