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)

- Anirban October 29, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

how would this work for 111000 ?

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

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.

- etilist November 10, 2012 | Flag
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.

- Rohit May 18, 2013 | Flag
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'.

- Anirban May 30, 2013 | Flag
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;
}

- sjain October 29, 2012 | Flag Reply
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;
}

- pratikrd October 29, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- hudibaba November 05, 2012 | Flag Reply
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*/

- hudibaba November 05, 2012 | Flag Reply
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;

- Kamy December 11, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Can we use a bubble sort algorithm ??

- avikodak December 24, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous March 27, 2013 | Flag
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 );

- brath April 28, 2013 | Flag Reply
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.

- Anonymous August 30, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

And the order is O(n)

- Anonymous August 30, 2013 | Flag
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]);

}

- freebird September 12, 2013 | Flag Reply


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