## Facebook Interview Question

Software Engineer / Developers**Country:**United States

**Interview Type:**In-Person

Since we know none of the interval overlaps, we can simply store them in a sorted array with information about if this entry is start or end of an interval.

Modify binary search algorithm to return the low index in case of failed search. This will give us the index of key if found else low index. This low index gives us the position of new element to be inserted. For ex:

intervals: [1, 10), [15, 25), [40, 50)

My array has, 1, 9, 15, 24, 40, 49

I want to insert new interval [30,32). Modified binary search will give position of 40. We need to verify that the 40 is start and 24 is end ..ie the two entries don't constitute an interval or else [30, 32) will overlap. if they don't constitute an interval insert [30,32) and push 40, 49. Therefore insertion is linear in worst case.

Search and delete would work similarly

We need to design a data structure:

Inserting an interval

Find if a point P belong to any interval

Delete an interval

Let's say we use balanced binary search tree:

Inserting an interval O(logn)

Find if a point P belong to any interval O(logn)

Delete an interval O(logn)

```
class Node{
double value;
int color; //1 for white, -1 for black
public Node(double value, int color){
this.value = value;
this.color = color;
}
}
class DataStructure{
BTree root; //Balanced binary search tree [RedBlack, AVL]
int e = 0.00001; //Limit
void insert(double a, double b){
root.insert(new Node(a - e, -1));
root.insert(new Node(a, 1));
root.insert(new Node(b - e, 1));
root.insert(new Node(b, -1));
}
void delete(double a, double b){
root.delete(new Node(a - e, -1));
root.delete(new Node(a, 1));
root.delete(new Node(b - e, 1));
root.delete(new Node(b, -1));
}
boolean find(double point){
//We will find two points in BST which is just smaller and just greater than point.
Node l = root.smaller(point);
Nodr r = root.greater(point);
if(l.color + r.color == 2) //Both are white
return true;
return false;
}
}
```

/*

* Note that insert, delete, smaller, greater of balanced tree can easily

* be implemented in O(logn) time

*/

The question is not really specified. So for a few interpretations:

1) Interval sizes are fixed means to me, that all intervals are of the same size, just as in the example. In that case just use either an unordered_set for space efficiency or a bitarray for more speed. The set only contains the left border of each interval while the array contains a 1 for each present number. Both have O(1) for all operations...

2) Interval can be of variable size. Order by left and right borders in two search trees. Insert/find/delete is log(n). Or use bitarray for efficiency and wasting space...

I think the answer is segment trees... a segment tree is a tree data structure for storing intervals, or segments. It allows querying which of the stored segments contain a given point. It is, in principle, a static structure; that is, its content cannot be modified once the structure is built

I think you are referring to interval trees. Interval tree do have methods to insert and delete in O(lgn). And I believe that's what is this question asking for.

If all intervals are know to be independent and of one fixed size, why not just stored in a BST, and all operations could be done in lgn

- bluesky October 16, 2012