## Amazon Interview Question Software Engineer / Developers

• 0

Without using extra space place all zeroes to left and 1's to right from an array of Zero's and 1's as below
011001 ans. 000111

``````public class Zeros_ones_New {

/**
* @param args
*/
public static void main(String[] args) {
int[] arrZerosOnes = { 0,1,0,1,0,1,1 };
int len = arrZerosOnes.length;
int firstOne = -1;
int lastZero = len;
for (int i = 0; i < len; i++) {
if (arrZerosOnes[i] == 1) {
firstOne = i;
break;
}
}

for (int u = len - 1; u > -1; u--) {
if (arrZerosOnes[u] == 0) {
lastZero = u;
break;
}
}

if (firstOne > -1 && lastZero<len) {
while (firstOne<lastZero) {

for (int j = firstOne; j < lastZero; j++) {
if (((j + 1) <= lastZero) && (j == firstOne)
&& (arrZerosOnes[j + 1] == 0)) {
arrZerosOnes[j] = 0;
arrZerosOnes[j + 1] = 1;
firstOne++;
/*if ((j + 1) == lastZero) {
break;
}*/
} else if (((j + 1) <= lastZero) && (arrZerosOnes[j] == 1)
&& (arrZerosOnes[j + 1] == 0)) {
arrZerosOnes[j] = 0;
arrZerosOnes[j + 1] = 1;
if ((j + 1) == lastZero) {
lastZero--;
}
}
}
}
}

for (int t = 0; t < len; t++) {
System.out.print(arrZerosOnes[t]);
}
}

}``````

Country: India
Interview Type: Phone Interview

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

``````#include<iostream.h>
void zerothenone(int *a,int n)
{
int i=0,j=n;
while(i<j)
{
if(a[i]==0 && a[j]==1)
{ i++; j--; }
if(a[i]==0 && a[j]==0)
{ i++; }
if(a[i]==1 && a[j]==0)
{ int t = a[i];
a[i] = a[j];
a[j] = t;
i++; j--;
}
if(a[i]==1 && a[j]==1)
{ j--;}

}
}
int main()
{ int c[10] = {0,0,1,0,1,1,1,0,0,};
int l = sizeof(c)/sizeof(c[0]);
zerothenone(c,l-1);
for(int i=0;i<=9;i++)
{ cout<<c[i]<<"\t";
}
getchar();
return 0;
}``````

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

The person who posted this question mentioned the restriction that you could only swap adjacent numbers. (This person added this on July 22, 2012 and said that he forgot to add this contraint)

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

Traverse the array from left to right and keep on storing the number of 1s till that index at each status.
Once traversal is done, traverse it from right to left, if the current index is more than 0 then replace current element with 1 and decrease the next element by 1. If you hit a 0 then all elements left to it should be 0.

``````public class ZeroOneSeparator {

public static void zeroOneSeparator(int[] inputArr){
for(int i = 1; i < inputArr.length; i++){
inputArr[i] = inputArr[i-1] + inputArr[i];
}
for(int i = inputArr.length - 1; i > 0 ; i--){
if(inputArr[i] > 0){
inputArr[i-1] = inputArr[i] - 1;
inputArr[i] = 1;
}else
inputArr[i-1] = 0;
}
for(int i = 0; i < inputArr.length; i++)
System.out.print(inputArr[i]);
}

public static void main(String[] args) {
int[] inputArr1 = {1,0,1,0,1,1};
ZeroOneSeparator.zeroOneSeparator(inputArr1);
System.out.println("");
int[] inputArr2 = {1,1,1,0,0,0,0,0,0,1};
ZeroOneSeparator.zeroOneSeparator(inputArr2);
int[] inputArr3 = {};
System.out.println("");
ZeroOneSeparator.zeroOneSeparator(inputArr3);
int[] inputArr4 = {0,0,0,0,0,0};
System.out.println("");
ZeroOneSeparator.zeroOneSeparator(inputArr4);
int[] inputArr5 = {0,1,0,1,0,1,0,1};
System.out.println("");
ZeroOneSeparator.zeroOneSeparator(inputArr5);
int[] inputArr6 = {1,1,1,1,1,1,0,0,0,0,0};
System.out.println("");
ZeroOneSeparator.zeroOneSeparator(inputArr6);
}

}``````

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

It works, I think.

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

``````#include<iostream.h>
void zerothenone(int *a,int n)
{
int i=0,j=n;
while(i<j)
{
if(a[i]==0 && a[j]==1)
{ i++; j--; }
if(a[i]==0 && a[j]==0)
{ i++; }
if(a[i]==1 && a[j]==0)
{ int t = a[i];
a[i] = a[j];
a[j] = t;
i++; j--;
}
if(a[i]==1 && a[j]==1)
{ j--;}

}
}
int main()
{ int c[10] = {0,0,1,0,1,1,1,0,0,};
int l = sizeof(c)/sizeof(c[0]);
zerothenone(c,l-1);
for(int i=0;i<9;i++)
{ cout<<c[i]<<"\t";
}
getchar();
return 0;
}``````

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

``in main() for(int i=0;i<=9;i++)......all is well ....I don't know why people is going for complex code........``

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

apoorvaGurav's code looks appealing although I did not test. But one condition is that only you may interchange the elements and that also adjacent elements. I meant to say that at anytime 0<=arr[i]<=1

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

1) Count the number of 0's and 1's. (One iteration and two variables)
Let # of zeros = n and # of ones = m.
2) put n zeros in front and m ones at the back.

Example: 011001
1)Count the number of zeros and ones
# of zeros = 3
# of ones = 3

2) The first 3 places are zeros
000XXX
3) The last 3 places are ones
000111

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

Sorry... Apologies.... You can only interchange the adjacent numbers... I forgot this

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

public class xyz {

/**
* @param args
*/
public static void main(String[] args) {
int array[]={1,1,1,1,0,0,0};
for(int i=0;i<array.length;i++)
{if(array[i]==1){

for(int j=i+1;j<array.length;j++)
{
if(array[j]==0){
array[i]=0;
array[j]=1;
break;
}
}
}

}
for(int i =0;i<array.length;i++)
System.out.println(array[i]);
}

}

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

You are not checking whether i and j are adjacent

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

``````public static void sortBinary(int []s) {

int st = 0  ,end = s.length-1;
int t  ;

while ( st < end) {
if ( s[st] !=1) st++ ;

if ( s[end] !=0) end--;

if (s[st] ==1 && s[end] == 0) {
t = s[st] ;
s[st] = s[end] ;
s[end] = t ;
st++ ; end-- ;
}
}

for (int i:s)
System.out.print(i);

System.out.println("");
}

sortBinary(new int [] {0,1,1,1,1,1,1,0,0,0,1});``````

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

st and end should be adjacent while being interchanged

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

``````previous one contains bug :-)

public static void sortBinary(int []s) {

int st = 0  ,end = s.length-1;
int t  ;

while ( st < end) {
if ( s[st] !=1) st++ ;

if ( s[end] !=0) end--;

if ( st < end && s[st] ==1 && s[end] == 0) {
t = s[st] ;
s[st] = s[end] ;
s[end] = t ;
st++ ; end-- ;
}
}

for (int i:s)
System.out.print(i);

System.out.println("");
}

sortBinary(new int [] {0,1,1,1,1,1,1,0,0,0,1});``````

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

use quicksort and it will be Olog2N

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

Quicksort interchange far away elements... Not only adjacents

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

``````void fun(int *arr,int n)
{
int i,j=n-1;
for(i=0;i<=j;)
{
if(arr[i]==1)
{
swap(&arr[i],&arr[j]);
j--;
}
else i++;
}
for(i=0;i<n;i++)
{
printf("%d ",arr[i]);
}
}

int main()
{
int arr[]={0,1,1,0,0,1};
fun(arr,sizeof(arr)/sizeof(arr[0]));

return 0;
}``````

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

#include<stdio.h>
#include<stdlib.h>

int main()
{
int i=0,j,n;
printf("enter the no of values\n");
scanf("%d",&n);
int *a=(int *)malloc(sizeof(int)*n);
printf("enter the nos.\n");
while(i<n)
scanf("%d",&a[i++]);
i=0,j=n-1;
while(i<=j)
{
if(a[i]==1 && a[j]==0)
{
a[i]=0;
a[j]=1;
i++;
j--;
}
else
{
if(a[i]==0)
i++;
if(a[j]==1)
j--;
}
}
i=0;
while(i<n)
printf("%d ",a[i++]);
return;
}

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

a simple way, O(n/2)
int[] arrZerosOnes = { 0,1,0,1,0,1,1 };
int firstOne = -1;
int oneCounter = 0;
int j = arrZerosOnes.Length - 1;
for (int i = 0; i < arrZerosOnes.Length/2; i++)
{
if (arrZerosOnes[i] == 1)
{
if (oneCounter == 0)
{
firstOne = i;
oneCounter = 1;
}
else
{
oneCounter++;
}

}
if (arrZerosOnes[j]==0)
{
if(oneCounter>0)
{
arrZerosOnes[j] = 1;
arrZerosOnes[firstOne++] = 0;
}
}
j--;
}

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

have some mistake

``````int[] arrZerosOnes = {1,0,1,0,1,1,0,0,1};
int firstOne = -1;
int oneCounter = 0;
int lastZero = -1;
int zeroCounter = 0;
int j = arrZerosOnes.Length - 1;
for (int i = 0; i <= j; i++)
{
if (arrZerosOnes[i] == 1)
{
if (oneCounter == 0)
{
firstOne = i;
}
oneCounter++;

}
if (arrZerosOnes[j]==0)
{
if (zeroCounter==0)
{
lastZero = j;
}
zeroCounter++;
}

if(oneCounter>0&&zeroCounter>0)
{
arrZerosOnes[lastZero--] = 1;
arrZerosOnes[firstOne++] = 0;
oneCounter--;
zeroCounter--;
}
j--;
}``````

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

``````no warranty
public static void sortBinary(int[] s) {

int t;
int cnt;

for (;;) {
int st = s.length - 2, end = s.length - 1;

while (st > -1) {

if (s[end] == 0 && s[st] == 1) {
t = s[st];
s[st] = s[end];
s[end] = t;

}
st--;
end--;
}

st = 0;
end = 1;
while (end < s.length) {

if (s[end] == 0 && s[st] == 1) {
t = s[st];
s[st] = s[end];
s[end] = t;

}

st++;
end++;
}

cnt = 0;
for (int i = 0; i < s.length - 1; i++)
if (s[i] != s[i + 1])
cnt++;

if (cnt == 1)
break;

}
for (int i : s)
System.out.print(i);

System.out.println("");
}

sortBinary(new int [] {1,1,1,0});``````

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

``````public static void sortBinary(int[] s) {

int t;
int cnt;

for (;;) {
int st = s.length - 2, end = s.length - 1;
while (st > -1) {
if (s[end] == 0 && s[st] == 1) {
t = s[st];
s[st] = s[end];
s[end] = t;
}
st--;end--;
}
st = 0;end = 1;
while (end < s.length) {
if (s[end] == 0 && s[st] == 1) {
t = s[st];
s[st] = s[end];
s[end] = t;
}
st++;end++;
}
cnt = 0;
for (int i = 0; i < s.length - 1; i++)
if (s[i] != s[i + 1])
cnt++;
if (cnt == 1)
break;
}
for (int i : s)
System.out.print(i);

System.out.println("");
}

sortBinary(new int [] {1,1,1,0});``````

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

``````Bubble sort is enough

public static void doIt(int[] a) {

int tmp ;
for (int i = 0 ; i < a.length; i++)
for (int j =0 ;j< a.length-1 ; j++)
if ( a[j] >a[j+1]){

tmp = a[j];
a[j] =a[j+1] ;
a[j+1] = tmp;
}

for (int i : a)
System.out.print(i);

System.out.println("");
}

doIt(new int [] {0,1,1,1,0,1,1,0,0,0,1,0});``````

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

simple method ,O(n/2)

#include<iostream.h>
#define size 6
void swap(int *x,int *y){
*x=*x+*y;
*y=*x-*y;
*x=*x-*y;
}
void main(){
int i,j=0,k=0,one,zero,arr[]={0,1,1,0,0,1};
cout<<"Orig: ";
for(i=0;i<size;i++)
cout<<arr[i]<<" ";
for(i=0;i<=size/2;i++){
for(;j<size/2;j++)
if(arr[j]==1){
one=j;
break;
}

for(;k<size/2;k++)
if(arr[size-1-k]==0){
zero=size-1-k;
break;
}
swap(&arr[one],&arr[zero]);
}

cout<<"\nRes : ";
for(i=0;i<size;i++)
cout<<arr[i]<<" ";
}

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

They expecting program using shift operator and bit operations

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

Given number is integer like=> 128--->00000000 00000000 00000000 10000000.

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

#include<stdio.h>
#include<conio.h>

void main()
{

unsigned int n=127;
int count=0;
int i;

clrscr();

for(i=1;n;i=i<<1) // count the number of 1's and make it 0;
if(n&i)
{
count++;
n=n^i;
}

printf("\n number of 1's =%d \n",count);

/* now n value become zero and we have cout the number of 1s bits */

while(count) // add number of one to the right most...
n= n|1<<sizeof(int)*8 - count--;
printf("%u",n);
getch();
}

o/p
number of 1's =7
65024

/* Remark :-- if number is int only then it wil be ans must be negative
*/

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

#include <stdio.h>

void segregate_zero_one(int * a, int len)
{
int itr = 0;
int last_one = -1;
for (itr = 0 ; itr < len ; itr++)
{
if (a[itr] == 0 && last_one >= 0)
{
a[itr] = 1;
a[last_one] = 0;
last_one++;
}
else if (a[itr] == 1 && last_one == -1)
{
last_one = itr;
}
}
}

void print(int * a, int len)
{
int itr = 0;
for (itr= 0 ; itr < len ; itr++)
{
printf("%d ", a[itr]);
}
printf("\n");
}

int main()
{
int k[14] = {0, 1, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 1, 1};
print(k, 14);
segregate_zero_one(k, 14);
print(k, 14);
}

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

public class Bedmas {
public static void main(String[] args) throws NumberFormatException, IOException
int size;
int[] a=new int[size];
for(int i=0;i<size;i++)
int[] ones=new int[size/2];
int g=0,h=0;
int[] zeroes=new int[size/2];
for(int i=0;i<size/2;i++)
{if(a[i]==1){ones[g]=i;g++;}
else{}
}
for(int i=0;i<size/2;i++)
{if(a[size-1-i]==0){zeroes[h]=(size-1-i);h++;}}
for(int i=0;i<h;i++)
{int j=a[ones[i]];
a[ones[i]]=a[zeroes[i]];
a[zeroes[i]]=j;}
for(int i=0;i<size;i++){System.out.println(a[i]);}
}
}

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

Use counting sort and get the answer .

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

public class SortingZeroToOne {
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
int parentIndex = -1;
int currentIndex = -1;
int[] arr = {0, 1, 1, 0, 0, 1};
for(int i = 0; i<arr.length; i++){
if(arr[i] == 0){
parentIndex = currentIndex;
currentIndex = i;
if(parentIndex != -1){
int temp = arr[parentIndex + 1];
arr[parentIndex + 1] = arr[currentIndex];
arr[currentIndex] = temp;
currentIndex = parentIndex +1;
}}else{
continue;
}}
for(int i = 0; i<arr.length; i++){
System.out.print( " " +arr[i]);
}}}

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book walking you through every aspect of getting a job at a top tech company, while focuses on software engineering interviews.

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