## Facebook Interview Question

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

**Interview Type:**In-Person

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.

- bluesky October 16, 2012