## Amazon Interview Question for SDE-2s

Country: United States
Interview Type: In-Person

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

Hey @jim, your code fails when there is multiple rotations such as [1,9,0]. This example should be an ascending rotated array. I made a few edits to your code that fixes this problem. This implementation should cover all general test cases excluding single element arrays.

``````public static String displayTypeOfArray(int[] input) {
int descCount = 0;
int ascCount = 0;

for(int i=0;i<input.length-1;i++) {
if(input[i] <= input[i+1]) {
ascCount++;
} else if(input[i] > input[i+1]) {
descCount++;
}
}

if(descCount == 0) {
return "Ascending";
} else if(ascCount == 0) {
return "Descending";
}

if(ascCount == descCount) {//desc and asc could only be possibly same in arr of size 3. so they will both equal 1
//because of this, we can figure out if ascCount or descCount is greater by checking

if(input <= input){
ascCount++;
}
else{
descCount++;
}

}

if(ascCount > descCount) {
return "Ascending Rotated";
} else if (ascCount < descCount){
return "Descending Rotated";
}
return null;
}``````

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

Pretty simple algorithm. First look at the first 2 numbers. That will tell you if if its ascending or descending.

Then go through the rest of the array and if you see it descending when you've already detected it to be ascending, then its rotated. Same with the other scenario.

Code:

``````private static String findOrder(int [] arr)
{
boolean isAscendingInitially = false;
boolean isDescendingInitially = false;
String output = "";

// Detected descending
if ( arr > arr)
{
isDescendingInitially = true;
output = "Descending";
}

// Detected Ascending
else
{
isAscendingInitially = true;
output = "Ascending";
}

// Now go through the rest of the array.
for (int i = 2; i < arr.length; i++)
{
if (arr[i-1] < arr[i] && isDescendingInitially)
{
output = "Descending Rotated";
}
else if (arr[i-1] > arr[i] && isAscendingInitially)
{
desc++;
output = "Ascending Rotated";
}

}

return output;
}``````

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

Hi @omarfarooq93, your code may fail at this test case- {6,1,2,3} since you are only checking the first two elements of the array. Please see my implementation and let me know whether my understanding of the problem is correct!

``````public static String displayTypeOfArray(int[] input) {
int descCount = 0;
int ascCount = 0;
for(int i=0;i<input.length-1;i++) {
if(input[i] <= input[i+1]) {
ascCount++;
} else if(input[i] > input[i+1]) {
descCount++;
}
}

if(descCount == 0) {
return "Ascending";
} else if(ascCount == 0) {
return "Descending";
}
if(ascCount > descCount) {
return "Ascending Rotated";
} else if (ascCount < descCount){
return "Descending Rotated";
} else if(ascCount == descCount && ascCount > 0) {
if(input>input) {
return "Ascending Rotated";
} else if(input < input) {
return "Descending Rotated";
}
}
return null;
}``````

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

My Java approach

``````public class Main {

public static void main(String[] args) {
//        int[] arr = {2, 1, 5, 4, 3}; // rotated decreasing
//        int[] arr = {9, 8, 7, 6, 5, 4, 3}; // decreasing
//        int[] arr = {4, 5, 6, 1, 2, 3}; // rotated increasing
int[] arr = {1, 2, 3, 4, 5}; // increasing
determineArrayType(arr);
}

public static void determineArrayType(int [] arr) {
int rotatedIncreasingResult = isRotatedIncreasing(arr, 0, arr.length - 1);
int rotatedDecreasingResult = isRotatedDecreasing(arr, 0, arr.length - 1);
if(rotatedDecreasingResult < 0 && rotatedIncreasingResult > 0) {
System.out.println("Is decreasing");
} else if(rotatedDecreasingResult > 0 && rotatedIncreasingResult < 0) {
System.out.println("Is increasing");
} else if(arr > arr[arr.length - 1]) {
System.out.println("Is rotated increasing");
} else {
System.out.println("Is rotated decreasing");
}
}

public static int isRotatedIncreasing(int[] arr, int left, int right) {
if (left >= right) {
return -1;
}
int mid = (left + right) / 2;
if (arr[mid + 1] < arr[mid]) {
return mid;
} else if (arr[left] < arr[mid]) {
return isRotatedIncreasing(arr, mid + 1, right);
} else {
return isRotatedIncreasing(arr, left, mid);
}
}

public static int isRotatedDecreasing(int[] arr, int left, int right) {
if (left >= right) {
return -1;
}
int mid = (left + right) / 2;
if (arr[mid + 1] > arr[mid]) {
return mid;
} else if (arr[left] > arr[mid]) {
return isRotatedDecreasing(arr, mid + 1, right);
} else {
return isRotatedDecreasing(arr, left, mid);
}
}
}``````

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

{ static void whatTypeOfArray(int[] arr) {

if(arr.length<=1) {
System.out.println("Ascending");
return;
}
int len = arr.length;
int start = 0;
int end = len-1;
while(start<len-1 && arr[start]==arr[start+1])
start++;
if(start==len-1) {
System.out.println("All same numbers");
return;
}
while(end>0 && arr[end]==arr[end-1])
end--;

if(arr[start]>arr[end]) {
if(start+1==end || (arr[start]>arr[start+1] && arr[end-1]>arr[end])) {
System.out.println("Decending");
} else
System.out.println("Ascending Sorted");
} else {
if(start+1==end || (arr[start]<arr[start+1] && arr[end-1]<arr[end])) {
System.out.println("Ascending");
} else
System.out.println("Decending Sorted");
}
}
}

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.