## Amazon Interview Question for Software Engineer / Developers

• 2

Team: 11
Country: India
Interview Type: In-Person

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

``````// O(1) for every case except
// O(logn) finding max in increase-decrease case
n = a.Length
if (n > 1) {
front = ""
tail  = ""

//compare first and second element
if (a[0] < a[1]) { front="increasing" }
if (a[0] > a[1]) { front="decreasing" }

//compare last and second last elements
if (a[n-1] < a[n-2]) { tail="decreasing" }
if (a[n-1] > a[n-2]) { tail="increasing" }

//where they the same
if (front == tail) {
print front
//max must be one of the ends
if (front == "increasing"){
print "max: " + a[n-1]
}
else {
print "max: " + a[0]
}
}
else {
print front +"-"+ tail
if (front=="decreasing" && tail=="increasing" ) {
//max must be one of the ends
if ( a[0] > a[n-1]) {
print "max: " + a[0]
}
else {
print "max: " + a[n-1]
}
}
else {
//max is somewhere in the middle at the inflextion point
max = a[1]
max = binaryMaxSearch(a, max, 1, (n-3)/2+1, n-2)
print "max: " + max
}
}
}

int binaryMaxSearch([] a, start, mid, end) {
//check for inflextion point
if (a[mid-1] < a[mid] && a[mid] > a[mid + 1]) {
return a[mid]
}

if (a[mid] < a[mid + 1]) { //go right
return binaryMaxSearch(a, mid, (end-mid)/2+mid, end)
}
else { // go left
return binaryMaxSearch(a, start, (mid-start)/2+start, mid)
}
}``````

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

what if 2 elements have same value?

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

what if n-1 elements are the same (list will still be increasing or decreasing)? you need to adjust your algorithm for that, and the worst case running time then would be O(n)

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

main()
{
int a[6] = {3,2,1,5,6,8};
int temp,c;
temp = a[0];
if(temp< a[1])
{
c = 1;
}
else
{
c= 2;
}
if(a[1] <a[2])
{
if(c== 1)
{
c=1;
}
else if(c == 2)
{
c = 4;
}
}
else if(a[1] >a[2])
{
if(c == 1)
{
c = 3;
}
}

switch(c)
{
case 1:
printf("increasing\n");
break;
case 2:
printf("decreasing\n");
break;
case 3:
printf("increase- decrease\n");
break;
case 4:
printf("decrease- increase\n");
break;
}
}

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

``````public static String checkArrayType(int[] array)
{
if(array.length <= 1)
return "Can't evaluate";
else
{
if(array[0] < array[array.length-1])
{
if(array[0] < array[1])
{
if(array[1] < array[2])
return "Increasing";
else
return "Decrease-Increase";
}
else
return "Increase-Decrease";
}
else
{
if(array[0] > array[1])
{
if(array[1] > array[2])
return "Decreasing";
else
return "Increase-Decrease";
}
else
return "Decrease-Increase";
}
}
}

public static int max(String arrayType, int[] array)
{
if(arrayType.equals("Increasing"))
return array[array.length-1];
else if(arrayType.equals("Decreasing"))
return array[0];
else if(arrayType.equals("Increase-Decrease"))
{
int maxNumber = -1;
for(int i=0;i<array.length-1;i+=2)
{
if(i==0)
maxNumber = array[i];
else if(maxNumber<array[i])
maxNumber = array[i];
}
return maxNumber;
}
else
{
int maxNumber = -1;
for(int i=1;i<array.length;i+=2)
{
if(i==1)
maxNumber = array[i];
else if(maxNumber<array[i])
maxNumber = array[i];
}
return maxNumber;
}

}``````

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

you can't use -1 for the default max, what if your array only goes from -10 to -5?

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

Your binaryMaxSearch method is designed for a sorted (monotonic) array and it has no base case. We want a variation that will check for the inflection point (still O(logn)) by checking whether the neighbors are greater or lower. Something like:

``````int binaryMaxSearch(int[] a, int start, int mid, int end) {
if (a[mid-1] < a[mid] && a[mid] > a[mid + 1]) { // it's the inflection point
return a[mid];
else if (a[mid-1] < a[mid] && a[mid] < a[mid + 1]) { // mid is in the increasing segment of array, so go further to the right
return binaryMaxSearch(a, mid, (end-mid)/2+mid, end);
}
else { // mid is in the decreasing segment of array, so go to the left
return binaryMaxSearch(a, start, (mid-start)/2, mid;
}
}``````

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

yup, i forgot the base case entirely too, kind of an important part, but you also don't need to check both directions for the second if / elseif.... and you need to add start to your new mid in the else

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

``````//Wow So many solutions already. Let me add my two cents. The java version
//I think 0(1) for finding the sorting type unless I missed something in the question
//Finding max element is 0(LOGN) only for INCR/DECR case. Everything else is O(1)
//Code in its entirety
public enum SortType {
INCREASING, DECREASING, INCREASEANDDECREASE, DECREASEANDINCREASE
}
private static SortType findArraySortType(int[] intArray) {
if (intArray.length == 1)
return SortType.INCREASING;// arbitary
boolean firstIncrease = false;
boolean secondIncrease = false;
// check the first two elements
if (intArray[1] > intArray[0])
firstIncrease = true;
else
firstIncrease = false;
int arrayLength = intArray.length;
if (intArray[arrayLength - 1] > intArray[arrayLength - 2])
secondIncrease = true;
else
secondIncrease = false;

if (firstIncrease && secondIncrease)
return SortType.INCREASING;
if (firstIncrease && !secondIncrease)
return SortType.INCREASEANDDECREASE;
if (!firstIncrease && !secondIncrease)
return SortType.DECREASING;
if (!firstIncrease && secondIncrease)
return SortType.DECREASEANDINCREASE;
throw new RuntimeException("Should not happen this way.Cannot determine the sort type for this array!!");
// check the last two elements
}

private static int getMaxElement(SortType sortType, int[] intArray) {
if(sortType == SortType.DECREASING) return intArray[intArray.length-1];
if(sortType == SortType.INCREASING) return intArray[0];
//Compare the last and first for the decrease and increase and return the max one
if(sortType == SortType.DECREASEANDINCREASE)
return intArray[0] > intArray[intArray.length-1]?intArray[0]:intArray[intArray.length-1];

if(sortType == SortType.INCREASEANDDECREASE) {
//Get the transition element and return that one.Done!!
int lo = 0;
int hi = intArray.length-1;
while(true) {
int mid = lo + (hi-lo) /2;
if(intArray[mid] > intArray[lo]) {
if(intArray[mid+1] < intArray[mid]) return intArray[mid];
//still decreasing. change the lo
lo = mid+1;
continue;
}
if(intArray[mid] < intArray[lo]) {
hi = mid+1;
}

}
}
return -1;
}

public static void main(String[] args) {
// TODO Auto-generated method stub
int [] incArray = new int [] {1,2,3,4};
SortType sortType = findArraySortType(incArray);
int maxElement = getMaxElement(sortType, incArray);
System.out.format("%s %d \n",sortType,maxElement	);

int [] decArray = new int [] {-1,-2,-3,-4};
sortType = findArraySortType(decArray);
maxElement = getMaxElement(sortType, decArray);
System.out.format("%s %d \n",sortType,maxElement	);

int [] incrAndDecArray = new int [] {1,2,3,4,-1,-2,-3,-4};
sortType = findArraySortType(incrAndDecArray);
maxElement = getMaxElement(sortType, incrAndDecArray);
System.out.format("%s %d \n",sortType,maxElement	);

int [] decAndIncArray = new int [] {-1,-2,-3,-4,-1,1,2};
sortType = findArraySortType(decAndIncArray);
maxElement = getMaxElement(sortType, decAndIncArray);
System.out.format("%s %d \n",sortType,maxElement	);

}``````

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

To find 1)increasing 2)decreasing arrays

1) compare the first two elements

if the first element is less than the second element then the array is increasing array
max element is the last element
if the first element is greater than the second element then the array is decreasing array
max element is the first element
if the first element is equal to the second element (duplicates in the array)
then fetch the next element and repeat from step 1

To find 1)increasing -decreasing arrays 2) decreasing-increasing arrays

loop thrugth the array
compare the first element and second element
if first < second (increasing)
continue the loop till first > second(decreasing)
maxelement is the first element

else first > second (decreasing)
continue the loop till first < second(increasing)
maxelement is the second element

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

C++ implementation

``````#include <iostream>

// Special case to find max in case of Inc-Dec
int binarySearchMax (int *arr, int size) {
int start = 0;
int end = size - 1;
int idx = size/2;
for (; ;) {
if ((arr[idx-1] < arr[idx]
&& arr[idx] > arr [idx+1])
|| end - start <= 1) {
break;
}
if (arr[idx-1] < arr[idx]) {
start = idx;
idx = idx + ((end - idx)/2);
}
else {
end = idx;
idx = idx/2;
}
}
return arr[idx];
}

void find (int *arr, int size) {

if (size > 1) {
if (arr[0] < arr[1]) {
if (arr[size - 2] < arr[size - 1]) {
std::cout << "Type: Increasing\n";
std::cout << "Max: " << arr[size-1] << "\n";
}
else if (arr[size - 2] > arr[size - 1]) {
std::cout << "Type: Increasing - Decreasing\n";
std::cout << "Max: " << binarySearchMax(arr, size) << "\n";
}
else {
find (arr, size - 1);
}
}
else if (arr[0] > arr[1]) {
if (arr[size - 2] > arr[size - 1]) {
std::cout << "Type: Decreasing\n";
std::cout << "Max: " << arr[0] << "\n";
}
else if (arr[size - 2] < arr[size - 1]) {
std::cout << "Type: Decreasing - Increasing\n";
std::cout << "Max: " << ((arr[0] > arr[size-1]) ? arr[0] : arr[size-1]) << "\n";
}
else {
find (arr, size - 1);
}
}
else {
find (&arr[1], size - 1);
}
}
else {
std::cout << "Array of size 0/1 or with same elements\n";
}
}

int main () {
int arr1[] = {0, 1, 2, 3, 4, 5};
int arr2[] = {5, 4, 3, 2, 1, 0};
int arr3[] = {0, 1, 3, 5, 3, 1};
int arr4[] = {5, 4, 0, 1, 2, 3};
int arr5[] = {};
int arr6[] = {1};
int arr7[] = {0, 0};
int arr8[] = {1, 1, 1};
int arr9[] = {0, 1, 5, 5, 3, 1};

find (arr1, 6);
find (arr2, 6);
find (arr3, 6);
find (arr4, 6);
find (arr5, 0);
find (arr6, 1);
find (arr7, 2);
find (arr8, 3);
find (arr9, 6);

return 0;
}``````

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

``````public static void GetTypeAndMax(int[] arr){
int n = arr.length;
if (n < 2)
return;
String head = (arr[0] > arr[1]) ? "decreasing" : "increasing";
String tail = (arr[n-2] > arr[n-1]) ? "decreasing" : "increasing";
System.out.printf("Increasing. Max elem : %d\r\n", arr[n - 1]);
else
System.out.printf("Decreasing. Max elem : %d\r\n" , arr[0]);
}
else{
System.out.printf("Increasing-Decreasing. Max elem: %d\r\n" , BinSearch(arr , 0 , n-1));
}
else{
System.out.printf("Decreasing-Increasing. Max elem: %d\r\n", arr[0] > arr[n - 1] ? arr[0] : arr[n - 1]);
}
}
}

public static int BinSearch(int[] arr , int l , int r){
int m = l+ (r-l)/2;
if (arr[m-1] < arr[m] && arr[m] > arr[m+1])
return arr[m];

if (arr[l] < arr[l+1] && arr[m-1] < arr[m+1]){
return BinSearch(arr , m+1 , r);
}
else{
return BinSearch(arr, l , m);
}
}``````

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

Here's one without Binary Search, worse case O(n)

``````public class ToneDetection {

public void detect(int... data) {
System.out.print("Data : [");
for (int i = 0; i < data.length; i++) {
System.out.print(data[i] + " ");
}
System.out.print("] - ");

boolean maybeInc = false, maybeDec = false;

if (data[0] < data[1]) {
maybeInc = true;
} else {
maybeDec = true;
}

int prev = data[1];
if (maybeInc) {
for (int i = 2; i < data.length; i++) {
if (data[i] > prev) {
prev = data[i];
} else {
break;
}
}
} else if (maybeDec) {
for (int i = 2; i < data.length; i++) {
if (data[i] < prev) {
prev = data[i];
} else {
break;
}
}
}

if (maybeInc) {
if (data[data.length - 1] == prev) {
System.out.print("Type : Increasing, ");
System.out.println(" Min : " + data[0] + ", Max : " + data[data.length - 1]);
} else {
System.out.print("Type : Increasing-Decreasing, ");
System.out.println(" Min : " + Math.min(data[0], data[data.length - 1]) + ", Max : " + prev);
}
}
if (maybeDec) {
if (data[data.length - 1] == prev) {
System.out.print("Type : Decreasing, ");
System.out.println(" Min : " + data[data.length - 1] + ", Max : " + data[0]);
} else {
System.out.print("Type : Decreasing-Increasing, ");
System.out.println(" Min : " + prev + ", Max : " + Math.max(data[0], data[data.length - 1]));
}
}
}

public static void main(String[] args) {
ToneDetection detection = new ToneDetection();
detection.detect(7, 5, 3, 1, 2, 4, 6, 8);
detection.detect(7, 5, 3, 1, 2);
detection.detect(7, 5, 3, 1);
detection.detect(1, 3, 5, 7, 6);
detection.detect(3, 5, 7, 6, 4, 2);
detection.detect(1, 3, 5, 7);
}

}``````

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.