Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Insert interval into given sorted intervals - May 29, 2018 8:40 PM mock interviews - given by a talented young graduate student who went to Google onsite in 2018.
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace InsertIntervalToGivenSortedIntervals
{
class Program
{
static void Main(string[] args)
{
RunTestcase();
}
/// <summary>
/// It is a good idea to work on a simple test case and then design how to implement the algorithm
/// intervals: [1, 3] and [4, 6]
/// inserted interval: [2, 5]
/// how to insert the interval to the above intervals.
/// Iterate the intervals, the current interval overlaps the inserted interval.
/// Make the merged two intervals to new inserted interval, [1, 5].
/// </summary>
public static void RunTestcase()
{
var intervals = new List<int[]>();
intervals.Add(new int[]{1, 3});
intervals.Add(new int[]{4, 6});
var afterInsert = InsertIntervalGivenSortedIntervals(intervals, new int[]{2, 5});
Debug.Assert(afterInsert[0][0] == 1);
Debug.Assert(afterInsert[0][1] == 6);
}
/// <summary>
/// mock interview on May 29, 2018 8:40 PM
/// </summary>
/// <param name="intervals"></param>
/// <param name="inserted"></param>
/// <returns></returns>
public static IList<int[]> InsertIntervalGivenSortedIntervals(IList<int[]> intervals, int[] inserted)
{
if(inserted == null)
{
return intervals;
}
var newOnes = new List<int[]>();
if(intervals == null || intervals.Count == 0)
{
newOnes.Add(inserted);
return newOnes;
}
var length = intervals.Count;
for(int index = 0; index < length; index++)
{
var insertStart = inserted[0];
var insertEnd = inserted[1];
var current = intervals[index];
var currentStart = current[0];
var currentEnd = current[1];
var overlapStart = Math.Max(currentStart, insertStart);
var overlapEnd = Math.Min(currentEnd, insertEnd);
var overlap = overlapEnd > overlapStart; // true
// check if inserted interval is front of current / after current
if(overlap)
{
inserted[0] = Math.Min(insertStart, currentStart);
inserted[1] = Math.Max(insertEnd, currentEnd);
}
else
{
// if inserted interval is front of current
if(insertEnd < currentStart)
{
newOnes.Add(inserted);
inserted = current;
}
else
{
newOnes.Add(current);
}
}
}
//edge case
if(inserted[1] - inserted[0] >0)
{
newOnes.Add(inserted);
}
return newOnes;
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.