## Microsoft Interview Question for Software Engineer in Tests

• 0

Country: India
Interview Type: In-Person

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

Sort the intervals by lower bound, and for each interval, just check if the next interval begins before the current one ends (return false if that's true anywhere). Data structure? Make an interval a struct of two ints or float or whatever they are, and use an array.

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

@ eugene ...
nice answer dude ..... :)

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

Pretty much the short version of 2). just in this case you do not return the overlapped intervals --> result will be just true or false which actually is the exact idea of the question :)

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

Similar, yes. The difference is that I avoid the extra binary search.

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

1. Min-heap with start times
2. Min-heap with end times
3. Pick min of both heaps, increment some variable X (initialized to 0) if picked is start, decrement if picked is end
4. Iterate, and return true if X > 1, anytime (assuming that's what you are interested in... if specific overlapping intervals are needed then we need to carry around some more info)

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

I can think of 3 solutions:
1.) use augmented interval three - O(nlogn) build time, O(logn) insert and search
2.) sort the sets by lower bound of the interval O(nlogn). Take the high bound of each element and do a binary search for next or equal lower bound element O(nlogn) => Total O(nlogn)
3.) if you know the interval is complete (not sparse) and the difference between max and min elements is small we can count the ranges in array (for every interval we increment the count[i], when finished we check where count[i] > 1 and this is the result) - O(sum(ranges) + (highest - lowest))

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

@gk, can you explain the third one with an example?

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

imagine we have (1,2) (2,3) (4,5). We traverse an int[] A for each interval and count++ for each idx in that interval. So the result a[] will be {0, 1, 2, 1, 1,1} which means that we have an overlap on num 2 since count > 1.

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

interval tree

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

I can think of one approach. First run a loop to ensure that date in an interval ranges from lower to higher[this is a test case].
Now, sort the data in increasing order higher range. nlogn
run a loop & check whether lower of an interval is smaller than the previous higher of interval. If yes, this is the overlapping interval.

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

its fine with if 1(i mean interval) is overlapped with 2 or 4 is overlapped with 5. But not in the case if 1 is overlapped with 2 3 4

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

I think a BST will do this.
If for any interval.. if you have to add a range starting number on left of some node and range ending number on right of some node and viceversa.. then they are overlapping..

If they are not overlapping... both number should fall at the same place(or you can say.. distance between the interval numbers should be zero after you have inserted into BST)

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

What about Map :)

For 2-7, 5-9, 10-20

Map[2] = 7
Map[5] = 9
Map[10] = 20

To Find overlap between X1,X2:
if Map[X1] > X2

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

Set collection would be the better option, you can use intersect operation for 2 different sets to calculate overlaps
ex: set1 = {2,3,4,5,6,7} set2 = { 5,6,7,8,9} set3={10,11,12,13,14,15,16,17,18,19,20}
intersect operation to these sets will give overlap result
ex: set1 with set2 = > {5,6,7} there is an overlap

if you are using .net then HashSet<T> can be used

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

if you can use linq then you can do this ex(C#):

var s1 = new int[] { 2,3,4,5,6,7 };
var s2 = new int[] { 5, 6, 7, 8, 9 };

var r = s1.Where(p => s2.Contains(p)); // result {5, 6, 7}

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.