Adobe Interview Question for Computer Scientists






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

We can take 2 arrays of size n, assuming n pairs of events exist.
Sort the first array consisting of start times.
Sort the second array consisting of end times.
Now, just like in the case of merge sort we merge the 2 arrays. But in addition to the merging we maintain a count variable. During the merging if the element is being picked from the first array, it is a start point, so we increment the count as count++. Whenever we pick the from the second array of end points, we decrement the count as count--. At the end of the merging. The count value eventually will be the number of overlaps.

The time complexity is O(nlog)+O(nlogn)+O(n+n) =>O(nlogn)
nlogn for each sort and O(n+n) for the merging.
This gives us a better overall time complexity but I cannot retrieve the pairs with this procedure. Can someone come up with an idea for that.

- teli.vaibhav July 01, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

merging , but how ?? Can u throw some light on it. I mean which value are u using for merging the two arrays??

- BABA July 06, 2012 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

use augmented trees with red-black trees.. check out coremen book. The order of searching if the interval exists or not can be done in O(log n) time...

- amnesiac July 02, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

to find all pairs, find the node in the tree n delete it & again search for the node..

- amnesiac July 02, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 2 vote

we can sort the array of pairs according to their starting points and then we can check from the first pair to see if it has greater ending point then other point . if a pair is found having less ending point we print it. continuing similarly one by one it till the end ...

- A. July 01, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Use Augmented BST where each node will have three child.
An interval with end time less than the start time of the root will serve as the left child.

An interval with start time greater than the start time of the root & end time less then end time of the root will serve as the middle child.

An interval with start time greater than the end time of the root will serve as the right child.

Now insert all intervals in the BST. Print all the middle children.
But the problem is that it won't allow the insertion of the intersecting intervals.Do the presence of intersecting intervals really change the solution?

- Aashish July 01, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

I am guessing the number of pairs involved in the overlapping are asked. Correct me if I'm wrong.

- teli.vaibhav July 01, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Yes, you are correct. Augmented BST will definitely handle this case. But it won't handle the case of intersecting intervals.

- Aashish July 01, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

NO its not overlapping intervals. one interval should be totally contained in the other one.

- itscool July 01, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

to find all pairs, find the node in the tree n delete it & again search for the node..

- amnesiac July 02, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

u could do this using 2d binary index trees

- @hubulu July 02, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

we can use augmented red black tree as an underlying data structure to build interval tree.
In interval tree, overlapping interval can be found in (lg n) time.
Please have a look at following link

staff.ustc.edu.cn/~csli/graduate /algorithms/ book6/ chap15.htm

- Coder July 02, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

use augmented trees with red-black trees.. check out coremen book. The order of searching if the interval exists or not can be done in O(log n) time...

- amnesiac July 02, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Segment tree ??

- bansalnvn September 16, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Make a hasmap of all intervals with slope of line as the key and atore the set of intervals. Now go through each entry in hashmap to find if the interval is contained in another interval

- manan July 01, 2012 | Flag Reply


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