Facebook Interview Question Software Engineers
Country: Israel
Interview Type: Phone Interview
It wasn't until I read your answer that I realized the question never stated the output had to be sorted.
Implemented your solution in C++:
#include <vector>
using namespace std;
struct Range
{
int begin, end;
Range(int a, int b) : begin(a), end(b) {}
};
vector<Range> mergeRanges(vector<Range> input, Range newRange)
{
vector<Range> output;
for (vector<Range>::const_iterator it = input.begin(); it != input.end(); ++it)
{
if (newRange.end < it->begin || newRange.begin > it->end)
{
output.push_back(*it);
}
else
{
if (it->begin < newRange.begin)
{
newRange.begin = it->begin;
}
if (it->end > newRange.end)
{
newRange.end = it->end;
}
}
}
output.push_back(newRange);
return output;
}
Sort the initial list of Range classes that do not overlap.
Given the newRange class that may or may not overlap...
Do a binary search on the sorted list of Range classes to figure out the overlapping range.
The meat of the solution lies in the criteria to search in the left/right subarrays using both the Range.begin and Range.end keys.
function mergeRange(ranges, range) {
var result = [],
toBeMerged = [],
toBeMerged.push(range);
ranges.forEach(function (r) {
if (overlap(range, r)) {
toBeMerged.push(r);
} else {
result.push(r);
}
});
result.push(merge(toBeMerged));
return result;
}
function merge(ranges) {
// find min, max return a new object
var min = ranges.reduce(function (a, b) {
return a.begin < b.begin ? a : b;
});
var max = ranges.reduce(function (a, b) {
return a.end > b.end ? a : b;
});
return { begin: min.begin, end: max: end };
}
function overlap(a, b) {
// a => { begin, end }
if (a.begin > b.begin) {
return a.begin < b.end;
} else {
return b.begin < a.end;
}
}
I would propose the following: (i) Find ranges that that overlap with the newRange (ii) merge them together one by one (iii) copy non overlapped ranges to the output and add the new merged interval.
public Range[] mergeRanges(Range[] ranges, Range newRange) {
int N = ranges.length;
/*** Detect overlaps ***/
boolean[] isover = isOverlap(ranges, newRange);
/*** Merge overlapped ranges and count the output array size ***/
int Nout = N+1;
Range newGuy = newRange;
for (int k=0; k<N; k++) {
if (isover[k] == false) continue;
Range curr = ranges[k];
newGuy = merge(newGuy, curr);
Nout--;
}
/*** Generate output ***/
Range[] out = new Range[Nout];
for (int k =0, j=0; k<N; k++)
if (isover[k] == false) out[j++] = ranges[k];
out[Nout-1] = newGuy; // don't forget the new guy
return out;
}
private Range merge(Range a, Range b) {
int x = new int[] {a.begin, b.begin};
int y = new Int[] {a.end, b.end};
int begin = Math.min(x);
int end = Math.max(y);
return new Range(begin, end);
}
private boolean[] isOverlap(Range[] a, Range x) {
int N = a.length;
boolean[] out = new boolean[N];
for (int k=0; k<N; k++) {
if (a[k].begin < x.begin && a[k].end < x.begin) out[k] = false;
else if (a[k].begin > x.end && a[k].end > x.end) out[k] = false;
else out[k] = true;
}
return out;
}
public static List<Range> MergeRanges(List<Range> ranges, Range overlap)
{
int start = overlap.start;
int end = overlap.end;
List<Range> result = new List<Range>();
for(int i = 0; i < ranges.Count; i++)
{
Ranges r = ranges[i];
// This also covers the case where r is larger than overlap
if(r.start < overlap.start && r.end >= overlap.start)
{
start = r.start;
}
else if(r.start <= overlap.end && r.end > overlap.end)
{
end = r.end;
}
else if(r.start < overlap.start && r.end > overlap.end)
{
start = r.start;
end = r.end;
}
else if(r.end < overlap.start || r.start > overlap.end)
{
result.Add(r);
}
}
result.Add(new Range(start, end));
return result;
}
function mergeRange(ranges, range) {
var result = [],
toBeMerged = [],
toBeMerged.push(range);
ranges.forEach(function (r) {
if (overlap(range, r)) {
toBeMerged.push(r);
} else {
result.push(r);
}
});
result.push(merge(toBeMerged));
return result;
}
function merge(ranges) {
// find min, max return a new object
var min = ranges.reduce(function (a, b) {
return a.begin < b.begin ? a : b;
});
var max = ranges.reduce(function (a, b) {
return a.end > b.end ? a : b;
});
return { begin: min.begin, end: max: end };
}
function overlap(a, b) {
// a => { begin, end }
if (a.begin > b.begin) {
return a.begin < b.end;
} else {
return b.begin < a.end;
}
}
function mergeRange(ranges, range) {
var result = [],
toBeMerged = [],
toBeMerged.push(range);
ranges.forEach(function (r) {
if (overlap(range, r)) {
toBeMerged.push(r);
} else {
result.push(r);
}
});
result.push(merge(toBeMerged));
return result;
}
function merge(ranges) {
// find min, max return a new object
var min = ranges.reduce(function (a, b) {
return a.begin < b.begin ? a : b;
});
var max = ranges.reduce(function (a, b) {
return a.end > b.end ? a : b;
});
return { begin: min.begin, end: max: end };
}
function overlap(a, b) {
// a => { begin, end }
if (a.begin > b.begin) {
return a.begin < b.end;
} else {
return b.begin < a.end;
}
}
function mergeRange(ranges, range) {
var result = [],
toBeMerged = [],
toBeMerged.push(range);
ranges.forEach(function (r) {
if (overlap(range, r)) {
toBeMerged.push(r);
} else {
result.push(r);
}
});
result.push(merge(toBeMerged));
return result;
}
function merge(ranges) {
// find min, max return a new object
var min = ranges.reduce(function (a, b) {
return a.begin < b.begin ? a : b;
});
var max = ranges.reduce(function (a, b) {
return a.end > b.end ? a : b;
});
return { begin: min.begin, end: max: end };
}
function overlap(a, b) {
// a => { begin, end }
if (a.begin > b.begin) {
return a.begin < b.end;
} else {
return b.begin < a.end;
}
}
function mergeRange(ranges, range) {
var result = [],
toBeMerged = [],
toBeMerged.push(range);
ranges.forEach(function (r) {
if (overlap(range, r)) {
toBeMerged.push(r);
} else {
result.push(r);
}
});
result.push(merge(toBeMerged));
return result;
}
function merge(ranges) {
// find min, max return a new object
var min = ranges.reduce(function (a, b) {
return a.begin < b.begin ? a : b;
});
var max = ranges.reduce(function (a, b) {
return a.end > b.end ? a : b;
});
return { begin: min.begin, end: max: end };
}
function overlap(a, b) {
// a => { begin, end }
if (a.begin > b.begin) {
return a.begin < b.end;
} else {
return b.begin < a.end;
}
}
function mergeRange(ranges, range) {
var result = [],
toBeMerged = [],
toBeMerged.push(range);
ranges.forEach(function (r) {
if (overlap(range, r)) {
toBeMerged.push(r);
} else {
result.push(r);
}
});
result.push(merge(toBeMerged));
return result;
}
function merge(ranges) {
// find min, max return a new object
var min = ranges.reduce(function (a, b) {
return a.begin < b.begin ? a : b;
});
var max = ranges.reduce(function (a, b) {
return a.end > b.end ? a : b;
});
return { begin: min.begin, end: max: end };
}
function overlap(a, b) {
// a => { begin, end }
if (a.begin > b.begin) {
return a.begin < b.end;
} else {
return b.begin < a.end;
}
}
function mergeRange(ranges, range) {
var result = [],
toBeMerged = [],
toBeMerged.push(range);
ranges.forEach(function (r) {
if (overlap(range, r)) {
toBeMerged.push(r);
} else {
result.push(r);
}
});
result.push(merge(toBeMerged));
return result;
}
function merge(ranges) {
// find min, max return a new object
var min = ranges.reduce(function (a, b) {
return a.begin < b.begin ? a : b;
});
var max = ranges.reduce(function (a, b) {
return a.end > b.end ? a : b;
});
return { begin: min.begin, end: max: end };
}
function overlap(a, b) {
// a => { begin, end }
if (a.begin > b.begin) {
return a.begin < b.end;
} else {
return b.begin < a.end;
}
}
function mergeRange(ranges, range) {
var result = [],
toBeMerged = [],
toBeMerged.push(range);
ranges.forEach(function (r) {
if (overlap(range, r)) {
toBeMerged.push(r);
} else {
result.push(r);
}
});
result.push(merge(toBeMerged));
return result;
}
function merge(ranges) {
// find min, max return a new object
var min = ranges.reduce(function (a, b) {
return a.begin < b.begin ? a : b;
});
var max = ranges.reduce(function (a, b) {
return a.end > b.end ? a : b;
});
return { begin: min.begin, end: max: end };
}
function overlap(a, b) {
// a => { begin, end }
if (a.begin > b.begin) {
return a.begin < b.end;
} else {
return b.begin < a.end;
}
}
function mergeRange(ranges, range) {
var result = [],
toBeMerged = [],
toBeMerged.push(range);
ranges.forEach(function (r) {
if (overlap(range, r)) {
toBeMerged.push(r);
} else {
result.push(r);
}
});
result.push(merge(toBeMerged));
return result;
}
function merge(ranges) {
// find min, max return a new object
var min = ranges.reduce(function (a, b) {
return a.begin < b.begin ? a : b;
});
var max = ranges.reduce(function (a, b) {
return a.end > b.end ? a : b;
});
return { begin: min.begin, end: max: end };
}
function overlap(a, b) {
// a => { begin, end }
if (a.begin > b.begin) {
return a.begin < b.end;
} else {
return b.begin < a.end;
}
}
The idea is, add this new range to the first element of the entire list of ranges, then use a while loop to update this set of ranges until stable - meaning the size of this list of ranges no longer changes.
Keeping the newly constructed range always in the first element, for each iteration, try to merge with the rest of the element and see if there's a successful merge, and update the list or ranges while keeping the merged range in the first element of this list.
in Python,
class Range(object):
def __init__(self, start, end):
self.start = start
self.end = end
def __str__(self,):
return "[%s, %s]" % (self.start, self.end)
def ranges_union(r1, r2):
#sort range head
if r1.start > r2.start:
tmp = r1
r1 = r2
r2 = tmp
#disjoint
if r1.end < r2.start:
return [r1, r2]
#subset
elif r1.end >= r2.end:
return [r1]
#partial overlap
elif r1.end < r2.end:
return [Range(r1.start, r2.end)]
def merge_ranges(ranges, new_range):
output = [new_range] + ranges[:]
#store the new interval on the first element, merged with others
stable = False
while not stable:
stable = True
for r in output[1:]:
merge_result = ranges_union(output[0], r)
if len(merge_result) == 1: #merged
output.remove(r)
output[0] = merge_result[0]
stable = False
break
return output
def print_ranges(ranges):
for r in ranges:
print r
#test
r1 = Range(1, 3)
r2 = Range(5,7)
r3 = Range(9, 11)
ranges = [r1, r2, r3]
new_range = Range(1, 4)
print_ranges(merge_ranges(ranges, new_range))
Take each entry in the rangelist and merge it with the new range...
O(n)
import java.util.*;
public class Ranges {
public static class Range{
public int begin;
public int end;
public Range(int begin,int end){
this.begin = begin;
this.end = end;
}
public String toString(){
return " " + this.begin + "-" + this.end;
}
}
public static ArrayList<Range> merge(ArrayList<Range> rangelist, Range range){
Iterator<Range> i = rangelist.iterator();
while(i.hasNext()){
Range r = i.next();
if(canMerge(r,range)){
merge(r,range);
i.remove();
}
}
rangelist.add(range);
return rangelist;
}
private static boolean canMerge(Range r, Range range) {
// TODO Auto-generated method stub
return ((r.begin >= range.begin && r.begin <= range.end)||
(r.end >= range.begin && r.end <= range.end)||
(range.begin >= r.begin && range.begin <= r.end)||
(range.end >= r.begin && range.end <= r.end));
}
private static void merge(Range r, Range range) {
if(range.begin > r.begin)
range.begin = r.begin;
if(range.end< r.end)
range.end = r.end;
}
public static void main(String arg[]){
Range r = new Range(1,5);
Range r2 = new Range(9,13);
Range r3 = new Range(17,22);
ArrayList<Range> rangelist= new ArrayList<Range>();
rangelist.add(r);
rangelist.add(r2);
rangelist.add(r3);
System.out.println(merge(rangelist,new Range(4,10)));
}
}
ArrayList<Range> merge(ArrayList<Range> list, Range range) {
sort(list);
int idx = 0;
while (idx < list.size() && range.begin > list.get(idx).end) {
idx++;
}
if (range.begin > list.get(idx).begin) {
range.begin = list.get(idx).begin;
}
int idx1 = idx;
while (idx1 < list.size() && range.end >= list.get(idx1).begin) {
idx1++;
}
if (range.end < list.get(idx1 - 1).end) {
range.end = list.get(idx1 - 1).end;
}
for (int i = idx; i < idx1; i++) {
list.set(i, null);
}
list.set(idx, range);
return list;
}
I assumed the inputs are the list of ranges and new range.
I used quicksort to sort the list of existing ranges and new range together by begin value.
After that scan the list and merge the overlapping ranges.
Running time is O(n log n), where n is the number of ranges in the list.
#include <list>
#include <string>
#include <climits>
#include <iostream>
using namespace std;
bool isNum(char c)
{
return (c >='0' && c<='9');
}
bool isOp(char c)
{
return (c =='+'|| c== '-'||c=='/'|| c=='*');
}
bool multiOrDiv(char c)
{
return (c == '*' || c == '/');
}
int compute(int l, int r, char op)
{
if (op =='+')
return l+r;
else if (op == '-')
return l-r;
else if (op == '*')
return l*r;
else if (op == '/')
return l/r;
return INT_MIN;
}
int eval_expr(string input)
{
list<int> numbers;
list<char> ops;
string token;
int result;
for (int i = input.length()-1; i >= 0; i--)
{
int num;
if (isNum(input[i]))
{
token.insert(0,1, input[i]);
if (i == 0 && token.length())
{
num = atoi(token.c_str());
numbers.push_back(num);
}
} else if (isOp(input[i]))
{
if (token.length())
{
num = atoi(token.c_str());
numbers.push_back(num);
token = "";
}
if (!multiOrDiv(input[i]))
{
char op = ops.back();
while (multiOrDiv(op) && numbers.size() >1)
{
ops.pop_back();
int l = numbers.back();
numbers.pop_back();
int r = numbers.back();
numbers.pop_back();
int result = compute(l, r, op);
numbers.push_back(result);
op = ops.back();
}
}
ops.push_back(input[i]);
}
}
while (numbers.size() >1 && ops.size() >0)
{
char op = ops.back();
ops.pop_back();
int l = numbers.back();
numbers.pop_back();
int r = numbers.back();
numbers.pop_back();
result = compute(l, r, op);
numbers.push_back(result);
}
return numbers.back();
}
I did not know the output does not have to be sorted. If that is the case, the following algorithm will give O(N) running time.
vector<Range> mergerange(vector<Range> &input, Range &newrange)
{
int start = newrange.begin;
int end = newrange.end;
vector<Range> result;
for (int i= 0; i <input.size(); i++)
{
if (start> input[i].end || end < input[i].begin)
{
result.push_back(input[i]);
}
else {
start = (start< input[i].begin)? start: input[i].begin;
end = (end > input[i].end)? end: input[i].end;
}
}
result.push_back(Range(start, end));
return result;
}
public static List<Range> MergeRanges(Collection<Range> ranges, Range newRange) {
BitSet bs = new BitSet();
bs.set(newRange.Begin, newRange.End+1, true);
for (Range r : ranges) bs.set(r.Begin, r.End + 1, true);
List<Range> newRanges = new LinkedList<>();
for (int begin = bs.nextSetBit(0), end = 0; begin >= 0; begin = bs.nextSetBit(end)) {
end = bs.nextClearBit(begin);
newRanges.add(new Range(begin, end - 1));
}
return newRanges;
}
- Anonymous February 23, 2015public Range[] merge(Range[] ranges, Range newRange) { List<Range> output = new LinkedList<>(); int b = newRange.begin; int e = newRange.end; for (Range r : ranges) { if (r.end < b || r.begin > e) { output.add(r); } else { b = Math.min(b, r.begin); e = Math.max(e, r.end); } } output.add(new Range(b, e)); return output.toArray(new Range[output.size()]); }