Amazon Interview Question
SDE-2sCountry: United States
Interview Type: In-Person
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[0] > arr[1])
{
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;
}
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[0]>input[1]) {
return "Ascending Rotated";
} else if(input[0] < input[1]) {
return "Descending Rotated";
}
}
return null;
}
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[0] > 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);
}
}
}
{ 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");
}
}
}
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.
- andrewbanksmail March 08, 2017