## Amazon Interview Question for Software Engineer / Developers

Country: India
Interview Type: Written Test

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

Its actually the sum of the number of 0's to the right for each 1. The pseudo code is as follows :-

``````swap = 0, count = 0
for (j = N; j >= 1; j--) {
if(arr[j] == 0)
count++
else
swaps += count
}
print(swaps)``````

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

how would this work for 111000 ?

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

see the total number of zeros right to each 1.here for
each 1 total number of zeros right to it are 3.hence total swaps will be 9.

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

For input "11000" we need only 2 swaps. But your program will print 3.
The optimal way looks to me to have two indexes: tracking zeroes from rhs (say i) and ones from lhs (j) and for as long as j<i keep swapping.

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

Here the swapping condition is that you can swap only between two adjacent elements. So in no way you can do it with 2 swaps. You need 6 swaps. 3 for each '1'.

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

int swapSort(string s) {
int count = 0;
while (1) {
bool flag=false;
for(int j=0; j<(s.length()-1);j++) {
if ((s.at(j)=='1') && (s.at(j+1)=='0')) {
s[j] = '0';
s[j+1] = '1';
count++;
flag = true;
}
}
if (!flag) {
break;
}
}
return count;
}

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

#include<iostream>
#include<string>
using namespace std;

int main()
{
string s;
cin >> s;
int i,j;
for (i=0; i<s.size();i++)
{
if(s[i] == '1')
break;
}
for (j = s.size();j>=0;j--)
{
if(s[j] == '0')
break;
}
cout << endl << j-i << endl;
cin.get();
cin.get();
return 0;
}

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

int swapSort(String s){
int numZeros = 0;
int count = 0;

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

sorry got submitted by mistake.. here is the code

int swapSort(String s){
int numZeros = 0;
int count = 0;
for(int i=s.length-1; i<=0; i++ ){
if(numZeros > 0 && s.charAt(i)=='1'){
count = count + numZeros;
}
else if(s.charAt(i) == '0'){
numZeros++;
}/* end else-if*/
}/*end for*/
return count;
}/*end swapSort*/

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

The idea is:
- I will keep in nextZero the position of the next Zero I will have to swap
- the number of swaps for a zero is the distance between the current position of a zero and the position this zero should be.
Complexity : time - O(n) space- O(1)

``````int nextZero = 0;
int count = 0;
while(bits[k] == 0) k++;
nextZero = k;

for(int i = k; i < bits.length; i++){
if(bits[i]==0){
count += i - nextZero;
nextZero++;
}
}

return count;``````

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

Can we use a bubble sort algorithm ??

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

We are no supposed to sort the list.. just find min swaps required

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

``````int[] arr = new int[] { 0, 0, 1, 0, 1, 0, 1, 1 };
int start = 0, end = arr.length - 1, swapCount = 0;
while( start < end ) {
while( arr[ start ++ ] == 0 );
while( arr[ end-- ] ==  1 );

if ( start - 1 < end + 1 ) {
arr[ start - 1 ] = 0;
arr[ end + 1 ] = 1;
swapCount++;
}
}
System.out.println( swapCount );``````

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

1. Count number of zeroes
2. Now - while number of zeroes before the first 1 encountered is not equal to the total number of zeroes - run a recursive Swap method.

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

And the order is O(n)

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

``````int array[]={0,0,1,0,1,0,1,1};
int array2[]={1,1,0,0};
int swapCount=0;

int i=0,j=array.length-1;
while(i<j){
while(array[i]==0 && i<array.length-1){
i++;
}
while(array[j]==1 && j>0){
j--;
}
if(i<j){
swapCount++;
int temp=array[i];
array[i]=array[j];
array[j]=temp;
}

}
System.out.println("Total no of swaps : "+swapCount+" final array ");
for(int k=0;k<array.length;k++)
{
System.out.println(array[k]);``````

}

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.