Google Interview Question
InternsCountry: United States
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;
}
}
}
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]
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]
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;
}
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
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
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)
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;
}
}
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;
}
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 :)
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
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();
}
}
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();
}
}
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;
}
}
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)
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;
}
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
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.
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))
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))
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)
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)
Sort each input array by the first number in the array:
- SK February 08, 2015[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.