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