Facebook Interview Question for Software Engineer / Developers


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;
 }
}

- bluesky October 16, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
2
of 2 votes

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 !

- tester February 04, 2014 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

GO with Linked List.
Advantages: Inserting, Deleting simpler O(1)
Disadvantages: Searching a particular interval O(n)

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

- Pankaj Gadge October 14, 2012 | Flag Reply
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.

- peter tang October 14, 2012 | Flag Reply
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.

- dustin October 21, 2012 | Flag Reply
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

- Second Attempt November 10, 2012 | Flag Reply
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
*/

- Aayush Bahuguna February 21, 2013 | Flag Reply
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...

- FBNerd February 26, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 3 vote

balanced binary search tree

- yy October 14, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

We could use HashMaps as well.

- mv October 23, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Why is this downvoted?

- Sam November 01, 2012 | Flag
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

- sumeet.kukkar October 15, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I admire your answer, that's great

- cdtsgsz October 17, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- nathan November 10, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- nanny November 10, 2012 | Flag
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.

- Second Attempt November 10, 2012 | Flag
Comment hidden because of low score. Click to expand.


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More