Microsoft Interview Question Software Engineer in Tests


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.

- eugene.yarovoi on June 23, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- salvo4u on June 23, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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 :)

- GKalchev on June 23, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- eugene.yarovoi on June 23, 2012 | Flag
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)

- sri on July 01, 2012 | Flag Reply
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))

- GKalchev on June 23, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Aashish on June 23, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- GKalchev on June 25, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 2 vote

interval tree

- codez on June 23, 2012 | Flag Reply
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.

- Aashish on June 23, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- upadhyay on February 28, 2013 | Flag
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)

- Siva on June 23, 2012 | Flag Reply
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

- Guru on June 23, 2012 | Flag Reply
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

- srinivasanvee on June 24, 2012 | Flag Reply
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}

- Mariusz on June 25, 2012 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book walking you through getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More