## Amazon Interview Question for Software Developers

• 0

Country: India

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

There is a nice explanation for the linear time solution of this problem on geeksforgeeks

www.geeksforgeeks.org/given-an-array-arr-find-the-maximum-j-i-such-that-arrj-arri

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

This is how I'd do it
optimizations
1: always start j after i so that we don need to check for i<j
2: i will always be less than size-max so that there is always a array that is larger than max to check for
3: j should start after i but also i+max so that the length of a[i], a[j] in comparison will never be smaller than max

``````public static void main(String[] args) {
Scanner in = new Scanner(System.in);

System.out.print("Enter the size of arr : ");
int size = in.nextInt();

int[] arr = new int[size];
for (int i = 0; i < size; i++) arr[i] = in.nextInt();

int max=0;
for(int i=0;i<size-max;i++)
for(int j=i+max+1;j<size;j++)
if (arr[i]<arr[j]&&j-i>max)
max=j-i;

System.out.println("the max length between a[i],a[j] where a[i]<a[j] is "+max);
}``````

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

unsigned int max_distance(const int arr [], unsigned int sz )
{

unsigned int gmax = 0;

if(sz <= 1)
return 0;

int prev = arr[0];

for(int i = 0; i < sz; i++ )
{
if(arr[i] > prev){
std::cout << "skipped " << arr[i] << "@ i = " << i << "\n";
continue;
}
unsigned int mdist=0;
for(int j = i; j < sz; j++)
{
if(arr[i] < arr[j])
mdist = (j-i);
}

prev = arr[i];
gmax = (gmax < mdist ? mdist : gmax);
}

return gmax;
}

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

``````unsigned int max_distance(const int arr [], unsigned int sz )
{

unsigned int gmax = 0;

if(sz <= 1)
return 0;

int prev = arr[0];

for(int i = 0; i < sz; i++ )
{
if(arr[i] > prev){
std::cout << "skipped " << arr[i] << "@ i =  " << i << "\n";
continue;
}
unsigned int mdist=0;
for(int j = i; j < sz; j++)
{
if(arr[i] < arr[j])
mdist = (j-i);
}

prev = arr[i];
gmax = (gmax < mdist ? mdist : gmax);
}

return gmax;
}``````

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

``````//Given an unsorted array find the maximum distance between two elements satisfying the condition A[i] < A[j] where i < j. There will always be a solution.
//
//        For eg. 6, 9, 3, 2, 10, 2, 3
//

import java.util.Scanner;
import java.util.stream.Stream;

public class ArrayMinMaxDistance {

private final int[] inputArray;

public ArrayMinMaxDistance(int[] input) {
this.inputArray = input;
}

public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);

System.out.println("Enter array");
int[] input = Stream.of(scanner.nextLine().split(", ")).mapToInt(Integer::parseInt).toArray();

ArrayMinMaxDistance arrayMinMaxDistance = new ArrayMinMaxDistance(input);

int output = arrayMinMaxDistance.findMaxDistance();
System.out.println(output);
}

private int findMaxDistance() {
int inputArrayLength = inputArray.length;
int[] minElementArray = new int[inputArrayLength];
int[] maxElementArray = new int[inputArrayLength];

minElementArray[0] = inputArray[0];
for (int i = 1; i < inputArrayLength; i++)
minElementArray[i] = Math.min(minElementArray[i-1], inputArray[i]);

maxElementArray[inputArrayLength - 1] = inputArray[inputArrayLength - 1];
for (int i = inputArrayLength - 2; i >= 0; i--)
maxElementArray[i] = Math.max(maxElementArray[i+1], inputArray[i]);

int minIndex = 0;
int maxIndex = 0;
int maxDistance = 0;
while(minIndex < inputArrayLength && maxIndex < inputArrayLength) {
if(minElementArray[minIndex] > maxElementArray[maxIndex]) {
minIndex++;
}
else {
maxDistance = Math.max(maxDistance, maxIndex - minIndex);
maxIndex++;
}
}
return maxDistance;
}
}``````

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

``````//Given an unsorted array find the maximum distance between two elements satisfying the condition A[i] < A[j] where i < j. There will always be a solution.
//
//        For eg. 6, 9, 3, 2, 10, 2, 3
//

import java.util.Scanner;
import java.util.stream.Stream;

public class ArrayMinMaxDistance {

private final int[] inputArray;

public ArrayMinMaxDistance(int[] input) {
this.inputArray = input;
}

public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);

System.out.println("Enter array");
int[] input = Stream.of(scanner.nextLine().split(", ")).mapToInt(Integer::parseInt).toArray();

ArrayMinMaxDistance arrayMinMaxDistance = new ArrayMinMaxDistance(input);

int output = arrayMinMaxDistance.findMaxDistance();
System.out.println(output);
}

private int findMaxDistance() {
int inputArrayLength = inputArray.length;
int[] minElementArray = new int[inputArrayLength];
int[] maxElementArray = new int[inputArrayLength];

minElementArray[0] = inputArray[0];
for (int i = 1; i < inputArrayLength; i++)
minElementArray[i] = Math.min(minElementArray[i-1], inputArray[i]);

maxElementArray[inputArrayLength - 1] = inputArray[inputArrayLength - 1];
for (int i = inputArrayLength - 2; i >= 0; i--)
maxElementArray[i] = Math.max(maxElementArray[i+1], inputArray[i]);

int minIndex = 0;
int maxIndex = 0;
int maxDistance = 0;
while(minIndex < inputArrayLength && maxIndex < inputArrayLength) {
if(minElementArray[minIndex] > maxElementArray[maxIndex]) {
minIndex++;
}
else {
maxDistance = Math.max(maxDistance, maxIndex - minIndex);
maxIndex++;
}
}
return maxDistance;
}
}``````

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

//Given an unsorted array find the maximum distance between two elements satisfying the condition A[i] < A[j] where i < j. There will always be a solution.
//
// For eg. 6, 9, 3, 2, 10, 2, 3
//

``````import java.util.Scanner;
import java.util.stream.Stream;

public class ArrayMinMaxDistance {

private final int[] inputArray;

public ArrayMinMaxDistance(int[] input) {
this.inputArray = input;
}

public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);

System.out.println("Enter array");
int[] input = Stream.of(scanner.nextLine().split(", ")).mapToInt(Integer::parseInt).toArray();

ArrayMinMaxDistance arrayMinMaxDistance = new ArrayMinMaxDistance(input);

int output = arrayMinMaxDistance.findMaxDistance();
System.out.println(output);
}

private int findMaxDistance() {
int inputArrayLength = inputArray.length;
int[] minElementArray = new int[inputArrayLength];
int[] maxElementArray = new int[inputArrayLength];

minElementArray[0] = inputArray[0];
for (int i = 1; i < inputArrayLength; i++)
minElementArray[i] = Math.min(minElementArray[i-1], inputArray[i]);

maxElementArray[inputArrayLength - 1] = inputArray[inputArrayLength - 1];
for (int i = inputArrayLength - 2; i >= 0; i--)
maxElementArray[i] = Math.max(maxElementArray[i+1], inputArray[i]);

int minIndex = 0;
int maxIndex = 0;
int maxDistance = 0;
while(minIndex < inputArrayLength && maxIndex < inputArrayLength) {
if(minElementArray[minIndex] > maxElementArray[maxIndex]) {
minIndex++;
}
else {
maxDistance = Math.max(maxDistance, maxIndex - minIndex);
maxIndex++;
}
}
return maxDistance;
}
}``````

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

``````I think this will work....
static int maxDistance(int[] arr) {
if (arr == null || arr.length < 2)
return -1;
int start = 0;
int end = arr.length - 1;

while (start < end) {
if (arr[start] < arr[end]) {
return end - start;
}
end--;

}
return -1;
}``````

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.