## Amazon Interview Question for Software Developers

Country: United States
Interview Type: Written Test

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

I think this can be solved in O(N)

``````class SolutionForExchangeTwoElementsForSortedArray {

public boolean solution(int[] arr) {
if(arr.length <= 1) {
System.out.println("Not enough element to swap");
return true;
}
boolean flag = true;
int first = -1;
int second = -1;

for (int i = 1; i < arr.length; i++) {
if (flag) {
if (arr[i - 1] > arr[i]) {
first = i - 1;
flag = false;
}
} else {
if (arr[first] <= arr[i]) {
second = i - 1;
}
}

if (second != -1) {
break;
}
}
if(second == -1) {
second = arr.length -1;
}
if (first == -1) {
return false;
}
int temp = arr[first];
arr[first] = arr[second];
arr[second] = temp;

for (int i = 1; i < arr.length - 1; i++) {
if (arr[i - 1] > arr[i]) {
return false;
}
}
return true;
}
}

public class ExchangeTwoElementsForSortedArray {

public static void main(String[] args) {
SolutionForExchangeTwoElementsForSortedArray mSol = new SolutionForExchangeTwoElementsForSortedArray();
System.out.println(mSol.solution(new int[] {4,2,2,2,5}));
System.out.println(mSol.solution(new int[] {4,2,2,2,3}));
System.out.println(mSol.solution(new int[] {3,2,2,2,3,3,4,4,4}));
System.out.println(mSol.solution(new int[] {3,2}));
System.out.println(mSol.solution(new int[] {3,2,2}));
System.out.println(mSol.solution(new int[] {3,2,4}));
System.out.println(mSol.solution(new int[] {8,2,2,4}));
System.out.println(mSol.solution(new int[] {8}));
}
}``````

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

Yes O(n) time with O(1) space.

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

in this input (1,2,3,4,5,6,7,8,0) your code work O(N) time complexity?

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

Note that your array is false as you can't make it sorted in one swap. You can just make it sorted in one rotation.

I can think of a 2N so O(n) solution. Scan once to find the first element where a[i] > a[i+1]. Then find the next element out of order such that a[j-1] > a[j]. Swap j and i Scan one more time to see if it's sorted.

``````1 2 3 7 5 6 4 8 9
Scan 1: a[i] = 7 a[j] = 4
Swap 4 and 7
Scan 3: It's in order
8 1 2 3 4 5 6 7 0
Scan 1:a[i] = 8 a[j] = 0
swap
scan 2: in order
1 2 3 5 4 7 6 8 9
Scan 1: a[i] = 5, a[j] = 4
Swap
Scan 2: out of order.
1 2 3 5 4 6 7 8 9
Scan 1: a[i] = 5 a[j] = 4
Swap
Scan 2 in order.
0, -10, 10, 20, 30, 40, 50
Scan 1: a[i] 0 and a[j] = -10
swap a[i] and a[i+1]
scan2 in order
0, 2, 4, 6, 8, 10, 9
Scan1: a[i] = 10, a[j] = 9
swap a[i] and a[j]
scan 2: sorted.``````

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

Note with the array you posted, no swaps will be done as there is no i s.t a[i] > a[i+1] as 0 is the last element. and it will correctly find that it cannot be sorted in one swap with the second scan.

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

1) Copy the original array
2) Sort the copy
3) loop through the arrays and check how many corresponding elements don't match

O(NlogN) - space 2N

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

Make a duplicate array , sort duplicate array and compare with original array element by elements , if there are only two mismatch , then it is possible otherwise not.

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

The nlogn is a rather generous runtime allowance here, as it meanns we can run a heapsort or similar.

The idea here is to create a sorted version of the array, and compare to see if there are exactly m differences (in this case, m=2)

in python:

``````def only_m_switches(val_array, m):
tmp_array = sorted(val_array)
for i in range(0, len(val_array)):
if tmp_array[i] != val_array[i]:
m -= 1
return m == 0``````

this fulfills the required space and time usage as well.

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

You can use quick sort to sort the array but during sorting if you need to do more than one swap just return false. Use pivot = N /2
This way you don't need additional space and most of the time don't need to sort entire array.

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

Assumptions:
*The method should return true/false, as the question is "is it possible to...".
*We can't affect the array insitu, since we are only characterizing it (it doesn't say "sort the array" or even "return a sorted array").
* Assuming sorting is lowest index => lowest value (numerical order starting at idx 0)

Discussion:
If swapping 2 elements results in a sorted array, it means all of the elements are in their proper place except for the 2 we need to swap.

Thus, if we just walk the array we will run into these "anomalies", which are the out-of-place elements. Naively I claim that we want two and exactly two anomalies, otherwise we can't do this.

But there is an edge-case (literally) when the out-of-place element is on either end and it belongs on the other side of the adjacent element, in which case we would only see one anomaly (either right at the beginning or at the end) and it can be swapped with the neighboring element. If either the start or end element belongs somewhere in the middle, we must have another out-of-place element with which to swap, but if there isn't an internal anomaly, then all of the elements are in the correct place and must be preserved. Allowing repeats makes the previous statement false so that would require clarification of the question.

An easy approach, then, is do a single walk of the array and notate anomalous indices. After the fact, we can return false if we got more than 2, or do some more processing to validate that the one or two out-of-place elements can be "fixed". In this example we do an array copy as a workspace for the swap, so we use an extra N space.

JAVA

``````public boolean canTwoSwapsSortArray(int[] arr)
{
int numAnomaliesFound = 0;
int[] anomalousIndices = new int[2];

// note the terminating condition
for ( int idx = 0; idx < arr.length - 2; idx++ )
{
if ( arr[idx] > arr[idx+1] )
{
numAnomaliesFound++;
// we can cut it short here if we get more that 2
if ( numAnomaliesFound > 2 )
return false;
else
anomalousIndices[numAnomaliesFound-1] = idx;
}
}

switch (numAnomaliesFound)
{
default:
return false;
case 1:
// check for edge-cases
if ( 0 == anomalousIndices[0] )
{
// We know the first one is greater than the 2nd
// We need to make sure it fits between the next 2
if (arr[0] <= arr[2] )
return true;
}
// Notice the -2 here, because we didnâ€™t actually
// flag the last index as anomalous, we detected it
// at the one before
else if ( (arr.length-2) == anomalousIndices[0] )
{
// We know the last one is less-than the second-to-last
// We need to make sure it fits between the previous 2
if ( arr[(arr.length-1)] >= arr[arr.length-3] )
return true;
}
else
{
return false;
}
case 2:
// swap the elements and check
int[] newArr = new int[arr.length];
newArr.copy(arr);
swap (newArr, anomalousIndices[0], anomalousIndices[1]);
// 2nd time through N elements:
for (int idx=0;idx<newArr.length - 2;idx++)
{
if ( newArr[idx] > newArr[idx+1] )
return false;
}
// it worked!
return true;
}
}``````

We need the 2N space for the copy when we are checking that the swap works. However we can optimize this by just checking that the newly swapped elements would fit between their new neighbors, without actually swapping.

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

``````class CheckSortedByOneSwap{

public static void main(String... a){

CheckSortedByOneSwap obj = new CheckSortedByOneSwap();

System.out.println("True :: " + obj.solution(new int[] {4,2,2,2,5}));
System.out.println("False :: " + obj.solution(new int[] {4,2,2,2,3}));
System.out.println("True :: " + obj.solution(new int[] {3,2,2,2,3,3,4,4,4}));
System.out.println("True :: " + obj.solution(new int[] {3,2}));
System.out.println("True :: " + obj.solution(new int[] {3,2,2}));
System.out.println("True :: " + obj.solution(new int[] {3,2,4}));
System.out.println("False :: " + obj.solution(new int[] {8,2,2,4}));
System.out.println("True :: " + obj.solution(new int[] {8}));

}

boolean solution(int[] arr){

int len = arr.length;
int indexForMisplaced = -1;
int secondIndexForMisplaced = len-1;

for(int i=1;i<len;i++){
if(indexForMisplaced < 0){
if(arr[i-1] > arr[i]){
indexForMisplaced = i-1;
}
}
else{
if(arr[indexForMisplaced] <= arr[i]){
secondIndexForMisplaced = i-1;
break;
}
}
}

if(indexForMisplaced != -1){
int temp = arr[indexForMisplaced];
arr[indexForMisplaced]=arr[secondIndexForMisplaced];
arr[secondIndexForMisplaced]=temp;
}
for(int i=1;i<len;i++){
if(arr[i-1]>arr[i]){
return false;
}
}

return true;

}

}``````

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

``````public boolean needMoreThanOneSwap(int[] a){
boolean swappedOnce = false;
int k = -1;
for (int i = 0; i < a.length; i++) {
if(i < a.length -1){
//its not last element yet..
if(a[i] > a[i+1]){
if(k == -1){
//record this index.. because we need to swap it later
// if we hit this condition again.
k = i;
continue;
}
//need swap
if(!swappedOnce){
//swap
int temp = a[k];
a[k] = a[i+1];
a[i+1] = temp;
swappedOnce = true;
k = -1;
}else{
//since we have already swapped once we don't want to swap again.. as
// this means the array cannot be sorted by one swap
return true;
}
}
}
}

if(k != -1){
//reaching here means we found array not sorted only at one index..and we couldn't swap it with.
return true;
}

return false;
}``````

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

``````public boolean needMoreThanOneSwap(int[] a){
boolean swappedOnce = false;
int k = -1;
for (int i = 0; i < a.length; i++) {
if(i < a.length -1){
//its not last element yet..
if(a[i] > a[i+1]){
if(k == -1){
//record this index.. because we need to swap it later
// if we hit this condition again.
k = i;
continue;
}
//need swap
if(!swappedOnce){
//swap
int temp = a[k];
a[k] = a[i+1];
a[i+1] = temp;
swappedOnce = true;
k = -1;
}else{
//since we have already swapped once we don't want to swap again.. as
// this means the array cannot be sorted by one swap
return true;
}
}
}
}

if(k != -1){
//reaching here means we found array not sorted only at one index..and we couldn't swap it with.
return true;
}

return false;
}``````

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.