Amazon Interview Question for Software Engineer / Developers


Country: India
Interview Type: Written Test




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

How about following?
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

- warrior October 27, 2012 | Flag Reply
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

- warrior October 27, 2012 | Flag
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;

- buffalo October 27, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- warrior October 28, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- warrior October 28, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- shilcare October 28, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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,
Correct ans : 1. Please advise

- Anonymous October 28, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Sory not warrior , it's buffalo

- Anonymous October 28, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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;

- buffalo October 28, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@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.

- Anonymous October 28, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous October 28, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous November 14, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@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.

- Anon1 November 22, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

"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...

- Sunny December 13, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

try 4321, fails miserably

- Riyad Parvez December 28, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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[0] 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.

- Hill Billy February 28, 2013 | Flag
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);

- buffalo October 27, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

@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.
Comments?

- Learner October 27, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

(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;

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

- buffalo October 27, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@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[0]?

- anon1 November 22, 2012 | Flag
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?

- Vincent October 28, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous October 28, 2012 | Flag
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

- srikanth October 27, 2012 | Flag Reply
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[0]; int b = input[1]; 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.

- Terence October 27, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- bidisha October 27, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Eswar October 27, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- shilcare October 27, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- artemis October 27, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- ajit October 27, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Eswar October 28, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- shilcare October 28, 2012 | Flag
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[4]= 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.

- New_Coder_007 October 27, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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???

- Mukund October 27, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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[5];
		arr[0]=9;
		arr[1]=9;
		arr[2]=5;
		arr[3]=43;
		arr[4]=6;
		
		sort(arr);
		for(int i=0;i<arr.length;i++)
			System.out.print("  "+arr[i]);
	}
}

- New_Coder_007 October 28, 2012 | Flag
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

- PKT October 27, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- buffalo October 27, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- warrior October 27, 2012 | Flag
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[0])

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;
}

- aka October 27, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- JustCoding October 27, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous September 28, 2013 | Flag
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)

- karu October 27, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

54321
54312
54123
51234
12345

- showell30@yahoo.com October 28, 2012 | Flag
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 = [0] * 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)

- showell30@yahoo.com October 28, 2012 | Flag Reply
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) .

- Anonymous November 25, 2012 | Flag Reply
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)

- rbsomeg February 19, 2013 | Flag Reply
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)

- S O U N D W A V E March 26, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

min*

- S O U N D W A V E March 26, 2014 | Flag
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+" ");

}
}

}

- Ritesh Gupta May 06, 2014 | Flag Reply
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;
	}

- Anonym October 30, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- anon1 November 22, 2012 | Flag
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;
	}

- Anonymous October 30, 2012 | Flag Reply
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).

- Krishna October 28, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- showell30@yahoo.com October 28, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Krishna October 29, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Anonymous October 29, 2012 | Flag
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous October 28, 2012 | Flag
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

- Logan September 24, 2013 | Flag


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