## Amazon Interview Question

Software Engineer in Tests**Country:**India

**Interview Type:**In-Person

package com.test;

import java.util.*;

public class MyOverLapRange {

public static void main (String args[]){

int a []={0,3,1,5,7,9,8,13};

Map<Integer, Integer> b= new HashMap<Integer, Integer>();

List<Integer> finalNonOverLapInerval =new ArrayList<Integer>();

boolean isInterval=true;

//put the integers in pairs

for (int i=0 ;i< a.length;i++)

{

if (i<a.length/2){

if ( i==0){

b.put(a[i], a[i+1]);

}

else{

b.put(a[i+i], a[i+i+1]);

}

}

}

//loop over elements of array to see if occur in any of the interval in this style x<a<y

//if not add them to a non-overlapping intervals

for (int i=0 ;i< a.length;i++){

isInterval=true;

//uncomment to trace values

// System.out.println("a = " + i + ", Value = " + a[i]);

Iterator<Map.Entry<Integer, Integer>> entries = b.entrySet().iterator();

while (entries.hasNext()) {

Map.Entry<Integer, Integer> entry = entries.next();

//uncomment to trace values

// System.out.println("Key = " + entry.getKey() + ", Value = " + entry.getValue());

if ( entry.getKey()< a[i] && a[i]< entry.getValue()){

isInterval=false;

}

}

if (isInterval){

finalNonOverLapInerval.add(a[i]);

}

}

//printing the non-overlapping intervals

for (int i=0 ;i< finalNonOverLapInerval.size();i++){

System.out.println("result["+i+"]: "+finalNonOverLapInerval.get(i));

}

}

}

please shaik tell me if i am wrong,

Here ranges are {0 to 3}, {1 to 5}, {5 to 7}, {7 to 9}, {8 to 13}

if so then how the output comes to be this one {0,5,7,13}

this require {0 to 5} to be a range, if so then why can't we take {0 to 13} as a range.

Let me explain it again, the first element which is 0 is the starting pointing of the line and the 2nd element which is 3 is the end point of the line. Draw a line from 0 to 3. Now take the 2nd of elements that is 1 and 5, now draw a line from 1 to 5, notice that the 1 is between 0 and 3 range which means the the line overlaps from 1 to 3 so now the starting point is 0 and the new end point is 5 excluding the overlapped points.

I hope this is clear.

Now, take the 3rd set of numbers which are 7 and 9, now draw a line from 7 to 9, notice that it doesn't overlap with the previous ranges. Again take the next set of elements that is 8 and 13, draw line from 8 to 13, notice that 8 is between 7 and 9, so there is an overlap from 8 to 9. Now exclude 8 and 9 since they overlap and take the start point 7 and the new end point will be 13.

I hope it is now clear.

Maybe I am not understanding the question correctly, but why can you not do something simple like the code I have below. You can simply iterate over the array once, which and get all of the values you need. Basically it will given you the end points of each non-overlapping arrays of a given range.

```
public class arrayTest {
public static void main(String args[]) {
int[] a = {0,3,1,5,7,9,8,13};
int range = 3;
for (int i = 0;i<a.length;i++) {
if ((i%(range+1)==range) || ((i%(range+1)) ==0)) {
System.out.println(a[i]);
}
if (i == (a.length-1) && ((i % (range+1)) != range)) {
System.out.println(a[i]);
}
}
}
}
```

Let me explain it again, the first element which is 0 is the starting pointing of the line and the 2nd element which is 3 is the end point of the line. Draw a line from 0 to 3. Now take the 2nd of elements that is 1 and 5, now draw a line from 1 to 5, notice that the 1 is between 0 and 3 range which means the the line overlaps from 1 to 3 so now the starting point is 0 and the new end point is 5 excluding the overlapped points.

I hope this is clear.

Now, take the 3rd set of numbers which are 7 and 9, now draw a line from 7 to 9, notice that it doesn't overlap with the previous ranges. Again take the next set of elements that is 8 and 13, draw line from 8 to 13, notice that 8 is between 7 and 9, so there is an overlap from 8 to 9. Now exclude 8 and 9 since they overlap and take the start point 7 and the new end point will be 13.

I hope it is now clear.

```
void NonOverlappingRanges(int[] arr)
{
int min = 0;
int max = 1;
for (int i = 2; i < arr.Length; i += 2)
{
if (arr[i] < arr[max])
{
if (arr[i + 1] <= arr[max])
{
arr[i] = -1;
arr[i + 1] = -1;
}
else
{
arr[max] = arr[i] = -1;
max = i + 1;
}
}
else
{
min = i;
max = i + 1;
}
}
for (int i = 0; i < arr.Length; i++)
{
if(arr[i]!=-1)
Console.WriteLine(arr[i]);
}
}
```

import java.util.LinkedList;

import java.util.List;

public class OverLappingRanges {

public static void main(String[] args) {

int inpranges[] = {0,3,1,5,7,9,8,13};

List<Range> listR = new LinkedList<Range>();

for(int i=0;i<inpranges.length/2;i++){

Range r = new Range(inpranges[i*2], inpranges[i*2+1]);

listR.add(r);

}

List<Range> finalRanges = new LinkedList<Range>();

Range prev = listR.get(0);

int i =1;

while(i< listR.size()){

Range curr = listR.get(i);

if(prev.low<= curr.low && prev.high >= curr.low){

prev.high = Math.max(prev.high, curr.high);

}else{

finalRanges.add(prev);

prev = curr;

}

i++;

}

finalRanges.add(prev);

for (Range range : finalRanges) {

System.out.print(range.low+" "+range.high+" ");

}

System.out.println();

}

}

class Range{

int low;

int high;

public Range(int low, int high){

this.low = low;

this.high = high;

}

}

Scala:

```
Assuming input in tuple format:
def nonOvrLapping(a: Array[(Int, Int)],r: Array[Int]): Array[Int] = a match {
case Array() => r
case Array(x,y,z@_*) if(x._2 > y._1) => nonOvrLapping(z.toArray, (r:+x._1):+y._2)
case Array(x,y,z@_*) => nonOvrLapping(z.toArray,r)
}
scala> nonOvrLapping(Array((0,3), (1,5), (7,9), (8,13)), Array())
res49: Array[Int] = Array(0, 5, 7, 13)
```

```
public class rengetest
{
public static void main(String[] args)
{
int[] A = { 0, 3, 1, 5, 7, 9, 8, 13 };
for (int i = 1; i < A.length; i += 2)
{
int rangeStart = A[i - 1];
int rangeEnd = A[i];
for (int l = rangeStart; l <= rangeEnd; l++)
{
boolean isInRange = false;
for (int j = 1; j < A.length; j += 2)
{
int internalRangeStart = A[j - 1];
int internalRangeEnd = A[j];
isInRange = isInRange(l, internalRangeStart,
internalRangeEnd);
if (isInRange)
{
break;
}
}
if (isInRange == false)
{
System.out.println(l);
}
}
}
}
public static boolean isInRange(int number, int rangestart, int rangeEnd)
{
if (number > rangestart && number < rangeEnd)
{
return true;
}
return false;
}
}
```

If input is not sorted,sort it with begin time inc

```
def unionranges(array):
start = array[0]
end = array[1]
result = []
for i in xrange(2,len(array),2):
if array[i] > end:
result.append((start,end))
start = array[i]
end = array[i+1]
else:
if array[i+1] > end:
end = array[i+1]
result.append((start,end))
return result
```

import java.util.*;

public class Overlap {

public Overlap() {

// TODO Auto-generated constructor stub

}

public static Set<Integer> fixOverLap(int[]A){

Set<Integer> newList = new LinkedHashSet<Integer>();

int pre=0;

for (int i=1;i<A.length+1;i++)

{

if (i==(A.length))

{

if (A[i-1]>pre)

{

newList.add(A[i-1]);

}

break;

}

if (A[i-1]<=A[i])

{

newList.add(A[i-1]);

pre=A[i-1];

}

else{

i+=1;

}

}

return newList;

}

public static void main(String[] args) {

// TODO Auto-generated method stub

int []A={0,3,1,5,7,9,8,13};

System.out.println(fixOverLap(A));

}

}

private int[] NonoverlappingArray(int[] ArrayInput)

{

int[] ArrayOutput = new int(1000); //suppose the entries are <1000

for(int i=1;i<ArrayInput.length()-1;i++)

{

if(ArrayInput[i] > ArrayInput[i-1] && ArrayInput[i] < ArrayInput[i+1])

{

ArrayOutput[i] = ArrayInput[i];

}

else if(ArrayInput[i] < ArrayInput[i-1] && ArrayInput[i] > ArrayInput[i+1])

{

ArrayOutput[i] = ArrayInput[i];

}

}

return ArrayOutput.RemoveNull();

}

hi shaik,

- Anonymous November 25, 2012is the array given is having ranges in sorted order or not??

unsorted can be {0,3,7,9,1,5,8,13}