## Microsoft Interview Question for Interns

• 0

Country: India

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

sort the input set according to finish time in monotonically non-decreasing order.
Basically it is greedy algorithm where we are making sure that finishing time of
the set should be the least so that we can get the maximum non-overlapping intervals.
You can read more on this in "Introduction-Algorithms-Edition-Thomas-Cormen"

Take the finishing time of first set and compare that with rest of the set. If any other set is compatible i.e. starting time is more than finishing time
of first set then add to result. Now make the compatible set as current set and do the same.
's' is array of starting time and 'f' finishing time

``````func(s, f)
{
n = s.length
A = a1
k = 1
for (m =2 to n) {
if (s[m] >= f[k]) {
A = A union { a[m] }
k = m
}
}
return A
}``````

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

Here is the algorithm one can follow

``````S <- Input set
End_time = 0;
Subset_count = 0;
SubSet = {}
Sort the S with non decreasing order of end time
While exists at least one interval whose starttime > end_time
element <- Take the first in (non decreasing) order of end time
Subset_count ++;
End_time = End_time of the element``````

Complexity : O(NlogN)
Time : O(1) or O(Result)

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

What if we sort on basis of start time
Would it work ?

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

no, it would not, try this
{{1-10},{2-4}{5-8}}
if start with start time, we will only return 1 element, but the answer is 2 (can be found using endtime sorting)

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

this is a classical greedy algorithm on finding the largest set of nonoverlapping intervals

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

Here is the C# code for it.

Define the Intervals

``````public class Interval
{
public int intervalStart;
public int intervalEnd;

public override string  ToString()
{
return string.Format("( Interval start at: {0}, IntervaleEnd at: {1} )", intervalStart.ToString(), intervalEnd.ToString());
}
}``````

Here is the subroutine to find out the max subset.

``````public static void FindMaxIntervals(Interval[] intervals)
{
if (intervals == null)
throw new Exception("intervals object undefined");
int length = intervals.Length;
for(int i = 0 ; i < length;i++)
{
if (intervals[i] == null)
throw new Exception(string.Format("{0}th interval is undefined", i));
}
Array.Sort<Interval>(intervals, delegate(Interval interval1, Interval interval2) { return interval1.intervalEnd.CompareTo(interval2.intervalEnd); });
//for (int i = 0; i < intervals.Length; i++)
//{
//    Console.WriteLine(intervals[i].ToString());
//}

int intervalCount = 1;
int currentIntervalEnd = intervals[0].intervalEnd;
Console.WriteLine(intervals[0].ToString());
for (int i = 1; i < intervals.Length;i++)
{
if(intervals[i].intervalStart >= currentIntervalEnd)
{
intervalCount++;
currentIntervalEnd = intervals[i].intervalEnd;
Console.WriteLine(intervals[i].ToString());
}
}
Console.WriteLine("Count : {0}", intervalCount);
}``````

Here is the main method to generate the random intervals

``````public static void Main(string[] args)
{
Interval[] intervals = new Interval[10];
var rand = new Random();
for(int i = 0; i < 10; i++)
{
int j = rand.Next(0, 10);
intervals[i] = new Interval() { intervalStart = rand.Next(0, 20) - 5, intervalEnd = rand.Next(20, 40) - 5 };
}
FindMaxIntervals(intervals);
}``````

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

The idea follows:
1. use sweep line algorithm to find how many interval overlaps with each other.
2. use the number of overlap of intervals as the cost function. And Employ the steepest descent algorithm to remove the intervals with the largest number of intervals.

It is to remove the least intervals to guarantee the left intervals are not overlapped with each other. Therefore guarantee that S' is one of the maximal non-overlap subset of S.

Details follow: cpluspluslearning-petert.blogspot.co.uk/2015/06/data-structure-and-algorithm-find_19.html

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

An example is provied as well

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.