Amazon Interview Question Software Engineer / Developers

  • amazon-interview-questions
    -1
    of 1 vote
    32
    Answers

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

    - banerjees36 on June 22, 2012 in India Report Duplicate | Flag
    Amazon Software Engineer / Developer

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

- saurabh on June 24, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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)

- m.b on June 30, 2012 | Flag
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);
	}

}

- apoorvagaurav on June 22, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

It works, I think.

- Yaya on June 24, 2012 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 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;
}

- saurabh on June 24, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- saurabh on June 24, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- banerjees36 on June 25, 2012 | Flag
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

- m.b on June 22, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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

- banerjees36 on June 22, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

reminding me abacus...

- murlikrishna.b on July 01, 2013 | Flag
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]);
}

}

- Nilima on June 22, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

You are not checking whether i and j are adjacent

- banerjees36 on June 22, 2012 | Flag
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});

- Anonymous on June 22, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

st and end should be adjacent while being interchanged

- banerjees36 on June 22, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous on June 22, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

use quicksort and it will be Olog2N

- capsen on June 22, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Quicksort interchange far away elements... Not only adjacents

- banerjees36 on June 22, 2012 | Flag
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;
}

- Aashish on June 22, 2012 | Flag Reply
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;
}

- Prabal on June 22, 2012 | Flag Reply
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--;
}

- capsen on June 22, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- capsen on June 22, 2012 | Flag
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});

- Anonymous on June 22, 2012 | Flag Reply
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});

- Anonymous on June 22, 2012 | Flag Reply
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});

- Anonymous on June 22, 2012 | Flag Reply
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]<<" ";
}

- manishvaidya on June 22, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

They expecting program using shift operator and bit operations

- Amazon 3rd round is scheduled on June 23, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- govind.chauhan143 on June 24, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

#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
*/

- govind.chauhan143 on June 24, 2012 | Flag
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);
}

- Software Architect on June 24, 2012 | Flag Reply
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
{BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
int size;
size=Integer.parseInt(br.readLine());
int[] a=new int[size];
for(int i=0;i<size;i++)
{a[i]=Integer.parseInt(br.readLine());}
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]);}
}
}

- faisal.mehfooz on June 26, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Use counting sort and get the answer .

- kk on June 26, 2012 | Flag Reply
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]);
}}}

- Anonymous on June 28, 2012 | Flag Reply


Add a Comment
Name:

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

Books

is a comprehensive book walking you through 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