Microsoft Interview Question
Software Engineer in TestsCountry: India
Interview Type: In-Person
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 :)
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)
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))
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.
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)
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
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 June 23, 2012