Google Interview Question for Software Engineer Interns


Country: United States




Comment hidden because of low score. Click to expand.
3
of 5 vote

Sort the pair, and then check each one with its previous one, if its a subset of the previous one dont add, else if the previous one is subset of this one, remove the previous one, and then add this one (regardless).

public class ArrayRangeSubset {

	public static class Pair implements Comparable<Pair>{
		Integer a;
		Integer b;
		public Pair(int a, int b)
		{
			this.a = a;
			this.b = b;
		}
		public boolean isInside(Pair other)
		{
			return (other!=null && 
					other.a <= other.b &&
					other.a <= this.a &&
					other.b >= this.b);
		}
		@Override
		public int compareTo(Pair o) {
			return o.a==this.a?b.compareTo(o.b):
				a.compareTo(o.a);
		}
		
		@Override
		public String toString() {
			return "("+a+", "+b+")";
		}
	}
	public static ArrayList<Pair> smallerSubArray(Pair[] data)
	{
		
		Arrays.sort(data);
		ArrayList<Pair> optList = new ArrayList<Pair>();
		optList.add(data[0]);
		for (int i=1;i<data.length;i++)
		{
			if (!data[i].isInside(optList.get(optList.size()-1))) 
			{
				if (optList.get(optList.size()-1).isInside(data[i])) {
					optList.remove(optList.size()-1);
					
				}
				optList.add(data[i]);
			}
			
		}
		return optList;
	}
	public static void main(String[] args) {
		Pair[] data={  new Pair(3,5), new Pair(2,6),  new Pair(2,8), new Pair(20,21), new Pair(8,20) } ;
		ArrayList<Pair> sm = smallerSubArray(data);
		System.out.println(sm);

	}

}

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

I think this one is a correct solution.

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

You can avoid removing from optList by changing your sort: if o.a==this.a then take the longer range first. This way it can't happen that the coming range contains previous one.

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

Do the ranges strictly include each other or they might overlap only partially, like in this example:
[[2:6], [3:8], [5:20]]?

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

If they were "overlapping only partially", we had nothing to do, because the task asks to remove subarrays. So it's both.

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

What do you mean nothing to do?
in the example we could have minimized it to [[2:20]] because it contains all ranges from original input.
So is the input "[[2:6], [3:8], [5:20]]" valid for this question? Is the task asks to only remove ranges that are completely included in other ranges or to minimize number of ranges so that all numbers from original input are still covered (by smaller number of ranges)?

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

The question asks to remove subarrays. So I would stick to that.

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

This is incorrect solution. For example: [2, 30] [3, 21] [4,26]
In above solution, [4,26] should be absorbed by [2, 30] but the sorted sequence will never compare [4, 26] to [2, 30]

- ashish.kaila October 22, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Sorry I meant [2, 30] [3, 41] [4, 26]

- ashish.kaila October 22, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

No, [4,26] will not be compared to [2,30], but it will be compared to [3,41] and will be ignored, because it's subarray.
The solution is correct.

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

I think the solution has a problem:
Consider the case [2, 4] [3, 6] [5, 8]
The ideal solution should be [2, 4] [5, 8]
But using the above, it will produce [2,4] [3,6] [5, 8]

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

If you need to preserve the subarray then you cannot sort to begin with ! Then it completely invalidates the above solution as it will change the order of entries !

- ashish.kaila October 23, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Anon, what do you mean by "ideal solution"? [2,4] [3,6] [5, 8] is correct solution, no range is contained in another range, so no range is removed.
@ashish.kaila, have you heard of Arrays.copyOf?

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

@damluar: I think the question requires some clarification from the post.
If the solution involves just checking the previous and next subarray, then the above solution is fine.
But, my guess is that they would want an optimal solution. For example, [2,4] [3,6] [5, 8], we would want [2,4][5,8] since it covers the entire range from 2-8.
We don't want to include [3,6] even though it is not included in the prev/next range since it would make no difference to the range [2-8]. This would involve dynamic programming.

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

What about [1,2][3,4],[1,5]?
expect output is [1,5]

but the program above will produce [1,2][1,5] I think.

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

> What about [1,2][3,4],[1,5]?
> expect output is [1,5]

> but the program above will produce [1,2][1,5] I think.
After the sorting step, the array will become [1,2][1,5][3,4]. Therefore, the final output will be [1,5].

- ducalpha November 05, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

you must find the max range which most of the ranges are contained in it.

- chuckNorris November 19, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

function getArrayRange(first, last){
        var arrRange =[];
        for(var i=first; i<=last; i++){

            arrRange.push(i);
        }
        return arrRange
    }
    //console.log(getArrayRange(7,21))

    function removeSubArr(arr){
        var obj = {};
        var fullArr = [];
        for (var i=0; i<arr.length; i++){
            for(var j=0; j<arr[i].length; j++){
                fullArr.push(getArrayRange(arr[i][0], arr[i][1]));
              obj[arr[i]] = getArrayRange(arr[i][0], arr[i][1]);
            }
        }

        for(var prop in obj){
           if(obj.hasOwnProperty(prop)){

               for(var i =0; i< fullArr.length; i++){
                   if(subArrCheck(obj[prop], fullArr[i]) == true){
                       fullArr.splice(i,1);
                   }
               }


           }
        }

        return fullArr;
    }

    function subArrCheck(arr, subarr) {


        var i, found, j;
        for (i = 0; i < 1 + (arr.length - subarr.length); ++i) {
            found = true;
            for (j = 0; j < subarr.length; ++j) {
                if (arr[i + j] !== subarr[j]) {
                    found = false;
                    break;
                }
            }
            if (found) return true;
        }
        return false;
    };

    console.log(removeSubArr([[2, 6],[3, 5],[7, 21],[20, 21]]));

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

How about a merge sort? O(n*log(n)) time, O(n) memory (n-ah, not in this python pseudocode)

The idea is the following - in both subarrays ranges are sorted by their left bound, shortest first. If one range contains another, just skip it. However, if we have two arrays
(a1, ...) (a2, ....), ...
(b1, ...) (b2, ...), ...
There are 3 cases
1) a1 < b1, then we are sure that (a1, ...) is not a subarray of any of (b1, ...), (b2, ...), etc. Also (b1, ...) is not a subarray of (a1, ...), so neither (b2, ...), (b3, ...) are, since they are already known to be not a subarray of (b1, ...) - emit (a1, ...)
2) a1 = b1, - basically can't happen, since then (a1, ...) would be sub-range of (b1, ...) or vice-versa
3) a1 > b1, then we are sure that (b1, ...) is not a subarray of any (a1, ...), (a2, ...), etc - emit (b1, ...)

def dumb_algo(ranges):
    """Dumb algorithm for checking correctness of merge sort approach"""
    result = []
    removed = set()
    for i, candidate in enumerate(ranges):
        for j, other in enumerate(ranges):
            if j in removed:
                continue
            if i != j and contains(other, candidate):
                removed.add(i)
                break
        else:
            result.append(candidate)
    return result

def contains(who, whom):
    return who[0] <= whom[0] <= whom[1] <= who[1]

def merge_sort(ranges):
    if len(ranges) <= 1:
        return ranges
    mid = len(ranges) / 2
    left = merge_sort(ranges[:mid])
    right = merge_sort(ranges[mid:])
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        l = left[i]
        r = right[j]
        if contains(l, r):
            j += 1
        elif contains(r, l):
            i += 1
        else:
            if l < r:
                result.append(l)
                i += 1
            else:
                result.append(r)
                j += 1
    result.extend(left[i:])
    result.extend(right[j:])
    return result

import random
for i in xrange(500):
    ranges = []
    for j in xrange(200):
        left = random.randrange(100)
        right = random.randrange(left, 101)
        ranges.append((left, right))
    assert sorted(merge_sort(ranges)) == sorted(dumb_algo(ranges))

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

Complexity: O(n log n) in time => due to the initial sort

If the input was already sorted the complexity would be O(n).

public static class Interval {
		public Interval(int s, int e) {
			this.start = s;
			this.end = e;
		}

		public int start;
		public int end;
		
	}

	public static List<Interval> clean(List<Interval> ranges) {

		Collections.sort(ranges, new Comparator<Interval>() {
			@Override
			public int compare(Interval int1, Interval int2) {
				return int1.start - int2.start;
			}

		});

		List<Interval> output = new ArrayList<>();
		int start = ranges.get(0).start;
		int end = ranges.get(0).end;
		for (int i = 1; i < ranges.size(); i++) {
			if (ranges.get(i).start <= end) {
				if (ranges.get(i).end > end)
					end = ranges.get(i).end;
			} else {
				Interval interval = new Interval(start, end);
				output.add(interval);
				start = ranges.get(i).start;
				end = ranges.get(i).end;
			}
		}

		Interval interval = new Interval(start, end);
		output.add(interval);

		return output;
	}

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

seems like it will output [(0, 5)] if we give it [(0, 3), (2, 5)]

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

The task asks to remove redundancies and not to merge the ranges.

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

You are right... I upvoted the other solution.

- tizianoP October 20, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

If we get an input like [(2,6),(3,7),(7,21),(20,21)]

Do we need to remove (3,7) ?

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

I don't think so, since this is not a reduction problem, otherwise the example OUTPUT would've been [(2,21)]

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

No. You are removing an array range that is a subset of another.

- dark_knight October 20, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Sort the pairs, and then check each element if its within the range of the previous one. Replace it accordingly.

public class ArrayRangeSubset {

	public static class Pair implements Comparable<Pair>{
		Integer a;
		Integer b;
		public Pair(int a, int b)
		{
			this.a = a;
			this.b = b;
		}
		public boolean isInside(Pair other)
		{
			return (other!=null && 
					other.a <= other.b &&
					other.a <= this.a &&
					other.b >= this.b);
		}
		@Override
		public int compareTo(Pair o) {
			return o.a==this.a?b.compareTo(o.b):
				a.compareTo(o.a);
		}
		
		@Override
		public String toString() {
			return "("+a+", "+b+")";
		}
	}
	public static ArrayList<Pair> smallerSubArray(Pair[] data)
	{
		
		Arrays.sort(data);
		ArrayList<Pair> optList = new ArrayList<Pair>();
		optList.add(data[0]);
		for (int i=1;i<data.length;i++)
		{
			if (!data[i].isInside(optList.get(optList.size()-1))) 
			{
				if (optList.get(optList.size()-1).isInside(data[i])) {
					optList.remove(optList.size()-1);
					
				}
				optList.add(data[i]);
			}
			
		}
		return optList;
	}
	public static void main(String[] args) {
		Pair[] data={  new Pair(3,5), new Pair(2,6),  new Pair(2,8), new Pair(20,21), new Pair(8,20) } ;
		ArrayList<Pair> sm = smallerSubArray(data);
		System.out.println(sm);

	}

}

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

public class ArrayRangeSubset {

	public static class Pair implements Comparable<Pair>{
		Integer a;
		Integer b;
		public Pair(int a, int b)
		{
			this.a = a;
			this.b = b;
		}
		public boolean isInside(Pair other)
		{
			return (other!=null && 
					other.a <= other.b &&
					other.a <= this.a &&
					other.b >= this.b);
		}
		@Override
		public int compareTo(Pair o) {
			return o.a==this.a?b.compareTo(o.b):
				a.compareTo(o.a);
		}
		
		@Override
		public String toString() {
			return "("+a+", "+b+")";
		}
	}
	public static ArrayList<Pair> smallerSubArray(Pair[] data)
	{
		
		Arrays.sort(data);
		ArrayList<Pair> optList = new ArrayList<Pair>();
		optList.add(data[0]);
		for (int i=1;i<data.length;i++)
		{
			if (!data[i].isInside(optList.get(optList.size()-1))) 
			{
				if (optList.get(optList.size()-1).isInside(data[i])) {
					optList.remove(optList.size()-1);
					
				}
				optList.add(data[i]);
			}
			
		}
		return optList;
	}
	public static void main(String[] args) {
		Pair[] data={  new Pair(3,5), new Pair(2,6),  new Pair(2,8), new Pair(20,21), new Pair(8,20) } ;
		ArrayList<Pair> sm = smallerSubArray(data);
		System.out.println(sm);

	}

}

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

I don't think so since the sample OUTPUT would've been [(2,21)]

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

O(NLogN) solution, based on sorting by Start value and then using stack to handle overlaps

class Program
	{

		class range
		{
			public int start;
			public int end;
			public range( int _start, int _end )
			{
				this.start = _start;
				this.end = _end;
			}
		}

		static void Main( string[] args )
		{
			int n = int.Parse( Console.ReadLine() );
			List<range> ranges = new List<range>();
			for ( int i = 0; i < n; i++ )
			{
				int[] arr = Console.ReadLine().Split().Select( x => int.Parse( x ) ).ToArray<int>();
				ranges.Add( new range( arr[0], arr[1] ) );
			}

			var r = ranges.OrderBy( x => x.start ).ToList();

			Stack<range> s = new Stack<range>();
			s.Push( r[0] );

			for ( int i = 1; i < r.Count; i++ )
			{
				range curr = s.Pop();
				if ( r[i].start >= curr.start && r[i].end <= curr.end )
				{
					s.Push( curr );
					continue;
				}
				else
				{
					s.Push( curr );
					s.Push( r[i] );
				}
			}

			foreach ( var kv in s )
				Console.WriteLine( "{0}-{1}", kv.start, kv.end );

		}
	}
}

- c.prashanth85 October 20, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Sorting is O(n log n). Finding maximum coverage with minimum items is O(n).

c++, implementation

struct sort_first_second {
    bool operator()(const pair<int, int>& left, const pair<int, int>& right) {
	if (left.first != right.first) return left.first < right.first;
        return left.second < right.second;
    }
};

void optimizeArray(vector<pair<int, int>>& arr) {
	vector<pair<int, int>> result;
	int i, limit, start, end, index;

	if (arr.size() == 0) return;

	sort(arr.begin(), arr.end(), sort_first_second());

	limit = arr[arr.size() - 1].second;
	start = arr[0].first;
	end = start;
	i = 0;
	while (end < limit) {
		index = -1;
		while (i < arr.size()) {
			if (arr[i].first <= start) {
				if (arr[i].second > end) {
					end = arr[i].second;
					index = i;
				}
			} else {
				if (index == -1) {
					start = arr[i].first;
				}
				break;
			}
			i++;
		}
		if (index != -1) {
			start = end;
			result.push_back(arr[index]);
		}
	}

	arr = result;
}

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

#include <vector>
#include <cstdio>
#include <utility>
#include <algorithm>

using namespace std;

vector<pair<int, int> > func(vector<pair<int, int> > list) {
	vector<pair<int, int> > ans;
	sort(list.begin(), list.end());
	ans.push_back(list[0]);

	for(int i=1; i<list.size(); i++) {
		pair<int, int> tmp=*(ans.end()-1);
		if(list[i].first>=tmp.first && list[i].second<=tmp.second) // this means that list[i] is completely within tmp
			continue;
		else if(tmp.first>=list[i].first && tmp.second<=list[i].second)
			ans[ans.size()-1]=list[i];
		else {
			if(list[i].first<tmp.first && list[i].first<tmp.second) {
				ans[ans.size()-1].first=list[i].first;
				ans[ans.size()-1].second=tmp.second;
			}
			else
				ans.push_back(list[i]);
		}
	}

	return ans;
}

int main() {
	vector<pair<int, int> > in, out;
	in.resize(4);
	in[0].first=2; in[0].second=6;
	in[1].first=3; in[1].second=5;
	in[2].first=7; in[2].second=21;
	in[3].first=20; in[3].second=21;
	out=func(in);
	for(int i=0; i<out.size(); i++)
		printf("%d %d\n", out[i].first, out[i].second);

	return 0;
}

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

struct range {
	int l, r;
}

struct range_comparator {
	bool operator()(const ranges& l, const ranges& r) const {
		return l.l < r.l || (l.l == r.l && l.r < r.r);
	}
}

std::vector<range> merge_array_range(std::vector<range> ranges) {
	std::sort(ranges.begin(), ranges.end(), range_comparator());
	std::vector<range> res;
	res.push_back(ranges.front());
	for (int i = 1; ranges.length(); ++i) {
		if (ranges[i].l <= res.back().l) {
			if (res.back.r < ranges[i].r)
				res.back.r = ranges[i].r;
		} else {
			res.push_back(ranges[i]);
		}
	}
	return res;
}

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

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct range {
	range(int ll, int rr) : l(ll), r(rr) {}
	int l, r;
};

struct range_comparator {
	bool operator()(const range& l, const range& r) const {
		return l.l < r.l || (l.l == r.l && l.r < r.r);
	}
};

void print_ranges(vector<range>& ranges) {
	for (vector<range>::iterator it = ranges.begin(); it != ranges.end(); ++it) {
		cout << "(" << it->l << " " << it->r << ") ";
	}
	cout << endl;
}

vector<range> merge_array_range(vector<range>& ranges) {
	sort(ranges.begin(), ranges.end(), range_comparator());
	vector<range> res;
	res.push_back(ranges.front());
	for (int i = 1; i < ranges.size(); ++i) {
		if (ranges[i].l <= res.back().r) {
			if (res.back().r < ranges[i].r) {
				res.back().r = ranges[i].r;
			}
		} else {
			res.push_back(ranges[i]);
		}
	}
	return res;
}

int main()
{
	vector<range> ranges;
	ranges.push_back(range(1, 5));
	ranges.push_back(range(1, 3));
	ranges.push_back(range(1, 7));
	ranges.push_back(range(2, 3));
	ranges.push_back(range(3, 5));
	ranges.push_back(range(8, 9));
	ranges.push_back(range(9, 17));
	ranges.push_back(range(5, 6));
	print_ranges(ranges);
	vector<range> merged = merge_array_range(ranges);
	print_ranges(merged);
	return 0;
}

> (1 5) (1 3) (1 7) (2 3) (3 5) (8 9) (9 17) (5 6)
> (1 7) (8 17)

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

Sort the set by start, if start values are equivalent, sort in descending end order
Iterate over the sorted array and add to result array entries where the value of end exceeds the current max. Update max in this case.
Time Complexity: O(n log n) due to sorting
Sorting is not stable, and I was not sure if this was supposed to modify the original array or return a different array.

var Tuple = function(start, end) {
	this.start = start;
	this.end   = end;
}

function removeRange(set) {
	var endMax = 0;
	var result = [];

	if (set.length < 2) { return set; }

	set.sort(function (a,b) {
		if (a.start === b.start) {
			return b.end - a.end;
		} else {
			return a.start - b.start;
		}
	});

	endMax = set[0].end;
	result.push(set[0]);
	for (var i = 1; i < set.length; i++){
		if (set[i].end > endMax) {
			result.push(set[i]);
			endMax = set[i].end;
		}
	}
	return result;
}


// Execute
var set1 = [ new Tuple(2,6), new Tuple(3,5), new Tuple(7,21), new Tuple(20,21) ];
var set2 = [ new Tuple(1,5), new Tuple(1,3), new Tuple(1,7), new Tuple(2,3) , 
			 new Tuple(3,5), new Tuple(8,9), new Tuple(9,17), new Tuple(5,6)];
var set3 = [ new Tuple(1,10), new Tuple(3,3), new Tuple(4,7), new Tuple(10,30) , 
 			 new Tuple(16,19), new Tuple(-1,9), new Tuple(9,31), new Tuple(9,29)];
console.log(removeRange(set1)); // Expected: [(2,6), (7,21)]
console.log(removeRange(set2)); // Expected: [(1,7), (8,9), (9,17)]
console.log(removeRange(set3)); // Expected: [(-1,9), (1,10), (9,31)]

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

This is the C++ solution.

Running time is O(n log n) due to the sorting.

#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

struct range {
	int start;
	int end;
	range(int s, int e): start(s), end(e) {}
};

bool compare(range* prev, range* after)
{
	return prev->start <= after->start;
}

void merge_range (vector<range*>& input)
{
	std::sort(input.begin(), input.end(), compare);
	vector<range*>::iterator iter = input.begin();
	range* cur = 0;
	while (iter != input.end())
	{
		if (!cur)
		{
			cur = *iter;
			iter++;
		} else if (cur->end >= (*iter)->start)
		{
			cur->end = (cur->end > (*iter)->end)? cur->end : (*iter)->end;
			iter = input.erase(iter);
		} else {
			cur = *iter;
			iter++;
		}			
	}
}

int main()
{
	vector<range*> input;
	input.push_back(new range(2,6));
	input.push_back(new range(3,5));
	input.push_back(new range(7,21));
	input.push_back(new range(20,21));
	merge_range(input);
	for (int i= 0; i < input.size(); i++)
		cout<<"( "<<input[i]->start<<", "<<input[i]->end<<" )"<<endl;

	return 1;
}

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

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;



int main() {
   
  vector< pair<int,int> > vp;
  
  int N, first, second;
 
  cout<<"Array range length : ";
  cin>>N;
  
  cout<<"Input :"<<endl; 
  for(int i=0;i<N;i++){

	cin>>first>>second;

        vp.push_back(pair<int,int>(first,second));
  }
  

  //Skip if already sort
  sort(vp.begin(), vp.end());

  pair<int,int> temp = vp[0];
  
  vector< pair<int,int> > ans;
  
  ans.push_back(temp);

  for(int i=1;i<vp.size();i++){

  	if(vp[i].first > temp.first && vp[i].second > temp.second){
        	
	  ans.push_back(vp[i]);  

	  temp = vp[i];

	}
  }
  
  cout<<"[";
  for(int i=0;i<ans.size();i++){
	if(i!=0){
    		cout<<",";
        }	
	cout<<"("<<ans[i].first<<","<<ans[i].second<<")";
	
  }

  cout<<"]"<<endl;
    
  return 0;
}

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

void deletingSubarray(vector<vector<int>> & vecArray) {
    set<int> badSet;
    sort(vecArray.begin(), vecArray.end(), compare);
    for(int i=0; i < vecArray.size(); ++i) {
        if(badSet.find(i)== badSet.end()) {
            for(int j=i+1; j< vecArray.size(); ++j) {
                if(vecArray[j].front() == vecArray[i].front() || vecArray[j].back() <= vecArray[i].back()) {
                    badSet.insert(j);
                }
            }
        }
    }
    for(int i=0; i< vecArray.size(); ++i) {
        if(badSet.find(i)== badSet.end()) {
            cout << "[" << vecArray[i].front() << ", " << vecArray[i].back() << "]" << endl;
        }

    }
}

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

void deletingSubarray(vector<vector<int>> & vecArray) {
    set<int> badSet;
    sort(vecArray.begin(), vecArray.end(), compare);
    for(int i=0; i < vecArray.size(); ++i) {
        if(badSet.find(i)== badSet.end()) {
            for(int j=i+1; j< vecArray.size(); ++j) {
                if(vecArray[j].front() == vecArray[i].front() || vecArray[j].back() <= vecArray[i].back()) {
                    badSet.insert(j);
                }
            }
        }
    }
    for(int i=0; i< vecArray.size(); ++i) {
        if(badSet.find(i)== badSet.end()) {
            cout << "[" << vecArray[i].front() << ", " << vecArray[i].back() << "]" << endl;
        }

    }
}

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

void deletingSubarray(vector<vector<int>> & vecArray) {
    set<int> badSet;
    sort(vecArray.begin(), vecArray.end(), compare);
    for(int i=0; i < vecArray.size(); ++i) {
        if(badSet.find(i)== badSet.end()) {
            for(int j=i+1; j< vecArray.size(); ++j) {
                if(vecArray[j].front() == vecArray[i].front() || vecArray[j].back() <= vecArray[i].back()) {
                    badSet.insert(j);
                }
            }
        }
    }
    for(int i=0; i< vecArray.size(); ++i) {
        if(badSet.find(i)== badSet.end()) {
            cout << "[" << vecArray[i].front() << ", " << vecArray[i].back() << "]" << endl;
        }

    }
}

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

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;

bool compare(vector<int> vec1, vector<int> vec2) {
if(vec1.front()!= vec2.front())
return vec1.front() < vec2.front();
return vec1.end() > vec2.end();
}


void deletingSubarray(vector<vector<int>> & vecArray) {
set<int> badSet;
sort(vecArray.begin(), vecArray.end(), compare);
for(int i=0; i < vecArray.size(); ++i) {
if(badSet.find(i)== badSet.end()) {
for(int j=i+1; j< vecArray.size(); ++j) {
if(vecArray[j].front() == vecArray[i].front() || vecArray[j].back() <= vecArray[i].back()) {
badSet.insert(j);
}
}
}
}
for(int i=0; i< vecArray.size(); ++i) {
if(badSet.find(i)== badSet.end()) {
cout << "[" << vecArray[i].front() << ", " << vecArray[i].back() << "]" << endl;
}
}
}

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

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

My C# Solution, I am asuming the ranges in a sort order, if that is not the case the ranges must be sorted first:

Array.Sort(ranges, IComparer<int>);

The IComparer interface must be implemented comparing the first element of the range.

public int[][] CombineRanges(int[][] ranges)
{
	int length = ranges.GetLength(0);
	if (length <= 1)
		return ranges;

	List<int[]> result = new List<int[]>();
	int[] p = ranges[0];
	for (int i = 1; i < length; i++)
	{
		int[] current = ranges[i];
		Debug.Assert(current.Length == 2);
		if (current[0] <= p[1])
		{
			int[] np = new int[2];
			np[0] = p[0];
			np[1] = Math.Max(p[1], current[1]);
			p = np;
		}
		else
		{
			result.Add(p);
			p = current;
		}
	}

	result.Add(p);
	return result.ToArray();
}

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

def rmsubrange(rs):
    """Given an array of 'array ranges' (rs), return an optimized array by
    deleting subarrays. Time complexity O(n*log(n)).

    NOTE: Array range (2,6) represents (2,3,4,5,6) 

    >>> rmsubrange([(2, 6), (3, 5), (20, 21), (7, 21)])
    [(2, 6), (7, 21)]
    >>> rmsubrange([(10, 13), (1, 8), (2, 6), (15, 18), (12, 18)])
    [(1, 8), (10, 13), (12, 18)]
    """
    if not rs or len(rs) == 1:
        return rs
    rs.sort(key=lambda x: x[0])
    rs_opt = []
    for i in range(len(rs) - 1):
        if rs[i]:
            if not (rs[i][0] >= rs[i+1][0] and rs[i][1] <= rs[i+1][1]):
                rs_opt.append(rs[i])
            if rs[i+1][1] < rs[i][1]:
                rs[i+1] = None
    return rs_opt


if __name__ == '__main__':
    import doctest
    doctest.testmod()

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

Pretty sure I have a working solution (minus some sorry length input edge cases or whatever have you) You want to check for 2 things:
1) An interval is completely inside a previous interval
2) An interval is completely inside the merger of neighboring intervals. This only happens when the End of previous interval is equal or -1 of the Start of the Next interval.

def intervals(arr):

	arr = sorted(arr, key = lambda x: (x[0],1/x[1]))
	res = [arr[0]]

	for i in range(1,len(arr)):
		curr = arr[i]

		# if previous interval 'completely covers' curr, skip
		if curr[0] >= res[-1][0] and curr[1] <= res[-1][1]: 
			continue
		else:
			useCurr = True
			for j in range(i+1,len(arr)):
				# check if curr is 'covered' by it's neighbors. ie: [1,5][3,7][6,10].
				# in this case we would not need [3,7]
				if arr[j][0] == res[-1][1] or arr[j][0] == res[-1][1]+1:
					if curr[1] <= arr[j][1]:
						useCurr = False
					else:
						break
				else:
					break					
			if useCurr:
				res.append(curr)

	return(res)

test1 = [(2,6),(3,5),(7,21),(20,21)]
test2 = [(2,6),(3,9),(8,21),(20,21)]
print(intervals(test1)) -----OUTPUT----> [(2, 6), (7, 21)]
print(intervals(test2)) -----OUTPUT----> [(2,6),(3,9),(8,21),(20,21)]

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

In Java:

List<List<Integer>> rangeList = new ArrayList<>();
        rangeList.add(Arrays.asList(7, 21));
        rangeList.add(Arrays.asList(20, 21));
        rangeList.add(Arrays.asList(2, 6));
        rangeList.add(Arrays.asList(3, 5));

        Set<List<Integer>> rangeForDeleteSet = new HashSet<>();

        for (List<Integer> range : rangeList) {
            int rangeStart = range.get(0);
            int rangeEnd = range.get(1);

            for (List<Integer> subRange : rangeList) {
                if (range == subRange) {
                    continue;
                }

                int subRangeStart = subRange.get(0);
                int subRangeEnd = subRange.get(1);

                if (rangeStart <= subRangeStart && rangeEnd >= subRangeEnd) {
                    rangeForDeleteSet.add(subRange);
                }
            }
        }

        for (List<Integer> list : rangeForDeleteSet) {
            rangeList.remove(list);
        }

        System.out.println(rangeList);

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

using range_t = pair<int, int>;

void removeSubranges(vector<range_t>& input) {
	vector<range_t> output;

	sort(input.begin(), input.end());

	for (size_t prev = 0; prev < input.size(); ) {
		
		size_t next = prev + 1;
		while (next < input.size()) {
			if (input[prev].first == input[next].first)
				prev++;
			else if (input[prev].second < input[next].first)
				break;
			next++;
		}
		output.push_back(input[prev]);
		prev = next;
	}

	input = output;
}

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

using range_t = pair<int, int>;

void removeSubranges(vector<range_t>& input) {
	vector<range_t> output;

	sort(input.begin(), input.end());

	for (size_t prev = 0; prev < input.size(); ) {
		
		size_t next = prev + 1;
		while (next < input.size()) {
			if (input[prev].first == input[next].first)
				prev++;
			else if (input[prev].second < input[next].first)
				break;
			next++;
		}
		output.push_back(input[prev]);
		prev = next;
	}

	input = output;
}

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

Here's a solution in JavaScript:

//
// Input: [[1,3], [5,7], [2,4], [6,8]]
// Output: [[1,4], [5,8]] (no specific order)
//

/**
 * Do these two ranges overlap?
 *
 * @param {array} a
 * @param {array} b
 * @return {boolen}
 */
var overlaps = function (a, b) {
  return a[0] >= b[0] && a[0] <= b[1]  // a[lo] is in range of b
      || a[1] >= b[0] && a[1] <= b[1]; // a[hi] is in range of b
};

/**
 * Merge two ranges, assuming overlap
 *
 * @param {array} a
 * @param {array} b
 * @return {array}
 */
var merge = function (a, b) {
  return [Math.min(a[0], b[0]), Math.max(a[1], b[1])];
};

/**
 * Merge a single range into a list of ranges
 *
 * @param {array[array]} list
 * @param {array} range
 * @param {array[array]}
 */
var mergeRange = function (list, range) {
  for (var i = 0; i < list.length; i++) {
    if (overlaps(list[i], range)) { // the range overlaps
      var newRange = merge(list[i], range);
      list.splice(i, 1);
      return mergeRange(list, newRange); // recursive call
    }
  }
  list.push(range); // the range doesn't overlap, so just add it to list
  return list;
};

/**
 * Merge a list of ranges into each other
 *
 * @param {array[array]} ranges
 * @return {array[array]}
 */
var mergeRanges = function (ranges) {
  return ranges.reduce(function (acc, curr) {
    return mergeRange(acc, curr);
  }, []);
};

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

Here's a working C++ solution

#include <algorithm>
#include <map>
#include <iostream>
using namespace std;
/************************************************************/
typedef pair<int, int> Range;

//auxilary function.
//return true if r2 is contained in r1
bool isContained(Range r1, Range r2) {
    return (r1.first <= r2.first) && (r1.second >= r2.second);
}
//------------------------------------------
void getMaxRange(Range& max, const vector<Range> ranges) {
  max = ranges[0];
  for(size_t i = 0; i < ranges.size(); ++i) {
    max = (isContained(ranges[i] ,max)) ? ranges[i] : max;
  }  
}
//------------------------------------------
void printOptimalRanges(vector<Range>& ranges) {
  if(ranges.empty()) {
    return;
  }  
  sort(ranges.begin(), ranges.end());  
  Range current, previous, max;
  getMaxRange(max, ranges);
  for(size_t i = 1; i < ranges.size(); ++i) {
    current = ranges[i];
    previous = ranges[i-1];
    if(isContained(max, current) && isContained(max, previous)) {
      continue;
    } else if(!isContained(previous, current)) {
      cout  << current.first << " " << current.second << endl;
    }
  }
  cout << max.first << " " << max.second << endl;
}
/************************************************************/
int main() {
  //int arr[] = {0,1,2,3,4,5,6};
  //printAllPairsSumToN(arr,7, 6);
  vector<Range> ranges;
  Range r = make_pair(2,6);
  ranges.push_back(r);
  r = make_pair(1,21);
  ranges.push_back(r);
  r = make_pair(3,5);
  ranges.push_back(r);
  r = make_pair(20,21);
  ranges.push_back(r);
  r = make_pair(1,40);
  ranges.push_back(r);
  printOptimalRanges(ranges);
  return 0;
}

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

public class IntervalMerge {
	
	public static void main(String[] args) {
		List<Interval> list = new ArrayList<>();
		Interval i1 = new Interval(2,6);
		Interval i2 = new Interval(3,5);
		Interval i3 = new Interval(7,21);
		Interval i4 = new Interval(20,21);
		list.add(i1);
		list.add(i2);
		list.add(i3);
		list.add(i4);
		IntervalMerge im = new IntervalMerge();
		List<Interval> r = im.getOptimalIntervalList(list);
		for (Interval interval : r) {
			System.out.println(interval.s + " " + interval.e);
		}
	}
	
	public List<Interval> getOptimalIntervalList(List<Interval> list) {
		if (list == null || list.isEmpty()) {
			return null;
		}
		Collections.sort(list);
		List<Interval> r = new ArrayList<>();
		int n = list.size();
		boolean keep[] = new boolean[n];
		Arrays.fill(keep, true);
		Interval in1, in2;
		int i = 1;
		
		while (i < n) {
			if (keep[i]) {
				in1 = list.get(i);
				in2 = list.get(i - 1);

				if (in1.containsInterval(in2)) {
					keep[i - 1] = false;
				} else if (in2.containsInterval(in1)) {
					keep[i] = false;
				}				
			}
			i++;
		}
		
		for (int j = 0; j < keep.length; j++) {
			if (keep[j]) {
				r.add(list.get(j));
			}
		}
		
		return r;
	}
	
}

class Interval implements Comparable<Interval> {
	Integer s;
	Integer e;
	public Interval(int s, int e) {
		super();
		this.s = s;
		this.e = e;
	}
	public boolean containsInterval(Interval i2) {
		return (this.s <= i2.s && this.e >= i2.e);
	}
	@Override
	public int compareTo(Interval o) {
		return this.s.compareTo(o.s);
	}
}

- guilhebl May 30, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Python3

def sub_arrs(inp):
    res = []
    tmp = inp[0]
    for i in inp[1::]:
        
        if (i[0] >= tmp[0] and i[1] <= tmp[1]):
            if (tmp not in res):
                res.append(tmp)
        else:
            res.append(i)
            tmp = i
    return res

- silvio.s December 15, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

I was able to come up with a O(N^2) solution pretty quickly with no memory overhead. I'm having trouble coming up with anything that's much faster for all cases.

My basic algorithm:
1. Beginning at the 0th index and increasing by one, select an interval I --> (i, j)
2. Compare the selected interval to the intervals after it, J. If there is overlap between intervals, take the min(I.i, J.i) as the new start and the max(I.j, J.j) as the end. Update interval I. Delete interval J from the array. Continue comparing again from the index of I, plus 1.
3. If no interval in the array had an overlap, interval I is part of the solution set. Move on to the next index.

C++

struct Pair {
	int i;
	int j;
	Pair(int a, int b)
	{
		i = a; j = b;
	}
};

void remove(vector<Pair> &v, int index)
{
	v[index].i = v[v.size() - 1].i;
	v[index].j = v[v.size() - 1].j;
	v.erase(v.end() - 1); // deleting from the end is O(1)
}

void combineRanges(vector<Pair> &input)
{
	for(int i = 0; i < input.size(); i++)
	{
		bool done = true;
		for(int j = i + 1; j < input.size(); j++)
		{
			// first range is entirely before second
			if(input[i].j < input[j].i) continue;

			// first range is entirely after second
			if(input[i].i > input[j].j) continue;

			// Otherwise, theres some sort of overlap
			// take max of the J's and min of the I's
			// to get the "new" range
			done = false;
			int newI = min(input[i].i, input[j].i);
			int newJ = max(input[i].j, input[j].j);

			// replace the ith item with this new range, delete the jth one
			input[i].i = newI; input[i].j = newJ;
			remove(input, j);
		}
		// repeat iteration with the new range at I to see if it can
		// combine with any others
		if(!done) i--;
	}
}

int main()
{
	vector<Pair> v;
	v.push_back(Pair(6,8));
	v.push_back(Pair(2,3));
	v.push_back(Pair(4,7));
	v.push_back(Pair(1,9));
	printVector(v);
	combineRanges(v);
	printVector(v);
}

Output:

(6, 8) (2, 3) (4, 7) (1, 9) 
(1, 9)

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

Can be done on O(n*log(n))

- koosha.nejad October 22, 2015 | Flag


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