Interview Question

Software Engineer, Google Fiber Interview

-Waterloo, ON

Google

Recently I attended the interview at Google and I was asked "You are given a sorted list of disjoint intervals and an interval, e.g. [(1, 5), (10, 15), (20, 25)] and (12, 27). Your task is to merge them into a sorted list of disjoint intervals: [(1, 5), (10, 27)]."

Tags:technical, google, algorithm, sorting, interval sort, merging
AnswerAdd Tags

Interview Answers

7 Answers

1

You can use line-sweep algorithm for that.

Anonymous on

1

JAVA CODE: import java.util.ArrayList; import java.util.Collections; import java.util.Comparator; import java.util.List; /** * Created by admin on 3/2/16. */ class Interval { int start; int end; Interval() {start = 0;end =0;} Interval(int s, int e) { start = s; end = e; } } public class Solution { public List insert(List intervals, Interval newInterval) { ArrayList result = new ArrayList(); intervals.add(newInterval); return merge(intervals); } public List merge(List intervals) { ArrayList result = new ArrayList(); if (intervals == null || intervals.size() == 0) { return result; } Collections.sort(intervals, new Comparator() { public int compare(Interval a, Interval b) { return a.start - b.start; } }); for (int i=0;i= intervals.get(i+1).start) { current.end = Math.max(current.end, intervals.get(i+1).end); i++; } result.add(current); } return result; } } Time Complexity: nlgn + n = O(nlgn)

lanyijia on

0

int[] mergeDisjointIntervals(int[] intervals, int[] range){ ArrayList result = new ArrayList(); for(int i=0;irange[0]&&high is inside return 0; } else if(lowrange[0]&&high overlaps tail return -1; } else if(low>range[0]&&lowrange[1]){ // 1 -> overlaps head return 1; } else{ // 2 -> does not overlap return 2; } }

Anonymous on

0

int[] mergeDisjointIntervals(int[] intervals, int[] range){ ArrayList result = new ArrayList(); for(int i=0;irange[0]&&high is inside return 0; } else if(lowrange[0]&&high overlaps tail return -1; } else if(low>range[0]&&lowrange[1]){ // 1 -> overlaps head return 1; } else{ // 2 -> does not overlap return 2; } }

Anonymous on

1

First you need to sort the pairs according to their starts. Then we compare each two first pair together if they have intersection or not. if the end of the first pair is greater or equal to beginning of the second pair then they have intersection and it is obviously : start = min(start_first pair, start_second pair), end= max(end_first pair, end_second pair); this new pair will be compared with the next pair.. till the end. if there is not an intersection we leave it az an interval. We can use queue to hold the pairs

shiva on

0

google_interview = ( [(1, 5), (10, 15), (20, 25) ], (12,27) ) just_insert = ( [(1, 5), (10, 15), (20, 25), (80,89)], (17, 18) ) join_case = ( [(1, 5), (10, 15), (20, 25), (80,89)], (12, 22) ) empty_case = ( [], (1,10) ) def merge(orig,anew): """ If the input items are sorted, and interval is a 2-tuple, create a new list of intervals, such that we join together any overlapping intervals into a single tuple describing the combined range of the two or three tuples that could collide when we merge another interval into a list""" newlist = [] if len(orig)==0: return [anew] n = 0 # get items that are before the join while norig[n][0]: middleitem[0] = orig[n][0] if n=orig[n+1][0] and middleitem[1] middleitem[1]: # print "break",orig[n] break if orig[n][1] > middleitem[1]: # print "extend" middleitem[1] = orig[n][1] # print "skip",orig[n] n = n + 1 # now append remaining items newlist = newlist + [tuple(middleitem)] newlist += orig[n:] return newlist def test(tup): print 'merge( '+repr(tup[0])+', '+ repr(tup[1])+ ' )' print ' -> ', merge(tup[0], tup[1] ) print ' ' print "Test begin" test( google_interview ) test( just_insert ) test( join_case ) test( empty_case ) print "Test end"

Warren on

0

n*lgn sorted by lower bound and gogogo scan once.

easy on

Add Answers or Comments

To comment on this, Sign In or Sign Up.