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[2] <= input[0]){
				ascCount++;
			}
			else{
				descCount++;
			}
			
		}	
		
		if(ascCount > descCount) {
			return "Ascending Rotated";
		} else if (ascCount < descCount){
			return "Descending Rotated";
		}
		return null;
	}

- andrewbanksmail March 08, 2017 | Flag Reply
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[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;
	}

- omarfarooq93 March 08, 2017 | Flag Reply
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[0]>input[1]) {
				return "Ascending Rotated";
			} else if(input[0] < input[1]) {
				return "Descending Rotated";
			}
		}		
		return null;
	}

- jim March 08, 2017 | Flag Reply
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[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);
        }
    }
}

- Anonymous March 08, 2017 | Flag Reply
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");
}
}
}

- hrshchaitanya May 01, 2017 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More