Facebook Interview Question for Software Engineer / Developers

• 0

Country: United States
Interview Type: In-Person

Comment hidden because of low score. Click to expand.
2
of 2 vote

``````basically using array of struct pointer.
//pseudo code
Struct Node {
int begin; //end can be inferrred due to fixed size and contiguous.
}
Struct*[] arr; //array of struct pointers.
int size = 10; //fixed given size

void insert(int begin) {
if(arr[begin] == null && arr[begin+size] == null) {
Struct s = new Struct();
s.begin = begin;
for(int i = 0; i <size; i++) {
arr[i+begin] = s;
}

}else {
raise "Cannot be inserted"
}
}

Struct* find(int v) {
return arr[v]
}

void delete(v) { //assuming v is the begin
for(int i=0; i < size; i++) {
arr[i+v] = null;
}
}``````

Comment hidden because of low score. Click to expand.
2

this appears to have a huge space complexity.. if the range is 100 , storing 100 elements would require you 10000 space.

I think BST is the best solution here !

Comment hidden because of low score. Click to expand.
1
of 1 vote

Disadvantages: Searching a particular interval O(n)

``````class IntervalNode
{
int start;
int end;
IntervalNode next
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

As they are not overlapped, so they are stored in the order. A structure having random access will boost the find() algorithm. Depending on how much operations of deleting and inserting a list may/may not used.

Comment hidden because of low score. Click to expand.
0
of 0 vote

I dont see the need to create fancy data structures to handle such simple requirements. why not create an array of the size of the range of interest, and initialize the array members to say 1. Then, simply "zero" the members of an interval inserted.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

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
*/

Comment hidden because of low score. Click to expand.
0
of 0 vote

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...

Comment hidden because of low score. Click to expand.
-1
of 3 vote

balanced binary search tree

Comment hidden because of low score. Click to expand.
-1
of 1 vote

We could use HashMaps as well.

Comment hidden because of low score. Click to expand.
0

Why is this downvoted?

Comment hidden because of low score. Click to expand.
-2
of 4 vote

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

Comment hidden because of low score. Click to expand.
0

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
1
of 1 vote

Interval trees are used to find intersection. Here we know none of the interval is overlapping. Interval trees would be overkill.

Comment hidden because of low score. Click to expand.

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.