Microsoft Interview Question for Interns


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
    }

- aka[1] June 11, 2015 | Flag Reply
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 ++;
	SubSet.Add(element)
	End_time = End_time of the element

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

- sonesh June 11, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- ash.taunk3 June 12, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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)

- sonesh June 15, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- pavel.em June 15, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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); 
	Console.ReadLine();
}

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);
}

- sonesh June 24, 2015 | Flag
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

- peter tang June 19, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

An example is provied as well

- peter tang June 19, 2015 | Flag


Add a Comment
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.

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