Microsoft Interview Question
Software Engineer / Developerslet me write simplistic psudocode for this to begin with.....
Assumtptions:
- all start and end times are +ves
- set of intervals given is unsorted, and is represented as a pair of numbers denoting start and end time.
for each interval I from set of all intervals
if ( Is <= elemnt && Ie >= elemnt )
return I
O(N) solution.
on 2nd look this looks too simple, there might be something missing.
Assuming intervals are sorted.
- algooz April 23, 2008lets say the element in question to be k.
now divide the n intervals in half, Consider n/2 interval to be [a,b]
Now k belongs in the interval [a,b] if (a-x)(b-x) <= 0
if(x > b)
then do binary search in the right side of the intervals of [a,b]
if(x < a)
then do binary search in the left side of the intervals of [a,b]
Complexity would be here O(logn) as is the case with binary search.