Amazon Interview Question
Software Engineer / DevelopersCountry: India
Interview Type: Written Test
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.
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.
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*/
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;
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 );
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.
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]);
}
Its actually the sum of the number of 0's to the right for each 1. The pseudo code is as follows :-
- Anirban October 29, 2012