Google Interview Question Software Engineer in Tests
void group_color(char * str){
// variant is [0..g-1] are red balls, [g,b-1] are green balls
// [b,i-1] are blue balls.
int g=0, b=0, i=0;
char temp;
while (str[i]!='\0'){
if (str[i]=='r') {
// red ball
temp = str[g]; // temp is a green ball now
str[g]=str[i]; // send red ball to its area
g++;
str[i] = temp; // str[i] now is a green ball
}
if (str[i]=='g') {
// red ball
temp = str[b]; // temp is a blue ball now
str[b]=str[i]; // send green ball to its area
b++;
str[i] = temp; // str[i] now is a blue ball
}
i++;
}
}
int nums[] = {1,1,1,2,1,1,2,2,1,0,2,1};
void swap(int a, int b){
int temp = nums[a];
nums[a] = nums[b];
nums[b] = temp;
}
void formDutchFlag(){
int length = 12;
/*
b: index to the growing bottom
t: index to the reducing top
m: index to the top of the middle
Traverse using the middle index
*/
int b = 0;
int m = 0;
int t = length - 1;
while (m != t) {
if (nums[m] == 0) {
swap(m,b);
b++;
m++;
}
else if (nums[m] == 2) {
/* Don't increment m because the number that you just swapped might need to be placed at the bottom*/
swap(m,t);
t--;
} else
m++;
}
}
Maintain two pointers, one pointing to the end of 0's, the other pointing to the start of 2's. Similar to the partition routine in quick sort, for loop through the array using a current pointer i until pointer i meets the start of 2's. A little trick is to make sure there is no immediate 2's to the left of the start pointer of 2's; otherwise, it might cause too many cases. Another simple while loop would resolve it.
Since the termination condition of the for loop is the current pointer meets the start pointer of 2's, the whole program is still a single scan.
It seems to be easier:
int curRed = 0;
int curBlue = n-1;
for (int i = 0; i < n; i++)
{
if (a[i] == "blue")
{
swap(a[i], a[curBlue]);
--curBlue;
}
if (a[i] == "red")
{
swap(a[i], a[curRed]);
++curRed;
}
}
Something on the lines of Lomuto's partitioning algorithm for quicksort and it works.
void swap(int *x, int *y)
{
int temp = *x;
*x = *y;
*y = temp;
}
int threewaypart(int a[], int p, int q)
{
int i = p-1, j = p-1, k = q+1, l = p;
for (;l<k; l++)
{
if (a[l] == 1)
j++;
else if (a[l] == 0)
{
swap(&a[++i], &a[l]);
j++;
}
else
{
swap(&a[--k], &a[l]);
--l;
}
}
}
void arrangearray( int *arr, int len )
{
int f,l;
int fi,li;
int i;
int t;
fi = 0;
f = arr[fi++];
while( arr[fi] == f ) fi++;
if( fi > len ) return;
l = arr[fi];
li = len-1;
for( i=fi; i<=li; i++ )
{
if( arr[i] == l )
{
while( arr[li] == l ) li--;
if( i<li )
{
t = arr[i];
arr[i] = arr[li];
arr[li] = t;
li--;
}
}
if( arr[i] == f )
{
t = arr[i];
arr[i] = arr[fi];
arr[fi] = t;
fi++;
}
}
}
//given a character array with r,b,g separate them into different regions in place
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cstdlib>
using namespace std;
char* dutchAlgo(char *inp) {
int len=strlen(inp);
char *str=(char*)malloc(sizeof(char)*(len+1));
strcpy(str,inp);
int p_red=0,p_blue=len-1;
int i;
for(i=0;i<=p_blue;i++) {
if(str[i]=='r') {
if(i>p_red) {
swap(str[i--],str[p_red]);
}
p_red++;
}
else if(str[i]=='b') {
swap(str[i--],str[p_blue--]);
}
}
return str;
}
int main() {
printf("%s : %s\n","rbg",dutchAlgo("rbg"));
printf("%s : %s\n","rrbbgbrgggbrgbrgbr",dutchAlgo("rrbbgbrgggbrgbrgbg"));
printf("%s : %s\n","rbgbrrggrbbrggrrggrb",dutchAlgo("rbgbrrggrbbrggrrggrb"));
}
Represent each colour by a number and simply sort the arry.
1->red
2->green
3->blue
{red,green,red,blue,green,red,blue} -> {1,2,1,3,2,1,3}
sort
{1,1,1,2,2,3,3} ->{red,red,red,green,green,blue,blue}
Keep swap until you see 0 or 1, and increment the counter
public class Main {
public static void main(String[] args) {
int[] array = new int[]{0, 2, 1, 1, 2, 0, 0, 2, 1, 1, 2, 2};
int posRed = 0;
int posBlue = array.length - 1;
for (int i = 0; i < posBlue;) {
if (array[i] == 0) {
swap(array, i, posRed);
posRed++;
i++;
} else if (array[i] == 2) {
swap(array, i, posBlue);
posBlue--;
} else {
i++;
}
}
for (int i: array) {
System.out.printf("%d ", i);
}
}
private static void swap(int[] array, int a, int b) {
int tmp = array[a];
array[a] = array[b];
array[b] = tmp;
}
}
Keep swap until you see 0 or 1, and increment the counter
public class Main {
public static void main(String[] args) {
int[] array = new int[]{0, 2, 1, 1, 2, 0, 0, 2, 1, 1, 2, 2};
int posRed = 0;
int posBlue = array.length - 1;
for (int i = 0; i < posBlue;) {
if (array[i] == 0) {
swap(array, i, posRed);
posRed++;
i++;
} else if (array[i] == 2) {
swap(array, i, posBlue);
posBlue--;
} else {
i++;
}
}
for (int i: array) {
System.out.printf("%d ", i);
}
}
private static void swap(int[] array, int a, int b) {
int tmp = array[a];
array[a] = array[b];
array[b] = tmp;
}
}
public class ZeroOneTwo {
public static void seperate(int[] arr){
int firstone = 0, lastone = arr.length - 1, temp;
for(int i = 0; i < arr.length ; i++){
if(arr[i] == 0){
if(firstone != i){
temp = arr[i];
arr[i] = arr[firstone];
arr[firstone] = temp;
}
firstone++;
}else if(arr[i] == 2){
while(arr[lastone] == 2) {lastone -- ;}
if(lastone > i){
temp = arr[i];
arr[i] = arr[lastone];
arr[lastone] = temp;
i--;
}
lastone --;
}
}
for(int a : arr){
System.out.print(a);
}
}
public static void main(String args[]){
seperate(new int[] {2,2,2,2,0,0,0,0,1,1,1,1});
}
}
here is nice post on this question
- Jack December 20, 2014campuscoke.blogspot.in/2014/12/given-array-of-red-green-and-blue-balls.html