## Amazon Interview Question for Software Engineer / Developers

• 0

Country: India
Interview Type: Written Test

Comment hidden because of low score. Click to expand.
4
of 8 vote

Input: sequence a

``````i = 1
for j = 1 to n
if a[j] == i
i++
return length(a)-i;``````

The idea behind is that when we scan a from left, all number without consecutive order should be delete and push on back. Hope it works

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

Sorry, it doesn't work....only valid for sequence whose element range from 1 to n

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

it should work after a small modification and the complexity would be o(N*logN).

(1) Copy the input array to a 2nd array (b[]) and sort b[] so each kth element in b[] is the kth smallest number.

(2) Slightly modify your code to

``````i = 0
for j = 1 to n
if a[j] == b[i]
i++
return length(a)-i-1;``````

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

Agree. An alternative one is find length of the longest non descending subsequence begin with the min element. And total length minus that length would also get the result. Complexity O(nlgn). But ur method is more intuitive.

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

Agree. An alternative one is find length of the longest non descending subsequence begin with the min element. And total length minus that length would also get the result. Complexity O(nlgn). But ur method is more intuitive.

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

I think the modified version by buffalo is the answer. And it seems that warrior's LIS way doesn't work in some situations, e.g., 234561789

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

The answer provided warrior seems to be not working for inpput as: 5, 3,4 .Sorted array is : 3 4 5 and functions returns 2 as answer which is wrong,

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

Sory not warrior , it's buffalo

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

There shouldn't a '-1' in return, it should be "return length(a)-i".

``````i = 0
for j = 1 to n
if a[j] == b[i]
i++
return length(a)-i;``````

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

@warrior the question is itself sorting of array .Here and if you sort and put it in a second array i think that is extra work that we are doing.I think we have to sort using the swap method defined.

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

The question is to find how many steps of this specifically "swap" operation needed to sort an array, not print the sorted array.

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

@buffalo, for a array like 4321, we get 3 from you code but after 3 seap we get 1432, not 1234. Is that correct?

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

@Buffalo I don't think your algorithm works. I tried it on 8796, your algo gives me 3 swaps needed but the given "swap" operation clearly takes more than 3 swaps.

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

"Swap" in this question means putting an element at the back of the array. It doesn't mean swap in the normal sense of swapping 2 elements. So for 8796 you simply need 3 swaps to put 7, 8 and 9 at the back of the array.

On the other hand, I don't know if buffalo's algorithm is right or not. If nothing else, the "j = 1 to n" certainly bothers me when i starts from 0...

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

try 4321, fails miserably

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

Correction to the buffalo's last comment(j should start from 0).
Overall explanation : Lets have a as given, b as sorted a.
Now for the sake of explanation lets say a has elements 1 to n and a is like:
<garb>,1,2,3,<garb>4,5,<garb>,6<garb>,7,8<garb>

for example 15,13,1,2,3,12,14,4,5,11,6,9,7,8,10

Basically I am trying to identify from min onwards how much of answer can be got by removing <garbs>.
Now removing of the garbage will be in the order : 9 to 15.
so swap(9),swap(10)...swap(15) will give us sorted array
So code :

``````i=0;
for(j=0;j<n,j++)
{
if(a[j]==b[i])
i++;
}
return len(a)-i;``````

So after removing garb, a to a[i-1] will be already sorted = total i elements sorted. So return len(a)-i

If j started with 1 will fail for 1,13,15,2,3,12,14,4,5,11,6,9,7,8,10 which has same property.

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

This can be done in O(n), or O(2*n) to be exact. Also don't need to do the swap operation.

Use a 2nd array, swapped[n] (initialized to 0), to record which number needs to be swapped. Also use a variable, min_swapped, to record the current min swapped number (initialized to n+1). Then use another variable, next_min, for the next min value (initialized to 1) which isn't marked as swapped.

The basic idea is

(1) If the current number is larger than the next_min, it needs to be swapped.
(2) If a number is larger than the current min_swapped, it also needs to be swapped.

For (1), use 234561789 as example, all the numbers (ie. 2, 3, 4, 5, 6) before 1 need to be swapped so 1 can be the first element in the array.

For (2), use the same example, 234561789. Before we parse 7, the min_swapped is 2. Thus, 7, 8, and 9 also need to be swapped because, after 2 is moved to the end of the array, 7, 8, and 9 need to be swapped so 2 can be right after 1.

a pseudo code is like following:

``````swap_count=0;
for (x=0; x<n; x++) {
if (input[x]>next_min || input[x]>min_swapped) {
swap_count++;
swapped[input[x]-1]=1;
if (input[x]<min_swapped) min_swapped=input[x];
}
else if (input[x]==next_min) {
for (y=next_min+1; y<=n; y++)
if (swapped[y-1]==0) break;
if (y==n+1) break;
else if (y > min_swapped) {
swap_count+=n-x-1;
break;
}
else next_min=y;
}
}

printf("swap count: %d\n", swap_count);``````

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

@Buffalo:
In your first example you mentioned that the numbers are to be shifted before 1. Doesn't the question talk about appending the numbers to the end of the array once the decision to swap is made?
Also, I think there are two cases, either to start traversing array from left or from right. This might produce different results.
For example, consider input [5,2,4,3].
From L to R, it takes 3 swaps, whereas in R to L it takes only 2 swaps to sort the array.

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

(1) Yes, append the the end. For the same example, 234561789, number of swaps (remove and append to the end) is 8. The order is to swap 2, 3, 4, 5, 6, 7, 8 9.

234561789 => 345617892 => 456178923 => 561789234 => 617892345 => 178923456 => 189234567 => 192345678 => 123456789

The question doesn't ask the swap order, only asks number of swaps. But to find the order is relatively quick, it's the ascending order of numbers needed to be swapped.

(2) 5, 2, 4, 3 would take 2 swaps, first swap 4, then 5.

BTW, my above code assumes the elements is 1 to N, if it's not, it just needs a small modification to sort the input array and makes the complexity o(N*logN).

However, I think the best solution is warrior's, the following is my reply to his:

========================================
it should work for elements not from 1 to N after a small modification and the complexity would be o(N*logN).

(1) Copy the input array to a 2nd array (b[]) and sort b[] so each kth element in b[] is the kth smallest number.

(2) Slightly modify your code to

``````i = 0
for j = 1 to n
if a[j] == b[i]
i++
return length(a)-i-1;``````

===============================================

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

@Buffalo
When you say - "Also use a variable, min_swapped, to record the current min swapped number (initialized to n+1). Then use another variable, next_min, for the next min value (initialized to 1) which isn't marked as swapped." Do you mean min_swapped is initialized to input[n-1] in an array input of size n and next_min initialized to input?

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

A question for interpretation of "How to do it less than O(n^2)"
What do you mean by "it"
you mean the algo for sorting the array?
or you mean the algo to calculate minimum steps to sort the array using swap?

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

It's actually the same o() for both if you do it right.

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

How about applying quicksort algorithm on that array. While portioning the array wrt to pivot element we need swaps to find the index of pivot position. We can use above swap function to easily append all the elements > pivot to the back of the array fixing index position for pivot element. In this way we can keep swaps are always going to be O(nlogn).

When

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

Scan the array from the first element to last, compare consecutive elements. If first is greater then second, then swap first (put it at end of list); else continue. Do so until you don't find any unordered pairs. Something like this:

``````int[] input = new int[] (3, 1, 2, 4);
int a = input; int b = input; int i = 0;
while(b != null) {
if (a > b) {
input.swap(a);
} else {
i = i + 1;
a = input[i];
b = input[i+1];
}
}``````

Worst case would be when list is sorted in descending order, meaning we would have to do a swap at each time, so n times.

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

how can we implement swap() in constant time if we use array? I think to implement swap() using linklist would be a better option as we only need to delete the node and append it to the tail of the list.

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

Then how about the cost of swap operation. If it's O(n), your algo takes O(n2) in worst case. In your program, After swapping a, a would be at last position. But the next iterations compares the same a value. it may lead to infinite loop.

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

For the input {1,4,3,2}, your method will need 3 swaps, while the minimum swaps needed is 2.

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

This will require repeated checkings, cannot be done in o(n).

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

I support artemis comment. Repeated checks are required and it can't be done in o(n). I think your code executes for o(n^2) times in worst case eg: array given in in reverse order

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

Hi Shilcare, Could you please explain how the sequence {1,4,3,2} takes minimum 2 swaps.

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

minimum swaps 1432->1423->1234,
his method 1432->1324->1243->1234.

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

Assumption: swap is not equal to copying and/or overwriting the value.

arr= 3124

sort(arr)
{
for(int i=0;i<arr.length-1;i++)
{
if(arr[i]>arr[i+1])
{

rotate(arr,i);
}
}
}

rotate function will rotate the part of the array that is given to rotate them.

It will always rotate the array from the given point to the end of the array.

eg.
3124 -> rotate function will rotate whole array to the left by one. So 3 will be appended to end.

1243 -> if(4>3) than rotate function will rotate that array of 2 to left. So 4 will be appended to the end.

Hope this helps.

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

I don't think this will work.
let's take an example 32145
according to you algo the transformation will be something like this.
3>2 ->>>> 21453 (i=0)
1<4 (i=1)
4<5 (i=2)
5<3 ->>>> 21435 (i=3)

It's still not sorted. Am i missing something here???

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

Thanks mukund for finding bug...
I modified my program & pasting the code.
Check it & tell me if any problem is still there.

``````public class SwapArray {

static void rotate(int arr[],int i){
int temp=arr[i];
int j;
for(j=i;j<arr.length-1;j++){
arr[j]=arr[j+1];
}
arr[j]=temp;
}
static void sort(int arr[]){

for(int i=0;i<arr.length-1;i++){
if(arr[i]>arr[i+1]){
rotate(arr,i);
i--;
if(i>=0){
i--;
}
}
}
}
public static void main(String[] args) {
int arr[]=new int;
arr=9;
arr=9;
arr=5;
arr=43;
arr=6;

sort(arr);
for(int i=0;i<arr.length;i++)
System.out.print("  "+arr[i]);
}
}``````

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

Nice explanation by all of you as Algo is easy to understand then code.....

bt all logic are quite same.... O(n^2)
no one gave sol in complexity < O(n^2) as asked in qus

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

mine is O(n). Both arrays are parsed once each totally.

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

I think it's the same as finding the most non descending subsequence

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

Concept is below:
10, 17, 6, 5
10 compare 17 ok
17 compare 6 not-ok array{10, 6, 5, 17}
10 compare 6 not-ok array{6, 5, 17, 10}
6 compare 5 not-ok array{5, 17, 10, 6}
5 compare 17 ok
17 compare 10 not-ok array{5, 10, 6, 17}
10 compare 6 not-ok array{5, 6, 17, 10}
6 compare 17 ok
17 compare 10 not-ok array{5, 6, 10, 17}
so output 5, 6, 10, 17 and number of times swap is called 6.

include <stdio.h>
#define SIZE(x) sizeof(x)/sizeof(x)

void swap(int a[], int i, int j)
{
int temp = j - i;
int store = a[i];
j = i + 1;
/* first shift */
while(temp){
a[i] = a[j];
i++;
j++;
temp--;
}
a[i] = store;
printf("called\n");
}

int main()
{
int a[] = {10, 5, 7, 6, 4};
int i = 0;
int j = 1;

while(i != (SIZE(a) - 1)) {
if(a[i] < a[j]) {
i++;
j++;
} else {
swap(a, i, (SIZE(a) - 1));
if(i) {
i--;
j--;
}
}
}
return 0;
}

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

What is the runtime of this? Looks like O(n^2)?

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

We can perform this in 3 swaps actually
10,17,6,5
10,17,5,6
17,5,6,10
5, 6,10,17

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

anon's solution provides a pattern of number of steps required to solve the problem.
One of the worst case scenario's: all numbers are in descending order

For n = 1: 0 steps
For n = 2: 1 steps
For n = 3: 3 steps
For n = 4: 6 steps
For n = 5: 10 steps
For n = 6: 15 steps

i.e. 1 + 2 + 3 + 4 + 5 ... (n-1) = O(n^2)

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

54321
54312
54123
51234
12345

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

The actual number of swaps is determined by the first element in sequence that is out of the order in the unsorted list.

``````def f(arr):
# O(n log n) time to sort the list
n = len(arr)
tuples = [(x, i) for i, x in enumerate(arr)]
sorted_tuples = sorted(tuples)

# linear time to count the swaps
positions =  * n
for i, tuple in enumerate(sorted_tuples):
val, pos = tuple
positions[i] = pos

def count_swaps():
for i in range(n - 1):
if positions[i+1] < positions[i]:
return n - (i + 1)
return 0
num_swaps = count_swaps()
print
print 'arr', arr
print num_swaps, 'swaps'

# actually performing the swaps is N-squared
if num_swaps:
print 'start:', arr
which_elem = n - num_swaps
for i in range(which_elem, n):
pos = positions[i]
if pos < n - 1:
val = arr.pop(pos)
arr.append(val)
print 'swap: ', arr
for j in range(n):
if positions[j] > pos:
positions[j] -= 1

arr = [2, 3, 5, 7, 11, 13]
f(arr)

arr = list(reversed(arr))
f(arr)

import random
for i in range(3):
random.shuffle(arr)
f(arr)``````

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

One expensive way to do a BFS taking the given array as root and having all the arrangements obtained by swapping each element as child. BFS would give the shortest path from the root to destination node (sorted array) .

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

``````def swap(a: Array[Int]): Array[Int] = {
val len = a.length-1
var i = 0
var arr = a
while(i < len){
if(arr(i) > arr(i+1)){
val tmp = arr(i)
val bef = arr.take(i)
val aft = arr.drop(i+1)
arr = bef ++ aft :+ tmp
i = if(i > 0) i-1 else i
}else { i = i+1 }
}
arr
}

scala> val v = swap(Array(8,3,5,6,1,6,9,0,-1, 78,45))
v: Array[Int] = Array(-1, 0, 1, 3, 5, 6, 6, 8, 9, 45, 78)``````

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

Selection sort does it in n-1 swaps

Find max, append it to the end. Repeat n-1 times (but exclude the previously appended items from your scan for max)

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

min*

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

public class SortingBySwapping {

static void swap(int [] arr1, int n){
int temp = arr1[n];
int i=0;
for(i=n ; i<arr1.length-1;i++){
arr1[i]=arr1[i+1];
}
arr1[i]= temp;
}

public static void main(String[] args) {
int[] arr1 = {3,1,2,4};
int count =0;
for(int j =0;j<arr1.length-1;j++){
if(arr1[j] > arr1[j+1]){
swap(arr1,j);
count++;
}
}
System.out.println("No of Swap "+ count);
for(int i: arr1){
System.out.print(i+" ");

}
}

}

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

O(N) complexity :

``````static int findMin(int[] a)
{
int mid, start = 0;
int end = a.length -1;

while(start < end){
mid = start + (end - start)/2;
if(a[mid] > a[end])
start = mid + 1;
else
end = mid;
}
return start;
}``````

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

Doesn't work. "Swap" here is not the usual swap, read the question.

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

O(N) complexity

``````static int findMin(int[] a)
{
int mid, start = 0;
int end = a.length -1;

while(start < end){
mid = start + (end - start)/2;
if(a[mid] > a[end])
start = mid + 1;
else
end = mid;
}
return start;
}``````

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

1. Maintain a min heap of size of N.
2. open a loop, and input traverse the array.
3. For every traversed element, insert the same in MinHeap(along with index).
4. Take the top of heap(minimum number so far) and swap it.
5. At the end of the loop, we will have sorted array with minimum swaps.
Space Complexity---0(n) ---- for Heap.
Time Complexity---- 0(nlogn).

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

Read the question more carefully. You need to determine the maximum number of swaps.

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

Question clearly says... "Find the minimum number of "swaps" needed to sort that array."

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

The question is to find the minimum swaps' but your method doesn't take minimum swaps.

For example, if the input is already sorted, like 12345 you method still swap 5 times. Or if the input is 12354, you still swap 5 times.

Basically, no matter what the input is, you always swap len(input) times.

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

merge sort or quick sort doesn't work for this problem. The swap here is different to the swap in normal sorts.

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

But all that is asked is the min. number of swaps required to sort, and in-place quick sort does the trick, I am not why that won't be optimal...
It sure is than bubble sort and solves in nlogn without extra space

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.