Google Interview Question Software Engineer in Tests
Country: United States
Java implementation
public class MergeIntervals {
class Interval{
double start;
double end;
public Interval(double start, double end) {
this.start = start;
this.end = end;
}
}
public List<Interval> mergeIntervals(List<Interval> nonOverlapInt, Interval another){
List<Interval> merge = new ArrayList<Interval>();
for(Interval current : nonOverlapInt){
if(current.end <= another.start || another.end <= current.start){
merge.add(current);
} else{
another.start = (current.start < another.start) ? current.start : another.start;
another.end = (current.end > another.end) ? current.end : another.end;
}
}
merge.add(another);
return merge;
}
}
I think linear search for entry point and exit point will do...
It would be better if u can provide some more example so that we can come up with algo/code
public static Collection<int[]> overlap(int[][] intervals, int[] otherInterval){
if(intervals.length == 0)
return Collections.emptyList();
List<int[]> result = new ArrayList<int[]>();
boolean found = false;
outter:
for(int i=0; i<intervals.length; i++){
int lowerBound = intervals[i][0];
int upperBound = intervals[i][1];
if(upperBound > otherInterval[0] && !found){
for(int y=i;y<intervals.length;y++){
int _upperBound = intervals[y][1];
if(y != intervals.length - 1){
if(otherInterval[1] >= _upperBound && otherInterval[1] <= intervals[y+1][0]){
result.add(new int[]{Math.min(lowerBound, otherInterval[0]), Math.max(_upperBound, otherInterval[1])});
found = true;
continue outter;
}
}
else{
// if it's the last item, then choose the largest among the upper bound of the interval
// and the upper bound of the other interval
result.add(new int[]{Math.min(lowerBound, otherInterval[0]), Math.max(_upperBound, otherInterval[1])});
found = true;
continue outter;
}
++i;
}
}
result.add(new int[]{lowerBound,upperBound});
}
return result;
}
Works in O(n) time
import java.util.ArrayList;
import java.util.List;
public class MergeIntervals {
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
List<Interval> intervals = new ArrayList<Interval>();
// intervals.add(new Interval(1, 4));
// intervals.add(new Interval(6, 10));
// intervals.add(new Interval(14, 19));
//
// Interval another = new Interval(13, 17);
intervals.add(new Interval(1, 5));
intervals.add(new Interval(6, 15));
intervals.add(new Interval(20, 21));
intervals.add(new Interval(23, 26));
intervals.add(new Interval(27, 30));
intervals.add(new Interval(35, 40));
Interval another = new Interval(14, 33);
List<Interval> result = mergedIntervals(intervals, another);
for(Interval res : result) {
System.out.println(res.getStart() + "," + res.getEnd());
}
}
private static List<Interval> mergedIntervals(List<Interval> intervals, Interval another) {
List<Interval> result = new ArrayList<Interval>();
for(int i = 0; i < intervals.size(); i++) {
Interval interval = intervals.get(i);
if(interval.getStart() < another.getStart() && interval.getEnd() < another.getStart()) {
result.add(interval);
} else if(interval.getStart() > another.getEnd() && interval.getEnd() > another.getEnd()) {
result.add(interval);
} else {
int start = Integer.MIN_VALUE, end = Integer.MIN_VALUE, j;
if(another.getStart() <= interval.getStart()) {
start = another.getStart();
} else if(another.getStart() > interval.getStart()) {
start = interval.getStart();
}
for(j = i + 1; j < intervals.size(); j++) {
Interval next = intervals.get(j);
if(another.getEnd() > next.getStart() && another.getEnd() < next.getEnd()) {
end = next.getEnd();
i = j;
break;
} else if(another.getEnd() > next.getEnd()) {
if((j != intervals.size() - 1) && (intervals.get(j + 1).getStart() > another.getEnd())) {
end = another.getEnd();
i = j;
break;
}
}
}
if(end == Integer.MIN_VALUE && j == intervals.size()) {
end = intervals.get(j - 1).getEnd();
}
result.add(new Interval(start, end));
}
}
return result;
}
}
class Interval {
private int start;
private int end;
public Interval(int start, int end) {
this.start = start;
this.end = end;
}
public int getStart() {
return this.start;
}
public int getEnd() {
return this.end;
}
}
I hope this is correct logic
- Represent all the intervals in a sorted array
- Insert the interval to be merged in this array
- And now keep iterating this array in ascending order
- If the given start Interval is in even position(array starts from 0) then include it
- Ignore all the elements from this position
- If the given end interval is in odd position include it and now stop ignoring the elements of the array
public static void main(String[] args) {
// int list[] = { 1, 4, 6, 10, 14, 19 };
// int low = 13;
// int high = 17; // Ans:(1,4) (6,10) (13,19)
int list[] = { 1, 5, 6, 15, 20, 21, 23, 26, 27, 30, 35, 40 };
int low = 14;
int high = 33;
list = insertAndRemoveDuplicates(list, low, high);
boolean startInterval = false;
for (int i = 0; i < list.length; i++) {
if (!startInterval && list[i] == low) {
startInterval = true;
if (even(i))
sysout(low);
continue;
}
if (startInterval && list[i] == high) {
startInterval = false;
if (!even(i)) {
sysout(high);
}
continue;
}
if (!startInterval)
sysout(list[i]);
}
}
Here is my version which uses binary search to find the first and the last intervals to merge with and does the merging inplace. In the worst case the complexity is O(n) as we may need to remove all intervals except one, however this is better solution than to traverse other all intervals.
#include <iostream>
#include <iterator>
#include <algorithm>
#include <vector>
struct Interval {
int start;
int end;
Interval(int s, int e)
: start(s)
, end(e)
{
}
friend std::ostream& operator<<(std::ostream& out, const Interval& interval)
{
out << "(" << interval.start << ", " << interval.end << ")";
out.flush();
return out;
}
};
typedef std::vector<Interval> Intervals;
int find_interval(const Intervals& list, int elem)
{
int low = 0;
int high = (int)list.size() - 1;
int index = high;
while (low <= high) {
int mid = (low + high) / 2;
if (elem <= list[mid].end) {
index = mid;
}
if (list[mid].end < elem) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return index;
}
void merge_interval(Intervals& list, Interval other)
{
const int begin = find_interval(list, other.start);
int end = find_interval(list, other.end);
list[begin].start = std::min(other.start, list[begin].start);
if (other.end < list[end].start) {
--end;
}
list[begin].end = std::max(other.end, list[end].end);
if (begin < end) {
list.erase(list.begin() + begin + 1, list.begin() + end + 1);
}
}
void print_intervals(const Intervals& list)
{
std::copy(list.begin(), list.end(), std::ostream_iterator<Interval>(std::cout, ", "));
std::cout << std::endl;
}
int main (int argc, const char * argv[])
{
Intervals list;
list.push_back(Interval(2, 5));
list.push_back(Interval(6, 15));
list.push_back(Interval(20, 21));
list.push_back(Interval(23, 26));
list.push_back(Interval(27, 30));
list.push_back(Interval(35, 40));
print_intervals(list);
merge_interval(list, Interval(1, 27));
print_intervals(list);
return 0;
}
public struct Range
{
public int Max;
public int Min;
}
public List<Range> MergeRange(Range[] input, Range target)
{
if (input == null || input.Length == 0)
{
throw new ArgumentException();
}
List<Range> result = new List<Range>();
bool lowerBoundFinds = false;
bool finished = false;
for (int i = 0; i < input.Length; i++)
{
if (finished)
{
result.Add(input[i]);
continue;
}
if (!lowerBoundFinds)
{
if (input[i].Max < target.Min)
{
result.Add(input[i]);
}
else if (target.Max < input[i].Min)
{
result.Add(target);
finished = true;
continue;
}
else if (target.Min <= input[i].Min && target.Max >= input[i].Min
|| target.Min >= input[i].Min && target.Min <= input[i].Max
)
{
target.Min = target.Min <= input[i].Min ? target.Min : input[i].Min;
if (target.Max > input[i].Max)
{
lowerBoundFinds = true;
}
else
{
target.Max = input[i].Max;
result.Add(target);
finished = true;
continue;
}
}
}
else
{
if (target.Max < input[i].Min)
{
result.Add(target);
result.Add(input[i]);
}
else if (target.Max > input[i].Max)
{
continue;
}
else
{
target.Max = input[i].Max;
result.Add(target);
finished = true;
continue;
}
}
}
return result;
}
Test:
/// <summary>
///A test for MergeRange
///</summary>
[TestMethod()]
public void MergeRangeTest()
{
Google1 target = new Google1(); // TODO: Initialize to an appropriate value
Google1.Range[] input = new Google1.Range[]{
new Google1.Range(){Min = 1, Max=5},
new Google1.Range(){Min = 6, Max=15},
new Google1.Range(){Min = 20, Max=21},
new Google1.Range(){Min = 23, Max=26},
new Google1.Range(){Min = 27, Max=30},
new Google1.Range(){Min = 35, Max=40},
};
Google1.Range target1 = new Google1.Range() {Max = 33, Min = 14}; List<Google1.Range> actual;
actual = target.MergeRange(input, target1);
actual.ForEach(m =>
{
Console.WriteLine("{0}, {1}", m.Min, m.Max);
});
}
C# code.
Use priority_queue to store the interval if it not sorted.
Take the first and second, let's say a, b.
If a.second >b.first, merge a b into c. use loop then compare c and third one.
Otherwise, if there is no merge between a and b, output a
code: q is the input queue
interval a=q.top();
q.pop();
interval b;
while(!q.empty())
{
b=q.top();
q.pop();
interval c;
if (a.first<b.first&&a.second>b.first) //merge a&b
{
c=make_pair(a.first,max(a.second, b.second));
a=c;
}
else
{
result.push(a);
a=b;
}
}
result.push(a);
Here is my solution in Python:
from heapq import heappush
from heapq import heappop
from heapq import heapify
def interval_overlapping(array, interval):
if array is None or len(array) < 1:
return False
if interval is None or len(interval) != 2:
return False
heapify(array)
heappush(array, interval)
result = []
# number of elements in queue is at least 2 - checked
while len(array) > 1:
xf, yf = heappop(array)
xs, ys = heappop(array)
if yf < xs:
result.append((xf, yf))
heappush(array, (xs,ys))
else:
x = min(xf, xs)
y = max(yf, ys)
heappush(array, (x,y))
result.append(heappop(array))
return result
Here's mine
public ArrayList<Interval> insert(ArrayList<Interval> intervals, Interval newInterval) {
// Start typing your Java solution below
// DO NOT write main() function
ArrayList<Interval> result = new ArrayList<Interval>();
boolean isOverlapping = true;
if(intervals.size() == 0)
{
result.add(newInterval);
return result;
}
for(int i = 0; i < intervals.size() ; i++)
{
Interval curr = intervals.get(i);
//beginning ones
if(curr.end < newInterval.start)
{
result.add(curr);
}
//end ones
else if(curr.start > newInterval.end)
{
if(isOverlapping)//will only reach here after end of last overlapping one
{
result.add(newInterval);
}
result.add(curr);
isOverlapping = false;
}
else
{
newInterval.start = (newInterval.start < curr.start) ? newInterval.start : curr.start;
newInterval.end = (newInterval.end > curr.end) ? newInterval.end : curr.end;
}
}
if(isOverlapping)
{
result.add(newInterval);
}
return result;
}
C++ simple implement (nlog(n))
My version do not treat the non overlapping intervals and the merging intervals separately, just put them together and sort those intervals. Finally, merge the overlapping intervals.
class Interval {
public:
int start, end;
Interval(int start, int end) {
this->start = start;
this->end = end;
}
bool operator<(const Interval &rhs) const {
if (this->start == rhs.start) {
return this->end < rhs.end;
}
return this->start < rhs.start;
}
};
vector<Interval> foo(vector<Interval> &v) {
sort(v.begin(), v.end());
vector<Interval> r;
Interval cur = v.front();
for (vector<Interval>::iterator i = v.begin() + 1; i != v.end(); i++) {
if (i->end <= cur.end) {
continue;
}
if (i->start <= cur.end) {
cur.end = i->end;
} else {
r.push_back(cur);
cur = *i;
}
}
r.push_back(cur);
return r;
}
private static List<Interval> merge(List<Interval> org, Interval interval) {
org.add(0,interval);
int counter = 1;
while(counter<org.size()){
if(counter+1 <= org.size()){
Interval curr = org.get(counter-1);
Interval next = org.get(counter);
print("Cur "+curr.print()+" : Next "+next.print());
if(curr.start > next.end){
org.set(counter-1, next);
org.set(counter, curr);
}else
if((curr.start<next.start)&&(curr.end>next.end)){
org.remove(counter);
continue;
}else
if(curr.end < next.start){
//Do nothing
}else{
if((curr.start<next.start)&&(curr.end>next.start)){
next.start = curr.start;
}
if((curr.start<next.end)&&(curr.end>next.end)){
next.end = curr.end;
}
org.remove(counter-1);
continue;
}
}
counter++;
}
return org;
}
suggestions appreciated...
#include <iostream>
#include <cmath>
#include <vector>
using namespace std;
struct interval{
int st;
int en;
interval(int _st, int _en){
st = _st;
en = _en;
}
};
interval* merge(interval* a, interval* b){
interval* c = new interval(min(a->st, b->st), max(a->en, b->en));
return c;
}
int main(){
int numMergeInterval = 0;
vector<interval*> allIntervals;
allIntervals.push_back(new interval(1,4));
allIntervals.push_back(new interval(6,10));
allIntervals.push_back(new interval(14,17));
interval* testInterval = new interval(1,19);
for (int i=0; i<allIntervals.size(); i++){
if (testInterval->st > allIntervals.at(i)->en)
continue;
if (testInterval->en < allIntervals.at(i)->st)
continue;
allIntervals.at(i)->st = min(allIntervals.at(i)->st, testInterval->st);
allIntervals.at(i)->en = max(allIntervals.at(i)->en, testInterval->en);
numMergeInterval++;
testInterval = new interval(allIntervals.at(i)->st, allIntervals.at(i)->en);
if (numMergeInterval > 1){
allIntervals.erase(allIntervals.begin() + i-1);
i--;
}
}
for (int i=0; i<allIntervals.size(); i++){
cout<<allIntervals.at(i)->st<<","<<allIntervals.at(i)->en<<endl;
}
}
import java.util.ArrayList;
import java.util.List;
class range{
public int start, stop;
public range(int start, int stop){
this.start=start;
this.stop=stop;
}
}
public class Intervals {
public Intervals(){
}
//new range(13,17)
public List<range> merge(range[] pA, range p){
range tempP=p;
List<range> myList=new ArrayList<range>();
for(range po: pA){
if(IsIntersect(po, tempP)){
tempP=mergeTwoRanges(po, tempP);
if(!IsRangeExist(myList, tempP)){
myList.add(tempP);}
}
else{
if(!IsRangeExist(myList,po)){
myList.add(po);
}
}
}
return myList;
}
public boolean IsRangeExist(List<range> rL, range r){
boolean exist=false;
for(range rr: rL){
if(rr.start==r.start && rr.stop==r.stop){
exist=true;
}
}
return exist;
}
public range mergeTwoRanges(range r1, range r2){
int start, stop;
start=(r1.start<r2.start)? r1.start : r2.start;
stop=(r1.stop>r2.stop)? r1.stop : r2.stop;
return new range(start,stop);
}
public boolean IsIntersect(range p1, range p2){
boolean intersect=false;
if(p1.start<=p2.stop && p2.start<=p1.stop){
intersect=true;
}
return intersect;
}
public static void main(String[] args){
range[] pArr={new range(1,4), new range(6,10), new range(14,19)};
range p=new range(13,17);
Intervals i=new Intervals();
List<range> l= i.merge(pArr, p);
for(range r: l){
System.out.println(r.start+ " "+ r.stop);
}
range[] pArr2={new range(1,5), new range(6,15), new range(20,21), new range(23,26), new range(27,30), new range(35,40)};
range p2=new range(14,33);
List<range> l2= i.merge(pArr2, p2);
System.out.println("second result");
for(range r: l2){
System.out.println(r.start+ " "+ r.stop);
}
}
}
Here is C++ Solution...!!!
#include<iostream>
#include<list>
using namespace std;
struct interval{
interval(){}
interval(int s, int e) :start(s), end(e){}
int start;
int end;
};
void findInterval( list<interval> input, interval other, list<interval>& output){
list<interval>::iterator it;
for (auto l : input)
{
if (l.end <= other.start || other.end <= l.start)
output.push_back(l);
else
{
other.start = (l.start < other.start) ? l.start : other.start;
other.end = (l.end>other.end) ? l.end : other.end;
}
}
output.push_back(other);
}
int main(){
//interval a(1, 4), b(6, 10), c(14, 19), other(13, 17);
interval a(1, 5), b(6, 15), c(20, 21),d(23,26),e(27,30),f(35,40), other(14, 33);
list<interval> input, result;
input.push_back(a);
input.push_back(b);
input.push_back(c);
input.push_back(d);
input.push_back(e);
input.push_back(f);
cout << "Input:\n";
for (auto i : input)
cout << "(" << i.start << ", " << i.end << ")" << endl;
cout << "\nOther:\n";
cout <<"("<< other.start << ", " << other.end << ")" << endl;
findInterval(input, other, result);
cout << "\nOutput:\n";
for (auto i : result)
cout << "(" << i.start << ", " << i.end << ")" << endl;
return 0;
}
#include<stdio.h>
#include<stdlib.h>
void merge(int s[],int f[],int n)
{
int i,j;
int m=n;
for(i=n-1;i>=1;i--)
{
for(j=i-1;j>=0;j--)
{
if(s[i]>s[j] && s[i]<f[j])
{
if(f[j]<f[i])
f[j]=f[i];
f[i]=0;
s[i]=0;
}
else if(s[i]<s[j] && f[j]<f[i])
{
s[j]=s[i];
f[j]=f[i];
s[i]=0;
f[i]=0;
}
else
continue;
}
}
for(i=0;i<m;i++)
{
if(s[i]==0 && f[i]==0)
continue;
printf("Merged overlapping interval is (%d %d)\n",s[i],f[i]);
}
}
int main()
{
int n,i,k,b,m;
scanf("%d",&n);
m=n/2;
int s[m],f[m];
for(i=0,k=0,b=0;i<n;i++)
{
if(i%2==0)
{
scanf("%d",&s[k++]);
}else
scanf("%d",&f[b++]);
}// presume the array is in sorted form of increasing order.
merge(s,f,m);
return 0;
}
here is c code....
#include<stdio.h>
#include<stdlib.h>
void merge(int s[],int f[],int n)
{
int i,j;
int m=n;
for(i=n-1;i>=1;i--)
{
for(j=i-1;j>=0;j--)
{
if(s[i]>s[j] && s[i]<f[j])
{
if(f[j]<f[i])
f[j]=f[i];
f[i]=0;
s[i]=0;
}
else if(s[i]<s[j] && f[j]<f[i])
{
s[j]=s[i];
f[j]=f[i];
s[i]=0;
f[i]=0;
}
else
continue;
}
}
for(i=0;i<m;i++)
{
if(s[i]==0 && f[i]==0)
continue;
printf("Merged overlapping interval is (%d %d)\n",s[i],f[i]);
}
}
int main()
{
int n,i,k,b,m;
scanf("%d",&n);
m=n/2;
int s[m],f[m];
for(i=0,k=0,b=0;i<n;i++)
{
if(i%2==0)
{
scanf("%d",&s[k++]);
}else
scanf("%d",&f[b++]);
}// presume that the code is in sorted form
merge(s,f,m);
return 0;
}
Here is my answer to this question:
- Andy March 12, 2012basicalgos.blogspot.com/2012/03/24-merging-overlapping-intervals.html
If the non-overlapping intervals are sorted, we can solve this within O(n). Otherwise, we can sort them first, and do the merge. The time complexity of the latter scenario is O(nlogn).