Google Interview Question for Interns


Country: United States




Comment hidden because of low score. Click to expand.
2
of 2 vote

Sort each input array by the first number in the array:
[4, 8], [3, 5], [-1 2], [10, 12] -> [-1 2], [3, 5], [4, 8], [10, 12]

Then compare the last number of an array (L) with the first number (F) of the next array. If L + 1 is strictly < than F, then output the range we have visited so far.

- SK February 08, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I liked this answer the best

import java.util.ArrayList;
import java.lang.Integer;
import java.util.ArrayDeque;
import java.util.Collections;
import java.lang.StringBuilder;


class Bash{

	public static void main( String [] args){
		ArrayList<Pair> pairs = new ArrayList<Pair>();
		pairs.add(new Pair(4, 8));
		pairs.add(new Pair(3, 5));
		pairs.add(new Pair(-1, 2));
		pairs.add(new Pair(10, 12));
		
		System.out.println(minimizeOverlap(pairs));
	}

	static String minimizeOverlap(ArrayList<Pair> pairs){
		ArrayDeque<Integer> result = new ArrayDeque<Integer>();

		if(pairs.size() <= 0) return "[,]";
		
		Collections.sort(pairs);
		StringBuilder str = new StringBuilder();
		Pair first = pairs.remove(0);
		
		str.append("[" + first.getLow());
		int last = first.getHigh();
		int next;
		int highest = 0;
		for(Pair x :pairs){
			
			next = x.getLow();
			if(last < next && Math.abs(next - last) > 1){
				str.append("," + last + "], [" + next);
				last = next;
				highest = x.getHigh();
			}else{
				next = x.getHigh();
				if(last < next){
					last = next;
				}
			}
		}

		str.append("," + highest + "]");
		
		return str.toString();

	}

	static class Pair implements Comparable<Pair>{
		int low;
		int high;

		Pair(int x, int y){
			high = y;
			low = x;
		}

		int getLow(){
			return low;
		}

		int getHigh(){
			return high;
		}

		public String toString(){
			return "[" + low + "," + high + "]";
		}

		public int compareTo(Pair o){
			
			if(low < o.getLow()) return -1;
			if(low > o.getLow()) return 1;

			return 0;
		}
	}
}

- Pumphouse February 17, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Idea in python

# your code goes here

def sort_by_first(x):
	return sorted(x, key=lambda first: first[0])
	
data = [[1, 5], [10, 20]]
sorted_list = sort_by_first(data)
print sorted_list
x = sorted_list[0][0]
print_last = 1
for i in xrange(1, len(sorted_list)):
	if int(int(sorted_list[i-1][1]) + 1) < int(sorted_list[i][0]):
		print x, sorted_list[i-1][1]
		x = sorted_list[i][0]
	else:
		#find if part of previous thing
		if i == len(sorted_list)-1:
			if int(int(sorted_list[i-1][1]) + 1) >= int(sorted_list[i][0]):
				print x, sorted_list[i][1]
			else:
				print sorted_list[i]
if x == sorted_list[len(sorted_list)-1][0]:
	print sorted_list[len(sorted_list)-1]

- aka October 19, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Based on the suggestion python code:

def sort_by_first(x):
	return sorted(x, key=lambda first: first[0])
	
data = [[1, 5], [10, 20]]
sorted_list = sort_by_first(data)
print sorted_list
x = sorted_list[0][0]
print_last = 1
for i in xrange(1, len(sorted_list)):
	if int(int(sorted_list[i-1][1]) + 1) < int(sorted_list[i][0]):
		print x, sorted_list[i-1][1]
		x = sorted_list[i][0]
	else:
		#find if part of previous thing
		if i == len(sorted_list)-1:
			if int(int(sorted_list[i-1][1]) + 1) >= int(sorted_list[i][0]):
				print x, sorted_list[i][1]
			else:
				print sorted_list[i]
if x == sorted_list[len(sorted_list)-1][0]:
	print sorted_list[len(sorted_list)-1]

- aka October 19, 2015 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

Sort first with start point and output when there is a gap:

#include <stdio.h>
#include <stdlib.h>

int main(void)
{
        int i, j, o, s, e, n = 4;
        int start[] = {4, 3, -1, 10};
        int end[] = {8, 5, 2, 12};
        int os[4], oe[4];

        /* insert-sort first */
        for (i = 1; i < n; i++) {
                s = start[i];
                e = end[i];
                for (j = i; j > 0; j--) {
                        if (s >= start[j-1])
                                break; /* found */
                        start[j] = start[j-1];
                        end[j] = end[j-1];
                }

                start[j] = s;
                end[j] = e;
        }

        /* output data */
        o = s = 0;
        for (i = 1; i < n; i++) {
                if (start[i] > end[i-1] + 1) {
                        /* output and update */
                        os[o] = start[s];
                        oe[o++] = end[i-1];

                        s = i; /* start a new one */
                        continue;
                }
        }
        os[o] = start[s];
        oe[o++] = end[i-1];

        for (i = 0; i < o; i++)
                printf("[%d,%d] ", os[i], oe[i]);
        printf("\n");
        return 0;
}

- thomas February 08, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

for i in range(len(intervals)):
 j = i + 1
while j < len(intervals):
	if intervals[i][1] + 1 == intervals[j][0]:
		# consecutive case
		intervals[i][1] = intervals[j][1]
        	intervals.pop(j)
 	elif intervals[i][0] <= intervals[j][0] and intervals[i][1] \
                                   >= intervals[j][0]:
                 # overlap case
                 if intervals[j][1] <= intervals[i][1]:
                     intervals.pop(j)
                else:
                    intervals[i][1] = intervals[j][1]
                     intervals.pop(j)
             else:
                 break

return intervals

- Anonymous February 09, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

for i in range(len(intervals)):
 j = i + 1
while j < len(intervals):
	if intervals[i][1] + 1 == intervals[j][0]:
		# consecutive case
		intervals[i][1] = intervals[j][1]
        	intervals.pop(j)
 	elif intervals[i][0] <= intervals[j][0] and intervals[i][1] \
                                   >= intervals[j][0]:
                 # overlap case
                 if intervals[j][1] <= intervals[i][1]:
                     intervals.pop(j)
                else:
                    intervals[i][1] = intervals[j][1]
                     intervals.pop(j)
             else:
                 break

return intervals

- TheSighing February 09, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

My methodology was to:
1. Generate each range of integers
2. Add the ranges to a python set (that way you have unique integers)
3. Sort the python set into a list
4. Walk the sorted list
a. if there's a difference between adjacent elements > 1
then print the two elements separated by a "], [" string
b. if it's the beginning or end of the list,
then print a '[' + the element or print a ']' + the element

def minimumOverlap(listOfIntervals):
    
    intSet = set()
    for intervalList in listOfIntervals:
        integerRange = range(intervalList[0], intervalList[1] + 1)
        listOrderedSets = []
        for integer in integerRange:
            intSet.add(integer)

    intList = sorted(intSet)

    string = ""
    for i in range(len(intList) ):
        if i == 0:
            string += '[' + str(intList[i]) 
        elif i == len(intList) - 1: 
            string += ', ' + str(intList[len(intList) - 1]) + ']'

        if intList[i] - intList[i-1] > 1:
            string += ', ' + str(intList[i-1]) + '], [' + str(intList[i]) 

    print(string)

# Test it out with this set of intervals
ls = [[4, 8], [3,5], [-1, 2], [10, 12], [32, 40], [34, 36], [10, 19]]
minimumOverlap(ls)

- Nii Mante February 09, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

A solution used Collections sort.

class Pair implements Comparable<Pair> {
	int start;
	int end;
	
	Pair(int start, int end) {
		this.start = start;
		this.end = end;
	}
	
	public int compareTo(Pair p) {
		return this.start - p.start;
	}
	
	public static List<Pair> minimizePairs(List<Pair> list) {
		List<Pair> result = new ArrayList<Pair>();
		Collections.sort(list);
		int head = 0;
		
		for (int i = 1; i < list.size(); i++) {
			if (list.get(i).start - list.get(i-1).end > 1) {
				result.add(new Pair(list.get(head).start, list.get(i-1).end));
				head = i;
			}
		}
		
		// put the rest
		result.add(new Pair(list.get(head).start, list.get(list.size()-1).end));
		return result;	
	}
}

- Anonymous February 09, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Answer given by SKOR works perfectly, we can insert pairs into an std:set which will take care of sorting, below is the c++ code:

#include "stdafx.h"
#include "stdio.h"
#include "conio.h"
#include <vector>
#include <set>

using namespace std;

struct MinMax
{
	int min_val;
	int max_val;
};

struct comparer
{
	bool operator() ( const MinMax& a, const MinMax& b )const
	{
		return ( a.min_val <= b.min_val ) ? true : false ;
	}
};

std::set<MinMax,comparer> myset;

int _tmain(int argc, _TCHAR* argv[])
{
	MinMax min_max, new_min_max;

	min_max.min_val = 4;
	min_max.max_val = 8;
	myset.insert( min_max );

	min_max.min_val = 3;
	min_max.max_val = 5;
	myset.insert( min_max );

	min_max.min_val = -1;
	min_max.max_val = 2;
	myset.insert( min_max );

	min_max.min_val = 10;
	min_max.max_val = 12;
	myset.insert( min_max );

	std::set<MinMax,comparer>::iterator iter;

	min_max = *myset.begin();
	for ( iter = myset.begin() ; iter != myset.end() ; ++iter )
	{
		new_min_max = *iter;

		//check for overlap
		if ( new_min_max.min_val <= min_max.max_val + 1 )
		{
			min_max.max_val = new_min_max.max_val;
		}
		else // no overlap
		{
			printf("(%d:%d) ", min_max.min_val, min_max.max_val );
			min_max = new_min_max;
		}
	}
	
	printf("(%d:%d) ", min_max.min_val, min_max.max_val );

	printf("\n");

	getch();

	return 0;
}

- koosha.nejad February 10, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

ideone.com/vOamQL

- tazo February 10, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Test Input: [4, 8], [3, 5], [-1 2], [10, 12]
Sort everything as below in an array: 'e' stand for end and 's' stand for start
[-1s 2e 3s 4s 5e 8e 10s 12e]
so we need to find consecutive and adjacent. Start from 0th index in array and look for end.
-1s matches with 2e [we found start and end]
then we see 3s and after that we see 4s so we know we can continue as both are consecutive then we look at 5e so we matched 3s with 5e but we had seen 4s which means that we again have to look for one "e" so we went till 8e.
[-1, 8] is the first answer.
After that we saw 10s which started a new interval and we matched that with 12e
[10, 12]
Look at the sorted array and look at the answer you will get the logic. Please comment if you don't understand and i will probably provide some more explanation but I may be missing some test cases which i didn't think about :)

- aka February 11, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

My solution in python in a different approach without sorting.

def PointInLine(line, point):
  if point >= line[0] and point <= line[1]:
    return True
  else:
    return False
    
def OverlapLineHelper(line1, line2):
  check1 = PointInLine(line1, line2[0])
  check2 = PointInLine(line1, line2[1])

  if check1 and check2:
    return line1
  elif check1:
    return [line1[0], line2[1]]
  elif check2:
    return [line2[0], line1[1]]
  else:
    return None
    
def OverlapLine(line1, line2):

  line = OverlapLineHelper(line1, line2)
  
  if line == None:
    return OverlapLineHelper(line2, line1)
  else:
    return line


set = [[4,8], [3,5], [-1,2], [10,12]]
newset = []

while len(set) != 0:
  test = set.pop()
  
  removeset = []
  
  for i, k in enumerate(set):
    check = OverlapLine(k, test)
    if check != None:
      test = check
      removeset.append(i)

  for i in reversed(removeset):
    del set[i]
      
  newset.append(test)
    
print newset

- hiuhchan February 12, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.Arrays;
import java.util.HashMap;


public class Solution {

	
	static int[] starts = {4, 3, -1, 10};
	static int[] ends= {8, 5, 2, 12};
	
	/* Test Input: [4, 8], [3, 5], [-1 2], [10, 12] 
		Test ouput: [-1, 8], [10,12]
	*/
	public static void printIntervals()
	{
		HashMap<Integer,Integer> map =  fillMAp();
		Arrays.sort(starts);
	//	System.out.print(start[0]);
		int start = starts[0];
		int end = map.get(start);
		int startInterval = starts[0];
		int endInterval = map.get(start);	
		
		for(int i = 1 ; i < starts.length ; i++)
		{
			if (starts[i] > map.get(start) + 1)
			{
				System.out.println("[ " + startInterval + " , " + end + " ]");
				start = starts[i];
				startInterval = starts[i];
				end = map.get(start);
			}
			
			if (map.get(starts[i]) > end )
			{
				end = map.get(starts[i]);
			}
			
				start  = starts[i];
			
		}
		System.out.println("[ " + startInterval + " , " + end + " ]");
	}
	
	
	private static HashMap<Integer,Integer> fillMAp() {
		HashMap<Integer,Integer> map = new HashMap<Integer,Integer>();
		for(int i = 0 ; i < starts.length ; i++)
		{
			map.put(starts[i], ends[i]);
		}
		return map;
	}


	public static void main(String[] args) {
		
		printIntervals();

	}

}

- justME February 12, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.Arrays;
import java.util.HashMap;


public class Solution {

	
	static int[] starts = {4, 3, -1, 10};
	static int[] ends= {8, 5, 2, 12};
	
	/* Test Input: [4, 8], [3, 5], [-1 2], [10, 12] 
		Test ouput: [-1, 8], [10,12]
	*/
	public static void printIntervals()
	{
		HashMap<Integer,Integer> map =  fillMAp();
		Arrays.sort(starts);
	//	System.out.print(start[0]);
		int start = starts[0];
		int end = map.get(start);
		int startInterval = starts[0];
		int endInterval = map.get(start);	
		
		for(int i = 1 ; i < starts.length ; i++)
		{
			if (starts[i] > map.get(start) + 1)
			{
				System.out.println("[ " + startInterval + " , " + end + " ]");
				start = starts[i];
				startInterval = starts[i];
				end = map.get(start);
			}
			
			if (map.get(starts[i]) > end )
			{
				end = map.get(starts[i]);
			}
			
				start  = starts[i];
			
		}
		System.out.println("[ " + startInterval + " , " + end + " ]");
	}
	
	
	private static HashMap<Integer,Integer> fillMAp() {
		HashMap<Integer,Integer> map = new HashMap<Integer,Integer>();
		for(int i = 0 ; i < starts.length ; i++)
		{
			map.put(starts[i], ends[i]);
		}
		return map;
	}


	public static void main(String[] args) {
		
		printIntervals();

	}

}

- justME February 12, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

O(nlogn) solution

class xyz{
        public static void main(String args[]){
                point arr[] = { new point( 4,8 ),
                                new point( 3, 5 ),
                                new point( -1,2 ),
                                new point(9,12),
                                new point(13,15) };

                Arrays.sort( arr );
                Queue<point> q = new LinkedList<point>();
                point p1 = arr[0];

                for( int i = 1 ; i < arr.length ; i++ ){
                        point p2 = arr[i];
                        if( p1.y+1 >= p2.x )
                                p1.y = p2.y;
                        else{
                                q.add(p1);
                                p1 = p2;
                        }
                }
                q.add(p1);

                for( point z : q ){
                        System.out.println( z.x + " " + z.y );
                }

        }
}

class point implements Comparable<point>{
        int x ;
        int y;
        public point( int x, int y ){
                this.x = x;
                this.y = y;
        }

        @Override
        public int compareTo( point p ) {
                return this.x - p.x;
        }
}

- Source February 14, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

intervals = [[4, 8], [3, 5], [-1, 2], [10, 12]]
        starts = [(a[0], 1) for a in intervals]
        ends = [(a[1], -1) for a in intervals]
        events = starts + ends
        events.sort(key=lambda x: x[0])
        print(events)
        merged = []
        sum = 1
        interval_start = events[0][0]
        for event in events[1:]:
            if sum == 0:
                interval_start = event[0]
            sum += event[1]
            if sum == 0:
                if len(merged)>0 and merged[-1][1] + 1 == interval_start:
                    merged[-1][1] = event[0]
                else:
                    merged.append([interval_start, event[0]])
        print(merged)

- Alex February 14, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

ArrayList<Interval> minimizeInterval(ArrayList<Interval> inp)
    {

        ArrayList<Interval> res=new ArrayList<Interval>();
        int len=inp.size();

        if(len==0)
            return res;

        Collections.sort(inp,new Comparator<Interval>(){
            public int compare(Interval I1, Interval I2)
            {
                return I1.start-I2.start;
            }
        });
        //
        //
        int start=inp.get(0).start;
        for(int i=1;i < len;i++)
        {
            if(inp.get(i).start >  (inp.get(i-1).end+1))
            {
                Interval obj=new Interval(start,inp.get(i-1).end);
                res.add(obj);
                start=inp.get(i).start;
            }
        }
        Interval obj=new Interval(start,inp.get(len-1).end);
        res.add(obj);
        return res;

    }

- Mir February 16, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def getkey(pair):
    return pair[0]

def merge(pairs):
    # sort the pairs in ascending order by their first value
    pairs.sort(key=getkey)
    
    current = 0
    while current + 1 < len(pairs):
        high     = pairs[current][1]
        lowNext  = pairs[current+1][0]
        highNext = pairs[current+1][1]
        
        # merge pairs that overlap (ie. (1,3)(4,5) -> (1,5))
        if high >= lowNext - 1:
            pairs[current][1] = high if (high > highNext) else highNext
            pairs.pop(current+1)
        else:
            current += 1
 
pairs = [[4,8], [3,5], [-1,2], [10,12]]
merge(pairs)
print pairs

- adam February 22, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Hey chudir-vai, nice username.

- whocares March 15, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

a = [(4, 8), (3, 5), (-1, 2), (10, 12)]

a.sort ()

b = [a[0]]
for al, ar in a[1:]:
        bl, br = b[-1]
        if al <= br:
                b[-1] = (bl, ar)
        else:
                b.append ((al, ar))

print (b)

- jan March 22, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Use the similar idea as the sweep line algorithm.

Pseudo-code:

- 1. Group lower bounds and upper bounds as {X1, ..., Xn} and {Y1, ..., Yn}
    - 2. Sort lower and upper bounds in ascending order as {L1, ..., Ln} and {U1, ..., Un}
    - 3. Take LowerBound = L1 as the lower bound of the first interval
    - 4. Compare Li+1 and Ui where i ranges from 1 to N-1
        * 4.1 if Li+1 > 1 + Ui, then 
                 construct the interval with Ui as the upper bound, [LowerBound, Ui]
                 update LowerBound = Li+1
                 go to Step 4.3
        * 4.2 if i = N - 1, then
                 construct the interval with Un as the upper bound, [LowerBound, Un]
                 Terminate the program
        * 4.3 Increment i by 1 and repeat Step 4

Example:

Let's take a look at the example: [4, 8], [3, 5], [-1 2], [10, 12]
The sorted lower and upper bounds are,
    - Lower bounds: {-1, 3, 4, 10}
    - Upper bounds: { 2,  5, 8, 12}
Here is the algorithm runs
    - Take -1 as the lower bound of the first interval
    - Ui = 2, Li+1 = 3, where  i = 1. it is a CONTINUOUS case and continue
    - Ui = 5, Li+1 = 4, where i = 2, it is a OVERLAP case and continue
    - Ui = 8, Li+1 = 10, where i = 3, this is none of above cases
        * The first interval stops her as [-1, 8]
        * The second interval starts here with lower bound as 10
    - Reach the end, construct the second interval with the upper bound of Un, [10, 12]

Follow this link: cpluspluslearning-petert.blogspot.co.uk/2015/04/data-structure-and-algorithm-find.html, for more details.

- peter tang April 28, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

My python solution

def mininterval(L):
        L = quicksort(L)
        i = 0
        result = []
        for ele in L:
            if i == 0:
                i +=1
                prev = ele
                result.append(ele)
                continue
            if ele[0] <= prev[1]+1:
                result.append((result[-1][0],ele[1]))
                del(result[-2])
                prev = ele
            else:
                result.append(ele)
                prev = ele
        return result

    def quicksort(L):
        left = []
    right = []
        if len(L)<=1:
            return L
        if len(L) == 2:
            if L[0][0]<L[1][0]:
                return L
            else:
                return [L[1],L[0]]
        else:
            i = (len(L)+1)//2-1
            for ele in L:
                if ele[0] <= L[i][0]:
                    left.append(ele)
                else:
                    right.append(ele)
        return quicksort(left)+ quicksort(right)


    a = [(4,8),(3,5),(-1,2),(10,12)]
    print(mininterval(a))

- Anonymous October 19, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

My python solution

def mininterval(L):
        L = quicksort(L)
        i = 0
        result = []
        for ele in L:
            if i == 0:
                i +=1
                prev = ele
                result.append(ele)
                continue
            if ele[0] <= prev[1]+1:
                result.append((result[-1][0],ele[1]))
                del(result[-2])
                prev = ele
            else:
                result.append(ele)
                prev = ele
        return result

    def quicksort(L):
        left = []
    right = []
        if len(L)<=1:
            return L
        if len(L) == 2:
            if L[0][0]<L[1][0]:
                return L
            else:
                return [L[1],L[0]]
        else:
            i = (len(L)+1)//2-1
            for ele in L:
                if ele[0] <= L[i][0]:
                    left.append(ele)
                else:
                    right.append(ele)
        return quicksort(left)+ quicksort(right)


    a = [(4,8),(3,5),(-1,2),(10,12)]
    print(mininterval(a))

- zjhzyrz October 19, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Python Code:

def intervals(A):
	A = sorted(A)
	low = A[0][0]
	high = A[0][1]
	current = 0
	merge = [False for i in range(len(A))]
	for i in range(1,len(A)):
		if((A[i][0]>low and A[i][0]<high)or(A[i][1]>low and A[i][1]<high)or(A[i][1]+1==low)or(A[i][0]-1==high)):
			merge[current] = True
			merge[i] = True
			if(A[i][0]<low):
				low = A[i][0]
			elif(A[i][1]>high):
				high = A[i][1]
		else:
			current = i
			low = A[i][0]
			high = A[i][1]
				
	result = []
	for i in range((len(A))):
		if merge[i]==False:
			result.append(A[i])
	result.append([low,high])
	result = sorted(result)
	return result

A = [[10,15],[4,8],[16,20],[21,32]]
print intervals(A)

- nationdie November 26, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def minimize_interval(a):
    d = {}
    for i in range(len(a)):
        #print(i)
        if a[i][0] in d.keys():
            d[a[i][0]].append(a[i])
        else:
            d[a[i][0]] = [a[i]]
    #print(d.keys())
    sorted_keys = mergeSort(d.keys())
    #print(sorted_keys)
    a = []
    for i in range(len(sorted_keys)):
        for j in range(len(d[sorted_keys[i]])):    
            a.append(d[sorted_keys[i]][j])
    #print(a)
    interval = a[0]
    for i in range(1,len(a)):
        if a[i][0]==interval[1]+1:
            interval[1] = a[i][1]
        elif a[i][0]<interval[1] and a[i][1]>interval[1]:
            interval[1] = a[i][1]
        elif a[i][0] > interval[1]+1:
            print(interval),
            interval = a[i]
        if i==len(a)-1:
            print interval

a = [[4, 8], [4, 7], [3, 5], [-1, 2], [10, 12]]
minimize_interval(a)

- vishal.gupta4081 December 19, 2016 | Flag Reply


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