Interview Question

Software Engineer Interview

Merge sorted, non-overlapping list of intervals with

  another interval [(1,3), (5,10), (12,30)] + (9,31) = [(1,3), (5,31)]
Answer

Interview Answer

2 Answers

0

Do binary search to locate the intervals (along with some logic to see if you are inside or outside an interval)

Henry David Thoreau on Apr 6, 2014
0

Given [ (1,3), (3,5), (7,9), (12,30), (32,42) ] and (9,31)

Starting with 9. Find a set with overlap otherwise append to solution.
Check 9 < 3 No. Sol = [ (1,3) ]
Check 9 < 5 No. Sol = [ (1,3), (3,5) ]
Check 9 < 9 No. Sol = [ (1,3), (3,5), (7,9) ]
Check 9 < 30 Yes.
------> Check 9 < 12 Yes. Sol = [ (1,3), (3,5), (7,9), (9,????) ]
              Check 31 > 30 Yes. Sol = [ (1,3), (3,5), (7,9), (9,????) ], right=31

Check 31 < 32 Yes. Sol = [ (1,3), (3,5), (7,9), (9,31), (32,42) ]

James Choi on Apr 23, 2014

Add Answers or Comments

To comment on this question, Sign In with Facebook or Sign Up