## Amazon Interview Question for Software Engineer in Tests

• 0

Country: India
Interview Type: In-Person

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

hi shaik,
is the array given is having ranges in sorted order or not??
unsorted can be {0,3,7,9,1,5,8,13}

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

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){

}
}

//printing the non-overlapping intervals
for (int i=0 ;i< finalNonOverLapInerval.size();i++){

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

}
}

}

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

Hi i found this solution

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

Hi,
I think the hashMap abstraction is not a good one for this question. A short nested Interval class will be better, isn't it?

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

The ranges are in sorted order, {0,3,1,5,7,9,8,13}

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

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.

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

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.

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

Thanks Rajkumari, it's working perfectly fine, I'm just trying to understand it now.

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

I can't understand the question. @shaik can you explain a bit more what is being asked?

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

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]);
}
}
}
}

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

can you elaborate what is being asked in the question.

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

can you explain the question

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

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.

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

int b[]={0,3,1,5,7,9,8,13};
int n=sizeof(b)/sizeof(b[0]);
for(i=0;i<=n/2;i+=2)
{
int j=i+2;
while(j<n-1)
{
if(b[j]>b[i] && b[j]<b[i+1])
printf("%d\t%d\n",b[i],b[j+1]);
else
break;
j+=2;
}
}

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

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]);
}
}

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

import java.util.List;

public class OverLappingRanges {

public static void main(String[] args) {
int inpranges[] = {0,3,1,5,7,9,8,13};
for(int i=0;i<inpranges.length/2;i++){
Range r = new Range(inpranges[i*2], inpranges[i*2+1]);
}

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{
prev = curr;
}
i++;
}

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;
}
}

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

I think A dynamic connectivity (Quick Union) approach would be a best fit for this problem. the union operation would group two ranges if they overlap else not.
The find operation would return the group (root) of the query group.

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

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)

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

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;
}

}

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

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

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

import java.util.*;
public class Overlap {

public Overlap() {
// TODO Auto-generated constructor stub
}

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

int pre=0;
for (int i=1;i<A.length+1;i++)
{
if (i==(A.length))
{

if (A[i-1]>pre)
{

}
break;
}

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

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));

}

}

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

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();
}

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.