Adobe Interview Question
Computer Scientistsuse 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...
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?
I am guessing the number of pairs involved in the overlapping are asked. Correct me if I'm wrong.
Yes, you are correct. Augmented BST will definitely handle this case. But it won't handle the case of intersecting intervals.
NO its not overlapping intervals. one interval should be totally contained in the other one.
We can take 2 arrays of size n, assuming n pairs of events exist.
- teli.vaibhav July 01, 2012Sort 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.