## Microsoft Interview Question for Software Engineer / Developers

• 0

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

Assuming intervals are sorted.

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

Comment hidden because of low score. Click to expand.
0

@algooz
you also can assume n=2.

Comment hidden because of low score. Click to expand.
0

@algooz
you also can assume n=2.

Comment hidden because of low score. Click to expand.
0

@algooz
you also can assume n=2.

Comment hidden because of low score. Click to expand.
0

algooz
you also can assume n=2.

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

Hi Anonymous,

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

Use segment tree

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

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

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

LOL
its trivial in O(n) ... so the only missing thing is to do it in less then O(N)

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

By an interval tree, it is O(lgn)!

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.

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