Facebook Interview Question
Software Engineer / DevelopersCountry: 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