Amazon Interview Question for Software Engineer / Developers


Country: India
Interview Type: Written Test




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

en.wikipedia.org/wiki/Dutch_national_flag_problem

- P May 12, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

You can only traverse the array once?

- Anonymous May 16, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

sorry it was intended for below comment

- Anonymous May 16, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

void DutchFlag()
{
	int a[12]={3,3,2,2,2,2,3,2,2,2,2,1};
	int p2=0,p3=0;
	for(int i=0;i<12;i++)
	{
		switch (a[i])
		{
			case 1:
				{
					if(i>p2) {
						swap(&a[i],&a[p2]);
						p2++;
					}
					if(a[i]==2)
					{
						if(i>p3)
						{
							swap(&a[i],&a[p3]);
							p3++;
						}
					}
					else
					{
						p2++,p3++;
					}
				break;
				}
			case 2:
				{
					if(i>p3)
					{
						swap(&a[i],&a[p3]);
						p3++;
					}
					else
					{
						p3++;
					}
				break;
				}
			case 3:
				{
				break;
				}
		}
	}

}

- Anonymous December 27, 2013 | Flag
Comment hidden because of low score. Click to expand.
6
of 6 vote

threeWayPartition(char data[], int size)
{
  	int p = 0;
  	int q = size-1;
  	int i ;

 	char t;
        for ( i = 0; i <= q;)
        {
                if (data[i] == 'R')
                {
                      t = data[i];
                        data[i] = data[p];
                        data[p] = t;
                        ++p;
                        ++i;
                }

                else if (data[i] == 'G')
                {
                        t = data[i];
                        data[i] = data[q];
                        data[q] =t;
                        --q;
                }
                else
                {
                        ++i;
                }
        }
}

Input:
R G B G B G B R R B G R R B B G R

Output:
R R R R R R B B B B B B G G G G G

- Abs May 27, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

it shud be
else if (data[i] == 'B')
instead of
else if (data[i] == 'G')

- Aditya Goel July 28, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

aditya is rite...output should be RGB, not RBG

- Anonymous August 30, 2012 | Flag
Comment hidden because of low score. Click to expand.
4
of 10 vote

Just maintain count of R, G, and B. And then overwrite whole array. Some thing like below

void Sort(char *arr, int len)
{
     int count[3] = {0, 0, 0};
     char chars[3] = {'R', 'G', 'B'};
     for (int i = 0; i < len ++ len)
     {
          if (arr[i] == 'R') ++count[0];
          else if (arr[i] == 'G') ++count[1];
          else if (arr[i] == 'B') ++count[2];
          // in else print error and return
   }
   
   int k = 0;
   for (int i = 0; i < 3; ++i)
   {
      for (int j = 0; j < count[i]; ++j)
      {
          arr[k++] = chars[i];
      }
   }
}

- bugbug May 13, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

You can only traverse the array once?

- Anonymous May 16, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

bakwaas

- Anonymous August 30, 2012 | Flag
Comment hidden because of low score. Click to expand.
2
of 2 vote

int main()
{
int r,g,b,i;
char x[] = {'r','r','g','g','b','r','r','r','g','g','b','b','b','g','g','r'}
for (i = 0;r = 0,g=0,b=0; x[i] != '\0' ;}
{
if(x[i] == 'r')
r++;
else if(x[i] == 'g')
g++;
else
b++;


}
memset(x,'r',r);
memset(x+r,'g',g);
memset(x+r+g,'b',b);
}

- softy June 06, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

excellent code

- nitin1986 August 26, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Perfect. Thanks!

- Anonymous September 21, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

memset is like traversing .
what would you do if you were told that no library calls are allowed ? ( which is the case in many interviews )

- Ran November 26, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void sortAnArrayInParticularOrder(char [] array){
int indexOfR = 0;
int indexOfB = array.length-1;
for(int i=0;i<=indexOfB;){
if(array[i]=='R'){
swap(i,indexOfR,array);
indexOfR ++;
i++;
} else if (array[i]=='B'){
swap(i,indexOfB,array);
indexOfB --;
}else{
i++;
}
}

for(char c:array){
System.out.println(c);
}

}

private static void swap(int i, int j, char[] array) {
char temp = array[i];
array[i]=array[j];
array[j]=temp;

}

- vibhanshu jha May 14, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int begin=0;
int end=n-1;
while(begin<end)
{
if (A[begin]=='G')
{
temp=begin+1;
while(A[temp]=='G')
temp++;
if(temp==end)
return;
else
{
swap(A[temp], A[begin])
}

}
if(A[begin]=='B')
{
swap(A[begin],A[end])
}
if(A[begin]=='R')
{
begin++;
}

if(A[end]=='G')
{
temp=end-1;
while(A[temp]=='G')
temp--;
if(temp==begin)
return;
else
{
swap(A[temp], A[end])
}
}
if(A[end]=='R')
{
swap(A[end],A[begin])
}
if(A[end]=='B')
{
end--;
}
}

- newcoder May 17, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int begin=0;
int end=n-1;
while(begin<end)
{
if (A[begin]=='G')
{
temp=begin+1;
while(A[temp]=='G')
temp++;
if(temp==end)
return;
else
{
swap(A[temp], A[begin])
}

}
if(A[begin]=='B')
{
swap(A[begin],A[end])
}
if(A[begin]=='R')
{
begin++;
}

if(A[end]=='G')
{
temp=end-1;
while(A[temp]=='G')
temp--;
if(temp==begin)
return;
else
{
swap(A[temp], A[end])
}
}
if(A[end]=='R')
{
swap(A[end],A[begin])
}
if(A[end]=='B')
{
end--;
}
}

- newcoder May 17, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

3-way quick sort with G as pivot.

- s May 21, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

3-way quick sort with G as pivot.

- s May 21, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

That took longer than it should have. C# The 'trick' was that you can only traverse once, but you don't necessarily need to increment your enumerator.

static void Sort(char[] values)
        {
            int rPointer = 0, bPointer = values.Length - 1,i=0;
            char temp;
            while ( i <= bPointer )
            {
            Return:
                switch (values[i])
                {
                    case 'R':
                        temp = values[rPointer];
                        values[rPointer] = 'R';
                        values[i] = temp;
                        while (values[rPointer] == 'R')rPointer++ ;
                        break;
                        
                    case 'B':
                        temp = values[bPointer];
                        values[bPointer] = 'B';
                        values[i] = temp;
                        while (values[bPointer] == 'B')bPointer-- ;
                        break;
                    case 'G':
                        i++;
                        break;
                }
            }
        }

- Christopher.R.Klein June 01, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

case 'B':
i++;
break;
and replace the B with G in the original case "B"

- elonso June 04, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

void swap(char * to,char *from)
{
char t = *to;
*to = *from;
*from = t;
}

void arrange(char str[] )
{
//if(!str) return ;
cout<<"before :"<<str<<endl;
int n = strlen(str);
int last[3]= {0,0,n-1};

for(int i=0;i<n;++i)
{
if(str[i] == 'R' )
{
swap(&str[last[0]],&str[i]);
++last[0] ;
}
else if(str[i] == 'B' && i<last[2])
{
swap(&str[i],&str[last[2]]);
--last[2];
}
else if(str[i] == 'G' )
{
last[1]=i ;
}

cout<<"Iteration :"<<i<<" "<<last[0]<<" "<<last[1]<<" "<<last[2]<<endl;
}

cout<<"after :"<<str<<endl;
}

- santosh patro June 06, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

char a[]="RGRBRGBRGBRGBRGRRGRGRGRGR"; should be the input

I was trying the reverse one after i solved this , Hence the wrong input

- Shiv June 18, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<iostream>
using namespace std;

void swap(char *x, char *y)
{
	cout<<"Entered swap";
	char temp;
	temp = *x;
	*x=*y;
	*y=temp;
	cout<<"Finished swap";
}

int main()
{
	char a[]="RRRRGGGGBBBB"; // Desired output RGBRGBRGBRGB
	int size = sizeof(a)/sizeof(a[0]);
	
	int low =0;
	int mid =0;
	int high = size-2;
	cout<<size<<high<<mid<<low;
	char temp;
	while(mid<=high)
	{
		
		if(a[mid]== 'R')
		{
			
			swap(&a[low],&a[mid]);
			low++;
			mid++;
		}
		else if(a[mid] == 'B')
		{
			mid++;
		}
		else if(a[mid] == 'G')
		{
			swap(&a[high],&a[mid]);
			
			high--;
			
		}
		for(int i=0;i<size-1;i++)
			{
				cout<<a[i];
			}
			cout<<endl;
	}
	
	for(int i=0;i<size-1;i++)
	{
		cout<<a[i];
	}
	
	return 0;
}

- Shiv June 18, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

void rearrange(char *s)
{
    int i;
    int length = strlen(s);
    int firstp=0;
    int lastp=length-1;
    int flag = 0;
    if(length>1)
    {
        while (firstp <length && s[firstp] == 'R')
            firstp++;
        while (lastp >= 0 && s[lastp] == 'B')
            lastp--;
        i=firstp;
        while (i<=lastp) 
        {
            i = i < firstp? firstp: i;
            if(s[i] == 'R')
            {
                s[i] = s[firstp];
                s[firstp] = 'R';
            }
            else if (s[i] == 'B') 
            {
                s[i] = s[lastp];
                s[lastp] = 'B';
            }
            else
                i++;
            while (firstp <length && s[firstp] == 'R')
                firstp++;
            while (lastp >= 0 && s[lastp] == 'B')
                lastp--;
        }
    }
}

- Bidhan Pal June 25, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

keep a red pointer from start, and blue pointer from end. Move the red pointer forward until you fing a non R character. Move the blue pointer backwards until you find a non B character. Initialize a green character from the current red position and keep moving until you find R/B. if you find R/B swap them and increase/decrease the corresponding pointer

- Anjana June 26, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Anjana's soln is ideal.

- Balaji July 07, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

How about an in-place Merge sort?

- Balaji July 07, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

please comment if u find it correct

- ritika July 31, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

we r allowed to traverse the array only once. it means time complexity is O(n).
no way we will use a complicated algo like "in order" merge sort to solve this problem which takes O(nlogn) time.

- Aditya Goel July 31, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

low=0;
    high=n;//size of array;
    for(i=0;i<n;)
    {    
           if(arr[i]<'G')
              swap(arr[i++],arr[low++]);
           else if(arr[i]>='G')
              swap(arr[i],arr[high--]);
           else i++;
              
    }

- Anonymous July 31, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

void threeWayPartition(int data[], int size, int low, int high) {
int p = -1;
int q = size;
for (int i = 0; i < q;) {
if (data[i] < low) {
swap(data[i], data[++p]);
++i;
} else if (data[i] >= high) {
swap(data[i], data[--q]);
} else {
++i;
}
}
}

- Shreyas November 04, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

what is the value of low and high???

- visanth August 09, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <stdio.h>
int main()

{
char data[] = "BRBRBRBGRGRGRRGRGRGRBRBRBR";
int size = sizeof(data)/sizeof(data[0]);
int index= 0;

int gFirstPosition;
int bFirstPosition;

int gVisit= 0;
int bVisit= 0;

printf("input: %s\n", data);

while (index < size)
{
if (data[index] == 'R')
{
if (gVisit == 1 && bVisit == 1)
{
data[gFirstPosition]= 'R';
data[bFirstPosition]= 'G';
data[index]= 'B';
gFirstPosition++;
bFirstPosition++;
}
else if (gVisit == 1 && bVisit == 0)
{
data[gFirstPosition]= 'R';
data[index]= 'G';
gFirstPosition++;
}
else if (gVisit == 0 && bVisit == 1)
{
data[bFirstPosition]= 'R';
data[index]= 'B';
bFirstPosition++;
}
}
else if (data[index] == 'G')
{
if (gVisit == 0)
{
gFirstPosition= index;
gVisit= 1;
}

if (bVisit == 1)
{
data[bFirstPosition]= 'G';
data[index]= 'B';
if (gFirstPosition > bFirstPosition)
gFirstPosition= bFirstPosition;

bFirstPosition++;
}

}
else if (data[index] == 'B')
{
if (bVisit == 0)
{
bFirstPosition= index;
bVisit= 1;
}
}
index++;
}

printf("output: %s\n", data);

return 0;
}

- Alireza March 01, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.Arrays;


public class SortRGB {

public static void main(String[]args){
char[]arr={'R','G','B','R','B','R','R','B','R','G','B','B','B','R','R','G','B'};

sortRGB(arr,'G','G');
System.out.println(Arrays.toString(arr));
}

private static void sortRGB(char[] arr, char key1, char key2) {
int p=0;
int size=arr.length-1;
int q=size;
for(int i=0;i<=q;){
if(arr[i]>key1){

swap(arr,p,i);
p++;
i++;
}
else if(arr[i]<key2){

swap(arr,i,q);
q--;
}
else{
i++;
}
}

}

private static void swap(char[] arr, int p, int q) {
char temp=arr[p];
arr[p]=arr[q];
arr[q]=temp;

}
}

- Sudhansu November 09, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<stdio.h>
#include<string.h>

int main()
{
	char c[] = {'r','g','b','g','b','g','b','r','r','b','g','r','r','b','b','g','r'},temp;
	int r=0,g=0,b=0,i;
	for(i=0;i<(sizeof(c)/sizeof(c[0]));i++) {
		if(c[i] == 'r') {
			temp = c[r];
			c[r] = c[i];
			c[i] = temp;
			r++;
			g++;
			b++;
		}
		else if(c[i] == 'g') {
			temp = c[g];
			c[g] = c[i];
			c[i] = temp;
			g++;
			b++;
		}
		else if(c[i] == 'b') {
			temp = c[b];
			c[b] = c[i];
			c[i] = temp;
			b++;
		}
	}
	for(i=0;i<(sizeof(c)/sizeof(c[0]));i++) 
		printf("%c",c[i]);
	printf("\n");
	return 0;		
}

- agmegharaj November 25, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

void swp(char a[], int sz)
{
int i=0,p=0,q=sz-1;
char temp;

while (i<q) {

if (a[p]=='r')
{
p++;
i++;
}
if (a[q]=='b')
q--;

if (a[p] != 'r' and a[q]=='r') {
temp = a[p];
a[p]= a[q];
a[q]= temp;
p++;
i++;
}
else if (a[q] != 'b' and a[p]=='b') {
temp = a[p];
a[p]= a[q];
a[q]= temp;
q--;
}

else if (a[p] != 'r' and a[i]=='r') {
temp = a[p];
a[p]= a[i];
a[i]= temp;
p++;
i++;
}
else if (a[q] != 'b' and a[i]=='b') {
temp = a[i];
a[i]= a[q];
a[q]= temp;
q--;
}

else
i++;

}
}

- adataengineer July 22, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.lang.reflect.Array;
import java.util.Arrays;
import java.util.Scanner;

public class Sortofchararray {

public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner sc = new Scanner(System.in);
int n =sc.nextInt();
// char arr[]= {'G','G','R','B', 'R', 'B', 'B', 'G', 'R', 'B', 'R'};
char arr[] = new char[n];
for(int p=0; p<arr.length; p++) {
char ch = sc.next().charAt(0);
arr[p]=ch;
}
Arrays.sort(arr);
int i=0;
int j =arr.length-1;
while(i<=j) {
char t = arr[i];
arr[i]= arr[j];
arr[j]= (char) t;
i++;
j--;
}
for(int p=0; p<arr.length; p++) {
System.out.print(arr[p]+" ");
}

}

}

- monu singh July 25, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

yup similar to sort 0,1,2 or dutch national flag algo.

- time May 13, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

yup similar to sort 0,1,2 or dutch national flag algo.

- time May 13, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

yup similar to sort 0,1,2 or dutch national flag algo.

- time May 13, 2012 | 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