Interview Questions

  • View all interview questions
  • blank
  • Insert an interval into a list of sorted disjoint intervals
    This is a common interview question where the input is a sorted list of disjoint intervals, and your goal is to insert a new interval and merge all necessary intervals returning a final new list. For example, if the interval list is [[1,5], [10,15], [20,25]] and you need to insert the interval [12,27], then your program should return the new list: [[1,5], [10,27]].

    Algorithm

    This seems like a question that would require a lot of code, but the solution is actually quite simple because the array of intervals is already sorted for us. (1) Create an array where the final intervals will be stored. (2) Push all the intervals into this array that come before the new interval you are adding. (3) Once we reach an interval in the array that comes after the new interval, add our new interval to the final array. (4) From this point, check each remaining element in the array and determine if the intervals need to be merged.

    Example

    intervals = [[1,5], [10,15], [20,25]] insert = [12,27] final = [] Begin looping through the array: 1st interval = [1,5] This interval comes before [12,27] so just add it to final. final = [[1,5]] 2nd interval = [10,15] This interval overlaps with our interval, [12,27], because 12 is between 10 and 15. So add the new interval to final. final = [[1,5], [12,27]] Now we check each remaining interval in the array and determine if we can merge somehow. 2nd interval = [10,15] This interval overlaps with the last element in final, so merge by taking the minimum start interval and maximum end interval. Minimum of (10, 12) and maximum of (15, 27) gives us: [10,27]. Now replace the last interval in final with this merged interval. final = [[1,5], [10,27]] 3rd interval = [20,25] This interval overlaps with the last element in final, so merge by taking the minimum start interval and maximum end interval. Minimum of (10, 20) and maximum of (27, 25) gives us: [10,27]. Now replace the last interval in final with this merged interval. final = [[1,5], [10,27]] No more intervals in the original array, so: final = [[1,5], [10,27]].

    Code

    function insertInterval(arr, interval) {
      
      var newSet = [];
      var endSet = [];
      var i = 0;
    
      // add intervals that come before the new interval
      while (i < arr.length && arr[i][1] < interval[0]) {
        newSet.push(arr[i]);
        i++;
      }
    
      // add our new interval to this final list
      newSet.push(interval);
    
      // check each interval that comes after the new interval to determine if we can merge
      // if no merges are required then populate a list of the remaining intervals
      while (i < arr.length) {
        var last = newSet[newSet.length - 1];
        if (arr[i][0] < last[1]) {
          var newInterval = [Math.min.apply(null, [last[0], arr[i][0]]), Math.max.apply(null, [last[1], arr[i][1]])];
          newSet[newSet.length - 1] = newInterval;
        } else {
          endSet.push(arr[i]);
        }
        i++;
      }
    
      return newSet.concat(endSet);
      
    }
    
    insertInterval([[1,5],[10,15],[20,25]], [12,27]); 
    //insertInterval([[6,7]], [1,9]);
    //insertInterval([[6,7]], [1,5]);
    //insertInterval([[1,5]], [6,7]);
    //insertInterval([[1,5],[6,11],[13,20],[40,50]], [12,19]);  
    //insertInterval([[1,5],[10,15],[20,25]], [2,6]); 
    //insertInterval([[1,5],[6,11],[13,20],[25,30],[32,55]], [12,45]); 
    //insertInterval([[1,5],[6,11],[20,22]], [24,45]); 
    
    def insertInterval(arr, interval):
      
      newSet = []
      endSet = []
      i = 0
      
      # add intervals that come before the new interval
      while i < len(arr) and arr[i][1] < interval[0]:
        newSet.append(arr[i])
        i += 1
        
      # add our new interval to this final list
      newSet.append(interval)
      
      # check each interval that comes after the new interval to determine if we can merge
      # if no merges are required then populate a list of the remaining intervals
      while i < len(arr):
        last = newSet[-1]
        if arr[i][0] < last[1]:
          newInterval = [min([last[0], arr[i][0]]), max([last[1], arr[i][1]])]
          newSet[-1] = newInterval
        else:
          endSet.append(arr[i])
        i += 1
          
      return newSet + endSet
      
    print insertInterval([[1,5],[10,15],[20,25]], [12,27]); 
    #print insertInterval([[6,7]], [1,9]);
    #print insertInterval([[6,7]], [1,5]);
    #print insertInterval([[1,5]], [6,7]);
    #print insertInterval([[1,5],[6,11],[13,20],[40,50]], [12,19]);  
    #print insertInterval([[1,5],[10,15],[20,25]], [2,6]); 
    #print insertInterval([[1,5],[6,11],[13,20],[25,30],[32,55]], [12,45]); 
    #print insertInterval([[1,5],[6,11],[20,22]], [24,45]); 
    
    Run Code
    Run Code

    Running time

    This algorithm runs in O(n) time because, in the worst case, we need to insert the new interval to the beginning of the array and then compare and merge every single other interval in the array, but this would still require only one pass through the array.

    Sources

    http://www.glassdoor.com/Interview/Recently-I-attended-the-interview-at-Google-and-I-was-asked-You-are-given-a-sorted-list-of-disjoint-intervals... http://www.careercup.com/question?id=13014685
    mrdaniel published this on 11/24/15 | array, merge, search, Google
    Comments
    Login to submit a comment