Amazon Interview Question Software Engineer / Developers
Country: India
Interview Type: Written Test
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;
}
}
}
}
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
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];
}
}
}
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);
}
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;
}
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--;
}
}
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--;
}
}
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;
}
}
}
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;
}
#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;
}
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--;
}
}
}
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
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;
}
}
}
#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;
}
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;
}
}
#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;
}
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++;
}
}
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]+" ");
}
}
}
en.wikipedia.org/wiki/Dutch_national_flag_problem
- P May 12, 2012