## Facebook Interview Question for Software Engineer Interns

• 2

Country: United States
Interview Type: Phone Interview

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

sorting and then using a stack

``````public ArrayList<Integer> MergeRangeArray(int[] arr1, int[] arr2){
ArrayList<Integer> list = new ArrayList<Integer>();
ArrayList<Info> arrInfo = new ArrayList<Info>();
Stack<Info> stack = new Stack<Info>();
for( int i = 0 ; i < arr1.length - 1;i+=2){
Info tempstart = new Info(arr1[i],'S');
Info tempEnd = new Info(arr1[i+1],'E');
//System.out.println(tempstart + " " + tempEnd);
}
for( int i = 0 ; i < arr2.length - 1;i+=2){
Info tempstart = new Info(arr2[i],'S');
Info tempEnd = new Info(arr2[i+1],'E');
}
Collections.sort(arrInfo);
//System.out.println(arrInfo.toString());
for( int i = 0 ; i < arrInfo.size();i++){
if( arrInfo.get(i).type == 'S'){
stack.push(arrInfo.get(i));
}
else{
Info temp = stack.pop();
if( stack.isEmpty()){
}
}
}
return list;
}``````

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

``````class Range:
def __init__(self, _min, _max):
self.min = _min
self.max = _max

def __str__(self):
return str(self.min) + "-" + str(self.max)

def __repr__(self):
return str(self)

def get_max(self):
return self.max

def get_min(self):
return self.min

def overlapping(self, other):
if (self.get_min() < other.get_min() < self.get_max()) \
or (self.get_min() < other.get_max() < self.get_max()) or \
(other.get_min() < self.get_min() < other.get_max()) \
or (other.get_min() < self.get_max() < other.get_max()):
return True
return False

def merge(self, other):
mmin = min(self.get_min(), other.get_min())
mmax = max(self.get_max(), other.get_max())
res = Range(mmin, mmax)
return res

def compare(self, other):
return cmp(self.min, other.min)

@staticmethod
def fix_array(index, array, retry=False):
if index > len(array):
return False
try:
left = array[index]
right = array[index + 1]
except Exception, e:
raise IndexError("fart")
if left.overlapping(right):
array.remove(left)
array.remove(right)
array.insert(index, left.merge(right))
if retry:
return Range.fix_array(index, array, retry=True)
return True

def merge(array1, array2):
result = []
result.extend(array1)
result.extend(array2)
result = sorted(result, cmp=Range.compare)
index = 0
while True:
try:
Range.fix_array(index, result, True)
index += 1
except IndexError, e:
return result

if __name__ == '__main__':
arr1 = [Range(3, 11), Range(17, 25), Range(58, 73)]
arr2 = [Range(6, 18), Range(40, 47)]
print merge(arr1, arr2)

arr1 = [Range(8, 13), Range(21, 32), Range(45, 60)]
arr2 = [Range(2, 9), Range(25, 46)]
print merge(arr1, arr2)

arr1 = [Range(1, 12), Range(26, 32), Range(51, 82)]
arr2 = [Range(9, 24), Range(49, 60), Range(75, 98)]
print merge(arr1, arr2)``````

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

``````private static ArrayList<Interval> mergeIntervals(ArrayList<Interval> a, ArrayList<Interval> b) {
ArrayList<Interval> result = new ArrayList<>();
int aIndex = 0;
int bIndex = 0;
while (aIndex < a.size() && bIndex < b.size()) {
Interval aInterval = a.get(aIndex);
Interval bInterval = b.get(bIndex);
if (!result.isEmpty() && (result.get(result.size() - 1).overlap(aInterval) || result.get(result.size() - 1).overlap(bInterval))) {
Interval previousResultInterval = result.get(result.size() - 1);
if (previousResultInterval.overlap(aInterval)) {
result.set(result.size() - 1, merge(previousResultInterval, aInterval));
aIndex++;
} else {
result.set(result.size() - 1, merge(previousResultInterval, bInterval));
bIndex++;
}
} else {
if (aInterval.before(bInterval)) {
aIndex++;
} else {
bIndex++;
}
}
}

while (aIndex < a.size()) {
aIndex++;
}

while (bIndex < b.size()) {
bIndex++;
}
return result;
}

private static Interval merge(Interval a, Interval b) {
if (a.overlap(b)) {
return new Interval(Math.min(a.start, b.start), Math.max(a.end, b.end));
}
return null;
}

private static class Interval {
final int start, end;

private Interval(int start, int end) {
this.start = start;
this.end = end;
}

private boolean overlap(Interval b) {
if ((start <= b.start && end >= b.start)
|| (b.start <= start && b.end >= start))
return true;
return false;
}

public boolean before(Interval other) {
return end < other.end;
}

@Override
public String toString() {
return "{" +
"start=" + start +
", end=" + end +
'}';
}
}``````

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

``````class Interval:
lower = None
upper = None

def __init__(self, lower, upper):
self.lower = lower
self.upper = upper

#Checks if the two intervals overlap with each other
def isOverlapping(self, ob):
if (ob.lower > self.lower and ob.lower < self.upper) \
or (ob.upper > self.lower and ob.upper < self.upper) :
return True

return False

#Pass in a set of interval elements to be merged
def merge(self, interval):
lowerBound = min(self.lower, interval.lower)
upperBound = max(self.upper, interval.upper)
return Interval(lowerBound, upperBound)

def findIntervalPosition(interval, arr1):
for i in xrange(len(arr1)-1,-1,-1):
if interval.lower > arr1[i].lower:
return i+1;

def mergeNewInterval(arr1, index):

lower = index - 1
upper = index + 1

while lower >= 0 or upper < len(arr1):
if lower >= 0:
if arr1[index].isOverlapping(arr1[lower]):
newInterval = arr1[index].merge(arr1[lower])
arr1.pop(index)
arr1.pop(lower)
arr1.insert(lower, newInterval)
index = index - 1
lower = lower - 1
upper = upper - 1
else:
lower = -1  #As soon as one lower element does not overlap, no other element
#below it will overlap. So no need to check

if upper < len(arr1):
if arr1[index].isOverlapping(arr1[upper]):
newInterval = arr1[index].merge(arr1[upper])
arr1.pop(upper)
arr1.pop(index)
arr1.insert(index, newInterval)
else:
upper = len(arr1) + 1

def main():
arr1 = [Interval(3,11), Interval(17,25), Interval(58,73)]
arr2 = [Interval(6,18), Interval(40,47)]

for interval in arr2:

#Insert the element into the right position in arr1
index = findIntervalPosition(interval, arr1)
arr1.insert(index, interval)
mergeNewInterval(arr1, index)

for interval in arr1:
print("({0}-{1})".format(interval.lower, interval.upper))

if __name__ == "__main__":
main()``````

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

``````class Interval:
lower = None
upper = None

def __init__(self, lower, upper):
self.lower = lower
self.upper = upper

#Checks if the two intervals overlap with each other
def isOverlapping(self, ob):
if (ob.lower > self.lower and ob.lower < self.upper) \
or (ob.upper > self.lower and ob.upper < self.upper) :
return True

return False

#Pass in a set of interval elements to be merged
def merge(self, interval):
lowerBound = min(self.lower, interval.lower)
upperBound = max(self.upper, interval.upper)
return Interval(lowerBound, upperBound)

def findIntervalPosition(interval, arr1):
for i in xrange(len(arr1)-1,-1,-1):
if interval.lower > arr1[i].lower:
return i+1;

def mergeNewInterval(arr1, index):

lower = index - 1
upper = index + 1

while lower >= 0 or upper < len(arr1):
if lower >= 0:
if arr1[index].isOverlapping(arr1[lower]):
newInterval = arr1[index].merge(arr1[lower])
arr1.pop(index)
arr1.pop(lower)
arr1.insert(lower, newInterval)
index = index - 1
lower = lower - 1
upper = upper - 1
else:
lower = -1  #As soon as one lower element does not overlap, no other element
#below it will overlap. So no need to check

if upper < len(arr1):
if arr1[index].isOverlapping(arr1[upper]):
newInterval = arr1[index].merge(arr1[upper])
arr1.pop(upper)
arr1.pop(index)
arr1.insert(index, newInterval)
else:
upper = len(arr1) + 1

def main():
arr1 = [Interval(3,11), Interval(17,25), Interval(58,73)]
arr2 = [Interval(6,18), Interval(40,47)]

for interval in arr2:

#Insert the element into the right position in arr1
index = findIntervalPosition(interval, arr1)
arr1.insert(index, interval)
mergeNewInterval(arr1, index)

for interval in arr1:
print("({0}-{1})".format(interval.lower, interval.upper))

if __name__ == "__main__":
main()``````

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

``````class Interval:
lower = None
upper = None

def __init__(self, lower, upper):
self.lower = lower
self.upper = upper

#Checks if the two intervals overlap with each other
def isOverlapping(self, ob):
if (ob.lower > self.lower and ob.lower < self.upper) \
or (ob.upper > self.lower and ob.upper < self.upper) :
return True

return False

#Pass in a set of interval elements to be merged
def merge(self, interval):
lowerBound = min(self.lower, interval.lower)
upperBound = max(self.upper, interval.upper)
return Interval(lowerBound, upperBound)

#Find the correct position of the new interval
def findIntervalPosition(interval, arr1):
for i in xrange(len(arr1)-1,-1,-1):
if interval.lower > arr1[i].lower:
return i+1;

#Merge all elements with which this new interval overlaps with
def mergeNewInterval(arr1, index):

lower = index - 1
upper = index + 1

while lower >= 0 or upper < len(arr1):
if lower >= 0:
if arr1[index].isOverlapping(arr1[lower]):
newInterval = arr1[index].merge(arr1[lower])
arr1.pop(index)
arr1.pop(lower)
arr1.insert(lower, newInterval)
index = index - 1
lower = lower - 1
upper = upper - 1
else:
lower = -1  #As soon as one lower element does not overlap, no other element
#below it will overlap. So no need to check

if upper < len(arr1):
if arr1[index].isOverlapping(arr1[upper]):
newInterval = arr1[index].merge(arr1[upper])
arr1.pop(upper)
arr1.pop(index)
arr1.insert(index, newInterval)
else:
upper = len(arr1) + 1

def main():
arr1 = [Interval(3,11), Interval(17,25), Interval(58,73)]
arr2 = [Interval(6,18), Interval(40,47)]

for interval in arr2:

#Insert the element into the right position in arr1
index = findIntervalPosition(interval, arr1)
arr1.insert(index, interval)
mergeNewInterval(arr1, index)

for interval in arr1:
print("({0}-{1})".format(interval.lower, interval.upper))

if __name__ == "__main__":
main()``````

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

This can be done in O(n) time. Keep reading from each array. Either the tow ranges are mutually exclusive. if exclusive find the smallest range and merge it with result array. Note you have to merge because it is possible that the new entry overlaps with previous entry in result. If the two entries read from the two arrays overlap and form a new overlap entry and merge it with result array.

Sample code:

{
#include "stdafx.h"
#include "vector"

struct entry
{
int start;
int end;
};

bool overlapping(struct entry entry1, struct entry entry2)
{
if ((entry1.start < entry2.start) && (entry1.end < entry2.start))
return false;
if ((entry1.start > entry2.end) && (entry1.end > entry2.end))
return false;

return true;
}

bool smaller(struct entry entry1, struct entry entry2)
{
if ((entry1.start < entry2.start) && (entry1.end < entry2.start))
return true;
return false;
}

void mergeToResult(std::vector<struct entry>& result, struct entry tempEntry)
{
if (result.size() == 0)
{
result.push_back(tempEntry);
return;
}
else
{
if (!overlapping(result[result.size() - 1], tempEntry))
{
if (smaller(result[result.size() - 1], tempEntry))
result.push_back(tempEntry);
//probably not needed, but can be there
else
{
struct entry tempEntry2 = result[result.size() - 1];
result.pop_back();
result.push_back(tempEntry);
result.push_back(tempEntry2);
}
}
else
{
struct entry tempEntry3;
struct entry tempEntry2 = result[result.size() - 1];
if (tempEntry.start <= tempEntry2.start)
tempEntry3.start = tempEntry.start;
else
tempEntry3.start = tempEntry2.start;

if (tempEntry.end >= tempEntry2.end)
tempEntry3.end = tempEntry.end;
else
tempEntry3.end = tempEntry2.end;

result.pop_back();
result.push_back(tempEntry3);
}
}
return;
}
int _tmain(int argc, _TCHAR* argv[])
{
std::vector<struct entry> arr1 = { { 3, 11 }, { 17, 25 }, { 58, 73 } };
std::vector<struct entry> arr2 = { { 6,18 }, { 40,47 } };

std::vector<struct entry> result = {};

int len1 = arr1.size();
int len2 = arr2.size();

{
{
{
}
else
{
}
}
else
{
struct entry tempEntry;
else

else

mergeToResult(result, tempEntry);
}
}
//fill remaining elements
{
{
}
}
else
{
{
}
}

//print result
{
printf("\n");
}
return 0;
}}

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

#include "stdafx.h"
#include "vector"

struct entry
{
int start;
int end;
};

bool overlapping(struct entry entry1, struct entry entry2)
{
if ((entry1.start < entry2.start) && (entry1.end < entry2.start))
return false;
if ((entry1.start > entry2.end) && (entry1.end > entry2.end))
return false;

return true;
}

bool smaller(struct entry entry1, struct entry entry2)
{
if ((entry1.start < entry2.start) && (entry1.end < entry2.start))
return true;
return false;
}

void mergeToResult(std::vector<struct entry>& result, struct entry tempEntry)
{
if (result.size() == 0)
{
result.push_back(tempEntry);
return;
}
else
{
if (!overlapping(result[result.size() - 1], tempEntry))
{
if (smaller(result[result.size() - 1], tempEntry))
result.push_back(tempEntry);
//probably not needed, but can be there
else
{
struct entry tempEntry2 = result[result.size() - 1];
result.pop_back();
result.push_back(tempEntry);
result.push_back(tempEntry2);
}
}
else
{
struct entry tempEntry3;
struct entry tempEntry2 = result[result.size() - 1];
if (tempEntry.start <= tempEntry2.start)
tempEntry3.start = tempEntry.start;
else
tempEntry3.start = tempEntry2.start;

if (tempEntry.end >= tempEntry2.end)
tempEntry3.end = tempEntry.end;
else
tempEntry3.end = tempEntry2.end;

result.pop_back();
result.push_back(tempEntry3);
}
}
return;
}
int _tmain(int argc, _TCHAR* argv[])
{
std::vector<struct entry> arr1 = { { 3, 11 }, { 17, 25 }, { 58, 73 } };
std::vector<struct entry> arr2 = { { 6,18 }, { 40,47 } };

std::vector<struct entry> result = {};

int len1 = arr1.size();
int len2 = arr2.size();

{
{
{
}
else
{
}
}
else
{
struct entry tempEntry;
else

else

mergeToResult(result, tempEntry);
}
}
//fill remaining elements
{
{
}
}
else
{
{
}
}

//print result
{
printf("\n");
}
return 0;
}

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

``````public List<Tuple<int, int>> Merge(List<Tuple<int, int>> l1, List<Tuple<int, int>> l2)
{
if (l1 == null && l2 == null)
return null;
if (l1 == null && l2.Count > 0)
return l2;
if (l2 == null && l1.Count > 0)
return l1;

var result = new List<Tuple<int, int>>();
int i = l1[0].Item1 < l2[0].Item1 ? 1 : 0;
int j = l2[0].Item1 < l1[0].Item1 ? 1 : 0; ;
Tuple<int, int> p = i == 1 ? l1[0] : l2[0];
Tuple<int, int> curr;

while (i < l1.Count || j < l2.Count)
{
if (i < l1.Count && j < l2.Count)

curr = (l1[i].Item1 < l2[j].Item1) ? l1[i++] : l2[j++];
else
curr = (i < l1.Count) ? l1[i++] : l2[j++];

if (curr.Item1 < p.Item2)
p = Tuple.Create(p.Item1, Math.Max(p.Item2, curr.Item2));
else
{
p = curr;
}
}

return result;
}``````

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

``````public class MergeIntervals {

static int[][] arr1 = new int[][] { { 3, 11 }, { 17, 25 }, { 58, 73 } };
static int[][] arr2 = new int[][] { { 6, 18 }, { 40, 47 } };
static int[][] arr3 = new int[arr1.length + arr2.length][];

/**
* @param args
*/
public static void main(String[] args) {

int i = 0;
int j = 0;
int k = 0;
int[] intersectionCheckInterval = null;
boolean isActiveIndexI = false; // This will tell with which array, we
// need to check
// intersection. This is useful in else case only when we already have
// an intersection
while (i < arr1.length && j < arr2.length) {
// If there was no previously known intersection to check current
// intervals with
if (intersectionCheckInterval == null) {
intersectionCheckInterval = getIntersectingInterval(arr1[i][0],
arr1[i][1], arr2[j][0], arr2[j][1]);
// If i and j do not intersect, select smaller interval and put
// into result array
if (intersectionCheckInterval == null) {
if (arr1[i][0] < arr2[j][0]) {
arr3[k++] = arr1[i++];
} else {
arr3[k++] = arr2[j++];
}
} else {
// If i and j intersect, we move ahead in i or j based on
// which
// interval had lesser high value
if (intersectionCheckInterval[1] == arr1[i][1]) {
j++;
isActiveIndexI = false;
} else {
i++;
isActiveIndexI = true;
}
}
} else {
// If we already have an intersection then
int[] temp = intersectionCheckInterval;
if (isActiveIndexI) {
intersectionCheckInterval = getIntersectingInterval(
intersectionCheckInterval[0],
intersectionCheckInterval[1], arr1[i][0],
arr1[i][1]);
if (intersectionCheckInterval == null) {
arr3[k++] = temp;
j++;
} else {
if (intersectionCheckInterval[1] == arr1[i][1]) {
j++;
isActiveIndexI = false;
} else {
i++;
isActiveIndexI = true;
}
}
} else {
intersectionCheckInterval = getIntersectingInterval(
intersectionCheckInterval[0],
intersectionCheckInterval[1], arr2[j][0],
arr2[j][1]);
if (intersectionCheckInterval == null) {
arr3[k++] = temp;
i++;
} else {
if (intersectionCheckInterval[1] == arr2[j][1]) {
i++;
isActiveIndexI = true;
} else {
j++;
isActiveIndexI = false;
}
}
}
}
}

if (i != arr1.length && j == arr2.length) {
while(i != arr1.length){
arr3[k++] = arr1[i++];
}
} else if (i == arr1.length && j != arr2.length) {
while(j != arr2.length){
arr3[k++] = arr2[j++];
}
}

for(int p=0;p<k;p++) {
System.out.println(arr3[p][0]+":"+arr3[p][1]);
}
}

static boolean isIntersecting(int low1, int high1, int low2, int high2) {
if (low1 >= low2 && low1 <= high2)
return true;
if (low2 >= low1 && low2 <= high1)
return true;
return false;
}

static int[] getIntersectingInterval(int low1, int high1, int low2,
int high2) {
int[] intersectInterval = null;
if (isIntersecting(low1, high1, low2, high2)) {
intersectInterval = new int[2];
intersectInterval[0] = Math.min(low1, low2);
intersectInterval[1] = Math.max(high1, high2);
}
return intersectInterval;
}

}``````

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

``````// C#
using System.Collections.Generic;

class Program
{
static void Main(string[] args)
{
Interval[] array1 = {
new Interval { Lower = 3, Upper = 11 },
new Interval { Lower = 17, Upper = 25 },
new Interval { Lower = 58, Upper = 73 } };

Interval[] array2 = {
new Interval { Lower = 6, Upper = 18 },
new Interval { Lower = 40, Upper = 47 }};

foreach (Interval r in Merge(array1, array2))
System.Console.Write("[" + r.Lower.ToString() + ", " + r.Upper.ToString() + "] ");
}

static Interval[] Merge(Interval[] array1, Interval[] array2)
{
List<Interval> result = new List<Interval>();

int i1, i2;
Interval currentInterval = new Interval(), selectedInterval = new Interval();

for (i1 = 0, i2 = 0; i1 < array1.Length || i2 < array2.Length;)
{
if (i1 < array1.Length && (i2 == array2.Length || array1[i1].Lower < array2[i2].Lower))
{
selectedInterval = array1[i1];
++i1;
}
else if (i2 < array2.Length && (i1 == array1.Length || array2[i2].Lower <= array1[i1].Lower))
{
selectedInterval = array2[i2];
++i2;
}

if (currentInterval.Upper >= selectedInterval.Lower)
{
if (currentInterval.Upper < selectedInterval.Upper)
currentInterval.Upper = selectedInterval.Upper;
}
else
{
currentInterval = selectedInterval;
}
}

result.RemoveAt(0);

return result.ToArray();
}
}

struct Interval
{
public int Lower;
public int Upper;
}``````

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

``````//Using LinkedLists with worst case time complexity of O(N+M) and space complexity //O(N+M)

public class IntervalOperations
{

public static Interval mergeIntervals(Interval a,Interval b)throws NullPointerException{
if(a==null||b==null)
{
throw new NullPointerException
}
Interval i=a;
Interval prevA=a;
Interval j=b;
Interval prevB=b;
Interval result;
Interval c;
if(a.start<=b.start)
{
result=i;
c=i;
prevA=i;
i=i.next;
}else
{
result=j;
c=j;
prevB=j;
j=j.next;
}
c.next=null;
while(i!=null && j!=null){
if(i.start<=j.start)
{
if(isOverlap(c,i))
{
c.start=Math.min(c.start,i.start);
c.end=Math.max(c.end,i.end);
prevA=i;
i=i.next;
}else{
prevA.next=null;
c.next=i;
c=c.next;
i=i.next;
c.next=null;
}
}else{
if(isOverlap(c,j))
{
c.start=Math.min(c.start,j.start);
c.end=Math.max(c.end,j.max);
prevB=j;
j=j.next;
}
prevB.next=null;
c.next=j;
c=c.next;
j=j.next;
c.next=null;
}

}

while(j!=null)
{
if(isOverlap(c,j))
{
c.start=Math.min(c.start,j.start);
c.end=Math.max(c.end,j.end);
prevB=j;
j=j.next;
}else{
prevB.next=null;
c.next=j;
c=c.next;
j=j.next;
c.next=null;

}
}
while(i!=null)
{
if(isOverlap(c,i))
{
c.start=Math.min(c.start,i.start);
c.end=Math.max(c.end,i.end);
prevA=i;
i=i.next;
}else{
prevA.next=null;
c.next=i;
c=c.next;
i=i.next;
c.next=null;
}
}
return result;

}

private static boolean isOverlap(Interval x,Interval y)
{
if(x.end<y.start||y.end<x.start)
{
return false;
}
return true;
}

public class Interval{
int start;
int end;
Interval next;
public Interal(int s,int e)
{
start=s;
end=e;
}
}

public static void printInterval(Interval a)
{
while(a!=null)
{
System.out.print("start: " + a.start + ", end: " + a.end + "-")
a=a.next;
}
}
public static void Main(String[] args)
{
Interval i=new Interval(3,10);
Interval v=i;
v.next=new Interval(12,15);
v=v.next;
v.next=new Interval(21,25);

Interval j=new Interval(6,10);
v=j;
v.next=new Node(11,18);

Interval result=IntervalOperations.mergeIntervals(i,j);

IntervalOperations.printInterval(i);
IntervalOperations.printInteval(j);
IntervalOperations.printInterval(result);
}
}``````

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

test

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

``````class Range:
def __init__(self, _min, _max):
self.min = _min
self.max = _max

def __str__(self):
return str(self.min) + "-" + str(self.max)

def __repr__(self):
return str(self)

def get_max(self):
return self.max

def get_min(self):
return self.min

def overlapping(self, other):
if (self.get_min() < other.get_min() < self.get_max()) \
or (self.get_min() < other.get_max() < self.get_max()) or \
(other.get_min() < self.get_min() < other.get_max()) \
or (other.get_min() < self.get_max() < other.get_max()):
return True
return False

def merge(self, other):
mmin = min(self.get_min(), other.get_min())
mmax = max(self.get_max(), other.get_max())
res = Range(mmin, mmax)
return res

def compare(self, other):
return cmp(self.min, other.min)

@staticmethod
def fix_array(index, array, retry=False):
if index > len(array):
return False
try:
left = array[index]
right = array[index + 1]
except Exception, e:
raise IndexError("fart")
if left.overlapping(right):
array.remove(left)
array.remove(right)
array.insert(index, left.merge(right))
if retry:
return Range.fix_array(index, array, retry=True)
return True

def merge(array1, array2):
result = []
result.extend(array1)
result.extend(array2)
result = sorted(result, cmp=Range.compare)
index = 0
while True:
try:
Range.fix_array(index, result, True)
index += 1
except IndexError, e:
return result

if __name__ == '__main__':
arr1 = [Range(3, 11), Range(17, 25), Range(58, 73)]
arr2 = [Range(6, 18), Range(40, 47)]
print merge(arr1, arr2)

arr1 = [Range(8, 13), Range(21, 32), Range(45, 60)]
arr2 = [Range(2, 9), Range(25, 46)]
print merge(arr1, arr2)

arr1 = [Range(1, 12), Range(26, 32), Range(51, 82)]
arr2 = [Range(9, 24), Range(49, 60), Range(75, 98)]
print merge(arr1, arr2)``````

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

Here is the java version

``````import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

/**
* Testing
* Created by joubin on 2/14/16.
*/
public class Range {
int min;
int max;

public Range(int min, int max) {
this.min = min;
this.max = max;
}

public int getMin() {
return min;
}

public void setMin(int min) {
this.min = min;
}

public int getMax() {
return max;
}

public void setMax(int max) {
this.max = max;
}

public boolean doesMerge(Range other) {
return (this.getMin() <= other.getMin() && other.getMin() <= this.getMax()) ||
(this.getMin() <= other.getMax() && other.getMax() <= this.getMax());
}

public void merge(Range other) {
this.setMin(Math.min(this.getMin(), other.getMin()));
this.setMax(Math.max(this.getMax(), other.getMax()));
}

private boolean after(Range range) {
return this.getMax() < range.getMin();
}

@Override
public boolean equals(Object obj) {
if (!(obj instanceof Range)) {
return false;
}
Range other = (Range) obj;
return this.getMin() == other.getMin() && this.getMax() == other.getMax();
}

@Override
public String toString() {
return this.min + "-" + this.max;
}

private int compare(Range p2) {
if (this.equals(p2)) {
return 0;
} else {
if (this.getMax() < p2.getMin()) {
return -1;
} else if (this.getMax() > p2.getMax()) {
return 1;
}
}
return 0;
}

public static class RangeCollection {
private List<Range> ranges = new ArrayList<>();

public RangeCollection(ArrayList<Range> ranges) {
}

int index = 0;
for (Range item : this.ranges) {
if (item.after(range)) {
index = this.ranges.indexOf(item);
} else {
break;
}
}
}

private void selfMerge() {
this.ranges.sort(Range::compare);
Range left = null;
Range right = null;
Iterator<Range> it = this.getRanges().iterator();
while (it.hasNext()) {
if (it.hasNext())
left = it.next();
if (it.hasNext())
right = it.next();
assert left != null;
assert right != null;
if (left.doesMerge(right)) {
left.merge(right);
this.ranges.remove(right);
it = ranges.iterator();
}
}

}

public List<Range> getRanges() {
return ranges;
}

for (Range item : this.ranges) {
if (item.doesMerge(range)) {
item.merge(range);
return;
}
}
this.selfMerge();
}

}

@Override
public String toString() {
return "" + ranges;
}
}

public static void main(String[] args) {
ArrayList<Range> rangeList1 = new ArrayList<Range>() {{

}};

ArrayList<Range> rangeList2 = new ArrayList<Range>() {{
}};

RangeCollection collection = new RangeCollection(rangeList1);

System.out.println(collection);

rangeList1 = new ArrayList<Range>() {{
}};
rangeList2 = new ArrayList<Range>() {{
}};

collection = new RangeCollection(rangeList1);
collection.selfMerge();

System.out.println(collection);

rangeList1 = new ArrayList<Range>() {{
}};
rangeList2 = new ArrayList<Range>() {{
}};

collection = new RangeCollection(rangeList1);
collection.selfMerge();

System.out.println(collection);

rangeList1 = new ArrayList<Range>() {{
}};
rangeList2 = new ArrayList<Range>() {{
}};

collection = new RangeCollection(rangeList1);
collection.selfMerge();

System.out.println(collection);

}

}``````

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

Here is the code in c++:

``````#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>

using namespace std;

class interval
{
public:
int start;
int end;

void set(int _start, int _end)
{
start=_start;
end=_end;
}

interval()
{

}
};

void merge_arrays_and_sort(interval a[10], interval b[10], interval sorted_res[20], int n, int m)
{
int co=0,i=0, j=0;

while(i<n && j<m)
{
if(a[i].start < b[j].start)
{
sorted_res[co]=a[i];
co++;
i++;
}
else
{
sorted_res[co]=b[j];
co++;
j++;
}
}

//left items in b
while(j<m)
{
sorted_res[co]=b[j];
j++;
co++;
}
//left items in a
while(i<n)
{
sorted_res[co]=a[i];
i++;
co++;
}

}

void merge_intervals(interval a, interval b, interval *new_interval)
{
interval bigger;
interval smaller;

if(a.start>b.start)
{
bigger.start=a.start;
bigger.end=a.end;
smaller.start=b.start;
smaller.end=b.end;
}
else
{
bigger.start=b.start;
bigger.end=b.end;
smaller.start=a.start;
smaller.end=a.end;
}

new_interval->start=smaller.start;
if(smaller.end>bigger.end)
{
new_interval->end=smaller.end;
}
else
{
new_interval->end=bigger.end;
}

}

bool overlap(interval a, interval b)
{
if(a.start<b.start)
{
if(b.start<a.end)
{
return true;
}
else
{
return false;
}
}
else if(a.start > b.start)
{
if(a.start>b.start)
{
if(a.start < b.end)
return true;
else
return false;

}
else
return false;
}
else  //start equally at same minute
return true;
}
void combin_intervals(interval arr[20], interval res[20], int *co, int n)
{

*co=0;
int i=1;
interval current;

current.start=arr[0].start;
current.end=arr[0].end;

while(i<n)
{

if(overlap(current, arr[i])==true)
{

interval new_interval;

merge_intervals(current, arr[i], &new_interval);

current.start=new_interval.start;
current.end=new_interval.end;
i++;
}
else
{
res[*co]=current;
*co=*co+1;
current=arr[i];
i++;
}
}
//left item
res[*co]=current;

}

int main()
{
interval a[10];
interval b[10];
interval sorted_arr[20];
interval result[20];
int n=3, m=2, result_co=0;

a[0].set(3, 11);
a[1].set(17, 25);
a[2].set(58, 73);

b[0].set(6, 18);
b[1].set(40, 47);

//1-merge arrays and sort them
merge_arrays_and_sort(a, b, sorted_arr, n, m);

cout<<"Merged and Sorted array:\n";
for(int i=0; i<m+n; i++)
cout<<sorted_arr[i].start<<"-"<<sorted_arr[i].end<<", ";

//2-combin intervals
combin_intervals(sorted_arr, result, &result_co, m+n);

cout<<"\nFinal Result:\n";

for(int i=0; i<=result_co; i++)
cout<<result[i].start<<"-"<<result[i].end<<", ";

return 0;
}``````

Comment hidden because of low score. Click to expand.
0

Steps:
1-Merge and sort both arrays (I didn't use a complicated sorting algorithm here since it's not requested)

2-Combin overlapping intervals in the resulted array.

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

``````# if possible merge tuple 't', otherwise insert 't' into the dictionary ('myData') of tuples
def mergeOrInsert(t, myData):

merge = False

for k in myData:

if k < t[0] and myData[k] > t[0]:
if t[1] > myData[k]:
myData[k] = t[1]
merge = True
break

if not merge:
myData[t[0]] = t[1]

def mergeXY(lhTuple1, lhTuple2):

myL = dict()

print(lhTuple1)
print(lhTuple2)
i = 0
j = 0

while True:

if i < len(lhTuple1) and j < len(lhTuple2):

n1 = lhTuple1[i]
n2 = lhTuple2[j]
if n1[0] < n2[0]:
nt = n1
i += 1
else:
nt = n2
j+= 1

else:

while i < len(lhTuple1):
mergeOrInsert(lhTuple1[i], myL)
i += 1
while j < len(lhTuple2):
mergeOrInsert(lhTuple2[j],myL)
j += 1

break
#break the while loop
merge = False
print(nt)
mergeOrInsert(nt, myL)

sL = sorted(myL.items(), key = lambda x: x[0])
print(sL)

x = [(3,8), (12, 19), (23, 45), (79, 99)]
y =[(6,18), (40, 65), (70, 101), (103, 110),  (115,200)]
mergeXY(x, y)

SAMPLE OUTPUT:
[(3, 19), (23, 65), (70, 101), (103, 110), (115, 200)]``````

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

``````class Interval
{
public \$start;
public \$end;

public function __construct(array \$pair)
{
\$this->start = \$pair[0];
\$this->end = \$pair[1];
}
}

function joinIntervals(array &\$result, Interval \$int)
{
if (count(\$result) == 0) {
\$result[] = \$int;
return;
}

\$last = end(\$result);
if (\$last instanceof Interval) {
if (\$last->end < \$int->start) \$result[] = \$int;
else \$last->end = \$int->end;
}
}

{
if (!is_array(\$list1) || !is_array(\$list2)) throw new InvalidArgumentException();

if (count(\$list2) == 0) return \$list1;
if (count(\$list1) == 0) return \$list2;

\$result = [];

\$pos1 = \$pos2 = 0;
while (\$pos1 < count(\$list1) || \$pos2 < count(\$list2)) {
if (\$pos2 == count(\$list2) || \$list1[\$pos1][0] <= \$list2[\$pos2][0]) {
joinIntervals(\$result, new Interval(\$list1[\$pos1]));
\$pos1++;
} elseif (\$pos1 == count(\$list2) || \$list1[\$pos1][0] > \$list2[\$pos2][0]) {
joinIntervals(\$result, new Interval(\$list2[\$pos2]));
\$pos2++;
}
}

return \$result;
}

\$list1 = [[3, 11], [17, 25], [26, 27], [29, 41], [58, 73]];
\$list2 = [[6, 18], [40, 47]];

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

``````class Interval
{
public \$start;
public \$end;

public function __construct(array \$pair)
{
\$this->start = \$pair[0];
\$this->end = \$pair[1];
}
}

function joinIntervals(array &\$result, Interval \$int)
{
if (count(\$result) == 0) {
\$result[] = \$int;
return;
}

\$last = end(\$result);
if (\$last instanceof Interval) {
if (\$last->end < \$int->start) \$result[] = \$int;
else \$last->end = \$int->end;
}
}

{
if (!is_array(\$list1) || !is_array(\$list2)) throw new InvalidArgumentException();

if (count(\$list2) == 0) return \$list1;
if (count(\$list1) == 0) return \$list2;

\$result = [];

\$pos1 = \$pos2 = 0;
while (\$pos1 < count(\$list1) || \$pos2 < count(\$list2)) {
if (\$pos2 == count(\$list2) || \$list1[\$pos1][0] <= \$list2[\$pos2][0]) {
joinIntervals(\$result, new Interval(\$list1[\$pos1]));
\$pos1++;
} elseif (\$pos1 == count(\$list2) || \$list1[\$pos1][0] > \$list2[\$pos2][0]) {
joinIntervals(\$result, new Interval(\$list2[\$pos2]));
\$pos2++;
}
}

return \$result;
}

\$list1 = [[3, 11], [17, 25], [26, 27], [29, 41], [58, 73]];
\$list2 = [[6, 18], [40, 47]];

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

``````import java.io.*;
import java.util.*;

class Range {
private int min, max;

public Range(int min, int max) {
this.min = min;
this.max = max;
}

public int getMin() {
return min;
}

public int getMax() {
return max;
}

public void setMin(int min) {
this.min = min;
}

public void setMax(int max) {
this.max = max;
}
}

class Solution {

public static List<Range> mergeRangesArrays(List<Range> arr1, List<Range> arr2) {
List<Range> result = new ArrayList<Range>();
Range newRange;

int arr1Index = 0, arr2Index = 0;

while(arr1Index < arr1.size() && arr2Index < arr2.size()) {
if (arr1.get(arr1Index).getMin() <= arr2.get(arr2Index).getMin()) {
if (arr1.get(arr1Index).getMax() >= arr2.get(arr2Index).getMin()) {
if (arr1.get(arr1Index).getMax() >= arr2.get(arr2Index).getMax()) {
newRange = new Range(arr1.get(arr1Index).getMin(), arr1.get(arr1Index).getMax());
} else {
newRange = new Range(arr1.get(arr1Index).getMin(), arr2.get(arr2Index).getMax());
}
arr1Index++;
arr2Index++;
} else {
newRange = new Range(arr1.get(arr1Index).getMin(), arr1.get(arr1Index).getMax());
arr1Index++;
}

} else {// (arr1[arr1Index].getMin() > arr2[arr2Index].getMin())
if (arr2.get(arr2Index).getMax() >= arr1.get(arr1Index).getMin()) {
if (arr1.get(arr1Index).getMax() >= arr2.get(arr2Index).getMax()) {
newRange = new Range(arr2.get(arr2Index).getMin(), arr1.get(arr1Index).getMax());
} else {
newRange = new Range(arr2.get(arr1Index).getMin(), arr2.get(arr2Index).getMax());
}
arr1Index++;
arr2Index++;
} else {
newRange = new Range(arr2.get(arr2Index).getMin(), arr2.get(arr2Index).getMax());
arr2Index++;
}
}
}

while (arr1Index < arr1.size()) {
arr1Index++;
}

while (arr2Index < arr2.size()) {
arr2Index++;
}

List<Range> actualResult = new ArrayList<Range>();

for (int i = 0; i < result.size(); i++) {
Range tmpRange = new Range(result.get(i).getMin(), result.get(i).getMax());
while (i < result.size() - 1 && tmpRange.getMax() >= result.get(i + 1).getMin()) {
tmpRange.setMax(result.get(i + 1).getMax());
i++;
}
}

return actualResult;
}

public static void main(String[] args) {
List<Range> arr1 = new ArrayList<Range>();
List<Range> arr2 = new ArrayList<Range>();

List<Range> result = mergeRangesArrays(arr1, arr2);

for (int i = 0; i < result.size(); i++) {
System.out.println("[" + result.get(i).getMin() + ", " + result.get(i).getMax() + "]");
}
}
}``````

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

Javascript: I wrote a version as if the ranges were strings

``````Arr1 = ["3-11", "17-25", "58-73"];
Arr2 = ["6-18", "40-47"];

function intersect(Arr1,Arr2){
arr = Arr1.concat(Arr2);
var index = 0;
var lastLength = 0;

for(var i=0;i<arr.length;i++){
if(index !== i){
var f1 = Number(arr[index].match(/\b\d+/));
var l1 = Number(arr[index].match(/\-\d+/)[0].substring(1));
var f2 = Number(arr[i].match(/\b\d+/));
var l2 = Number(arr[i].match(/\-\d+/)[0].substring(1));

if(f2<f1 && l2>f1){
foundOne(index,i,arr);
break;
}else if(f1<f2 && l1>f2){
foundOne(index,i,arr);
break;
}else{
}
}
}
}

function foundOne(index,i,arr){
var first = f1<f2 ? f1 : f2;
var last = l1>l2 ? l1 : l2;

arr[i] = first + "-" + last;
arr.splice(index,1);
lastLength = arr.length;
}

return arr.sort();
}``````

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

``````#!/usr/bin/perl

use Data::Dumper;
use strict;

#
# within range  start_element < first < end_element  AND new-range  existing end_element < first
#
my @array1 = ([17..25],[3..11],[58..73]);
my @array2 = ([6..18],[0..47],[101..1000]);

my %set;
my %hash ;
my @set_define ;
my \$count = 1;
foreach  my \$each_set ((@array1,@array2)) {
map {\$hash{\$_}++} @{\$each_set};
}

my \$temp ;
foreach my \$keys (sort {\$a<=>\$b} keys %hash) {
if (\$temp) {
my \$diff = \$keys - \$temp ;
if ( \$diff > 1) {
push @{\$set{++\$count}}, \$keys ;
} else {
push @{\$set{\$count}}, \$keys ;
}
} else {
push @{\$set{\$count}}, \$keys ;
}
\$temp = \$keys;
}

foreach my \$array (sort {\$a<=>\$b} keys %set) {
my \$first = \$set{\$array}->[0];
my \$last = \$set{\$array}->[-1];
push @set_define, [\$first."..".\$last];
}

map {print "[",@{\$_},"] "; } @set_define;``````

O/P :- [0..47] [58..73] [101..1000]

It is the one of the easiest way to solve this algorithm, using associative array ( hash ).

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

``````#!/usr/bin/perl

use Data::Dumper;
use strict;

#
# within range  start_element < first < end_element  AND new-range  existing end_element < first
#
my @array1 = ([17..25],[3..11],[58..73]);
my @array2 = ([6..18],[0..47],[101..1000]);
## O/P array3 = ([3..25],[40..47],[58..73]);

my %set;
my %hash ;
my @set_define ;
my \$count = 1;
foreach  my \$each_set ((@array1,@array2)) {
map {\$hash{\$_}++} @{\$each_set};
}

my \$temp ;
foreach my \$keys (sort {\$a<=>\$b} keys %hash) {
if (\$temp) {
my \$diff = \$keys - \$temp ;
if ( \$diff > 1) {
push @{\$set{++\$count}}, \$keys ;
} else {
push @{\$set{\$count}}, \$keys ;
}
} else {
push @{\$set{\$count}}, \$keys ;
}
\$temp = \$keys;
}

foreach my \$array (sort {\$a<=>\$b} keys %set) {
my \$first = \$set{\$array}->[0];
my \$last = \$set{\$array}->[-1];
push @set_define, [\$first."..".\$last];
}

map {print "[",@{\$_},"] "; } @set_define;``````

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

If we implement this using Interval-Tree would have been more generic a solution.

``````#include <stdio.h>

typedef struct _Interval{
int low;
int high;
}interval;

bool doOverlap(interval i, interval j){
return (i.low <= j.high && j.low <= i.high) ? true: false;
}
void findAllOverlaps(interval *arr, interval j, int size, interval *ret, int *ii){
for (int i = 0; i < size; i++){
if (doOverlap(arr[i], j))
ret[(*ii)++] = arr[i];
}
}
int main(){
interval arr1[3] = { { 3, 11 }, { 17, 25 }, { 58, 73 } };
interval arr2[2] = { { 6, 18 }, { 40, 47 } };
int next = 0;
interval temp[3];
for (int jj = 0; jj < 2; jj++)
{
int j = 0;
findAllOverlaps(arr1, arr2[jj], 3, temp, &j);
next += j;
if (j > 0){
arr1[jj].low = temp[0].low;
arr1[jj].high = temp[j - 1].high;
}
else arr1[jj] = arr2[jj];
}
for (int jj = next; jj < SIZE; jj++)
arr1[jj] = arr1[jj];
for (int i = 0; i < SIZE; i++)
printf("%d-%d ",arr1[i].low, arr1[i].high);
return 0;
}``````

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

Keep merging data from both list , insert first interval with lesser start

Arr1 = [3-11, 17-25, 58-73];
Arr2 = [6-18, 40-47];

Arr3 = 3-11,

Arr1 = 17-25,58-73
Arr2 = 6-18,40-47

when inserting next interval check if curlow <= A3.high && curhigh >A3.high, if so update A3.high, else add (curlow-curhigh) to list

A3 = 3,18
Arr1 = 17-25,58-73
Arr2 = 40-47

A3 = 3,25
Arr1 = 58-73
Arr2 = 40-47

A3 = 3,25, 40-47, 58-73

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

Shorter solution in python using generators:

``````def mergeit(list1, list2):
p1, p2 = 0, 0
while p1 < len(list1) or p2 < len(list2):
if p2 >= len(list2) or list1[p1] < list2[p2]:
yield list1[p1]
p1 += 1
else:
yield list2[p2]
p2 += 1

def merge(list1, list2):
current = None
for seg in mergeit(list1, list2):
if current is None:
current = seg
else:
if seg[0] > current[1]:
yield current
current = seg
elif seg[1] > current[1]:
current = (current[0], seg[1])
else:
pass
if current is not None:
yield current

print(list(merge([(3,11), (17,25), (58,73)], [(6,18),(40,47)])))
# Output: [(3, 25), (40, 47), (58, 73)]``````

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

python version

``````def merge(left, right):
p_left = 0
p_right = 0
result = []

if left[p_left][0] <= right[p_right][0]:
start = left[p_left][0]
end = left[p_left][1]
p_left +=1
else:
start = right[p_right][0]
end = right[p_right][1]
p_right += 1

while p_left < len(left) or p_right < len(right):
if p_left < len(left) and start <= left[p_left][0] and end >= left[p_left][0]:
end = max(end, left[p_left][1])
p_left += 1
elif p_right < len(right) and start <= right[p_right][0] and end >= right[p_right][0]:
end = max(end, right[p_right][1])
p_right += 1
else:
result.append((start, end))

if p_left < len(left) and p_right < len(right):
start = min(left[p_left][0], right[p_right][0])
end = left[p_left][1] if start == left[p_left][0] else right[p_right][1]
elif p_left < len(left):
start = left[p_left][0]
end = left[p_left][1]
else:
start = right[p_right][0]
end = right[p_right][1]

result.append((start, end))

return result``````

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

``````#include <iostream>
#include <vector>

using std::cout;
using std::vector;

// arr1 = [ 3-11, 17-25, 58-73 ]
// arr2 = [ 6-18, 40-47 ]

vector<int> * merge_arrays(const vector<int>& arr1, const vector<int>& arr2) {
vector<int> * merged = new vector<int>();

auto i = arr1.begin();
auto j = arr2.begin();

while (i != arr1.end() || j != arr2.end()) {
if (j == arr2.end() || *i < *j) {
merged->push_back(*i);
++i;
} else if (i == arr1.end() || *j < *i) {
merged->push_back(*j);
++j;
} else {
merged->push_back(*i);
++i;
++j;
}
}
return merged;
}``````

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

Simple solution using two pointers.
Time Complexity: O(n). Space complexity: O(1) (no extra memory except the return merged intervals).

``````struct Interval{
int begin, end;
Interval(int begin, int end){
this->begin = begin;
this->end = end;
}
};

void merge_interval(vector<Interval*> &intervals, Interval* to_be_merged){
int n = (int) intervals.size();
if(n == 0){
intervals.push_back(to_be_merged);
return;
}

if(to_be_merged->begin > intervals[n-1]->end){
intervals.push_back(to_be_merged);
}else{
intervals[n-1]->end = max(intervals[n-1]->end, to_be_merged->end);
}
}
vector<Interval*> merge_intervals(vector<Interval*> &intervals1, vector<Interval*> &intervals2){
if(intervals1.size() == 0){
return intervals2;
}
if(intervals2.size() == 0){
return intervals1;
}
vector<Interval*> merged_intervals;
// now we are sure that none of them is empty.
int i=0, j =0;
while(i < intervals1.size() && j < intervals2.size() ){
if(intervals1[i]->begin < intervals2[j]->begin){
merge_interval(merged_intervals, intervals1[i++]);
}else{
merge_interval(merged_intervals, intervals2[j++]);
}
}

while(i < intervals1.size()){
merge_interval(merged_intervals, intervals1[i++]);
}
while(j < intervals2.size()){
merge_interval(merged_intervals, intervals2[j++]);
}
return merged_intervals;
}``````

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

def merge(arr1, arr2):
#return Array
arr3 = []
while len(arr1) > 0 and len(arr2) > 0:
a1 = [int(x) for x in arr1[0].split("-")]
a2 = [int(x) for x in arr2[0].split("-")]

if a1[0] < a2[0]:
m = a1
del arr1[0]
else:
m = a2
del arr2[0]

if len(arr3) == 0:
arr3.append(m)
else:
if m[0] < arr3[-1][1]:
arr3[-1][1] = m[1]
else:
arr3.append(m)
#
if len(arr1)>0:
a1 = [int(x) for x in arr1[0].split("-")]
if len(arr3) > 0 and a1[0] < arr3[-1][1] :
arr3[-1][1] = a1[1]
del arr1[0]
if len(arr1) > 0:
for a1 in arr1:
arr3.append([int(x) for x in arr1[0].split("-")])
else:
a2 = [int(x) for x in arr2[0].split("-")]
if len(arr3) > 0 and a2[0] < arr3[-1][1]:
arr3[-1][1] = a2[1]
del arr2[0]
if len(arr2) > 0:
for a2 in arr2:
arr3.append([int(x) for x in arr2[0].split("-")])

for a3 in arr3:
a3 = str(a3[0])+"-"+str(a3[1])

return arr3

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

``````function merge(intervals1, intervals2) {
const ascendingByStart = []
let i = 0
let j = 0
while (i < intervals1.length || j < intervals2.length) {
if (i === intervals1.length) {
ascendingByStart.push(intervals2[j++])
} else if (j === intervals2.length) {
ascendingByStart.push(intervals1[i++])
} else if (intervals1[i][0] < intervals2[j][0]) {
ascendingByStart.push(intervals1[i++])
} else {
ascendingByStart.push(intervals2[j++])
}
}
const mergedIntervals = []
let start = null
let end = null
for (const interval of ascendingByStart) {
if (start === null && end === null) {
start = interval[0]
end = interval[1]
continue
}
if (start < interval[0] && interval[0] < end) {
end = Math.max(interval[1], end)
} else {
mergedIntervals.push([start, end])
start = interval[0]
end = interval[1]
}
}
if (start !== null && end !== null) {
mergedIntervals.push([start, end])
}
return mergedIntervals
}

// some overlap, no full containment
console.log(merge(
[[3, 11], [17, 25], [58, 73]],
[[6, 18], [40, 47]]
))

// some intervals fully contained in others
console.log(merge(
[[4, 5], [7, 9], [10, 15]],
[[3, 8], [11, 13]]
))``````

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

No need for sorting, similar to merging sorted arrays in merge sort just we need to consider ranges

``````package com.example.test;

import java.util.ArrayList;
import java.util.List;

public class MergeSortedArrays {

class Range {
int min;
int max;

public Range(int min, int max) {
this.min = min;
this.max = max;
}
}

public List<Range> mergeSortedArrays(List<Range> arr1, List<Range> arr2) {

if(arr1 == null || arr2 == null)
return null;

if(arr1.size() == 0)
return arr2;

if(arr2.size() == 0)
return arr1;

List<Range> result = new ArrayList<Range>();
int length1 = arr1.size();
int length2 = arr2.size();
Range lastNode = null;
int count = 0, i = 0, j = 0;

while(i < length1 && j < length2) {

Range current = null;

if(arr1.get(i).min < arr2.get(j).min) {
current = arr1.get(i);
i++;
}
else {
current = arr2.get(j);
j++;
}

if(lastNode != null) {
if(lastNode.max >= current.min) {
result.get(count-1).max = current.max;
continue;
}
}
lastNode = current;
count++;
}

while(i < length1) {
i++;
}

while(j < length2) {
j++;
}
return result;
}

public static void main(String args[]) {
MergeSortedArrays mergeArray = new MergeSortedArrays();
List<Range> range1 = new ArrayList<Range>();
List<Range> range2 = new ArrayList<Range>();

List<Range> res = mergeArray.mergeSortedArrays(range1, range2);

if(res != null) {
for(Range r : res) {
System.out.println("["+r.min + "," + r.max+"]");
}
}
}
}``````

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

``````package com.example.test;

import java.util.ArrayList;
import java.util.List;

public class MergeSortedArrays {

class Range {
int min;
int max;

public Range(int min, int max) {
this.min = min;
this.max = max;
}
}

public List<Range> mergeSortedArrays(List<Range> arr1, List<Range> arr2) {

if(arr1 == null || arr2 == null)
return null;

if(arr1.size() == 0)
return arr2;

if(arr2.size() == 0)
return arr1;

List<Range> result = new ArrayList<Range>();
int length1 = arr1.size();
int length2 = arr2.size();
Range lastNode = null;
int count = 0, i = 0, j = 0;

while(i < length1 && j < length2) {

Range current = null;

if(arr1.get(i).min < arr2.get(j).min) {
current = arr1.get(i);
i++;
}
else {
current = arr2.get(j);
j++;
}

if(lastNode != null) {
if(lastNode.max >= current.min) {
result.get(count-1).max = current.max;
continue;
}
}
lastNode = current;
count++;
}

while(i < length1) {
i++;
}

while(j < length2) {
j++;
}
return result;
}

public static void main(String args[]) {
MergeSortedArrays mergeArray = new MergeSortedArrays();
List<Range> range1 = new ArrayList<Range>();
List<Range> range2 = new ArrayList<Range>();

List<Range> res = mergeArray.mergeSortedArrays(range1, range2);

if(res != null) {
for(Range r : res) {
System.out.println("["+r.min + "," + r.max+"]");
}
}
}
}``````

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

It's quite a straightforward, No need to complicate it.
Logic: Use two pointers & a queue.
Steps:
1. Start each pointer from the start of the list.
2. If the queue is empty, compare the pointers such that
2.1 If the interval overlap, insert the new interval inside the queue and increment the pointers.
2.2 Insert the lower interval into the list and increment that pointer.
3. Compare both the pointers with the head of the queue. Dequeue & enqueue if required.
4. Repeat this process until all intervals are covered.

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

I have done a JavaScript solution that is O(n log n) due to the sort.

``````function getNonIntersetingArrayMerge(first, second) {
var workingItem;
var items = first.concat(second);
var results = [];

items.map(function (val, index, array) {
array[index] = val.split('-').map(Number);
});

items.sort(function (a, b) {
return a[0] - b[0];
});

workingItem = items.splice(0,1)[0];

while(items.length > 0) {
item = items.splice(0,1)[0];

if (item[0] < workingItem[1]) {
workingItem[1] = item[1];
continue;
}

results.push(workingItem);
workingItem = item;
}

results.push(workingItem);

results.map(function (val, index, array) {
array[index] = val.join('-');
});
return results;
}

var first = ['3-11', '17-25', '58-73'];
var second = ['6-18', '40-47'];

getNonIntersetingArrayMerge(first, second);``````

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

``````O(|arr1| + |arr2|) solution in java

static ArrayList<int[]> merge(int[][] arr1, int[][] arr2) {
ArrayList<int[]> result = new ArrayList<>();

boolean arr1Empty= arr1==null || arr1.length==0;
boolean arr2Empty= arr2==null || arr2.length==0;

if(arr1Empty && arr2Empty ) {
return result;
}else if ( arr1Empty) {
return result;
}else if ( arr2Empty) {
return result;
}

int i= 0, j= 0;
int start= -1, end = -1;

while( i<arr1.length && j < arr2.length){
if( arr1[i][0] < arr2[j][0] ) {
if(end < arr1[i][0]) {
if(start!=-1) {
}
start = arr1[i][0];
end = arr1[i][1];
}else{
end =  arr1[i][1];
}
i++;
}else{
if(end < arr2[j][0]) {
if(start!=-1) {
}
start = arr2[j][0];
end = arr2[j][1];
}else{
end =  arr2[j][1];
}
j++;
}
}

if(i<arr1.length || j<arr2.length) {
}

while( i<arr1.length ){
i++;
}

while( j<arr2.length ){
j++;
}

return result;
}``````

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.

### 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.