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

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

You can only traverse the array once?

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

sorry it was intended for below comment

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

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

}

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

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

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

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

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

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

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

You can only traverse the array once?

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

bakwaas

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

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

excellent code

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

Perfect. Thanks!

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

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 )

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;

}

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

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

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

3-way quick sort with G as pivot.

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

3-way quick sort with G as pivot.

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

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

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

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

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

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

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

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

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

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

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

Anjana's soln is ideal.

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

How about an in-place Merge sort?

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

please comment if u find it correct

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

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.

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

}``````

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

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

what is the value of low and high???

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

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;

}
}

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

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

}
}

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

}

}

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.

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.

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.

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.

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