Amazon Interview Question: Given a string of Rs and Gs, ... | Glassdoor

Interview Question

Software Development Engineer Intern Interview Seattle, WA

Given a string of Rs and Gs, design an algorithm to produce

a string with Rs in the front and Gs after that. The number of flips from Rs to Gs or otherwise should be minimum. The number of Rs and Gs in the end need not be same as that in the beginning, however the length of the entire string should be the same.

2

Regarding the R&G problem... couldn't you just scan the string keeping a count and then regurgitate the values? Essentially you could achieve an O(N) solution.

for (int i = 0; i < inputString.size(); i++) {
if ("R" == inputString.charAt(i)) {
System.out.print("R");
else
++count;
}

for (int i = 0; i < count; i++) {
System.out.print("G");
}

--------

Alternatively I suppose you could swap all "R"s for 1, all "G"s for 0, calculate the binary value and then its a straight output.

RGGGRRGRGGRRRR == 10001101001111 == 9039 == 8x1 = 8xR+6xG = 14char (initial length)

Or am I misunderstanding the way you've explained the question.

Capn on Jul 16, 2012
0

How about using Merge Sort? It would be done in O(nlogn).

Rahul on Jan 7, 2013
0

I think the interviewer's intent is to use the idea of counting sort;
keep one pointer from head tracking Rs, another pointer from tail tracking Gs;
moving forward the head pointer until reach a G;
then moving backward the tail pointer until reach a R;
swap R and G;
move on until the pointers meet;

helloslz on Dec 29, 2013
0

public static void test() {
System.out.println(solution("RGRGRRRGGG".toCharArray()));
}
private static char[] solution(char[] input) {
int i;
int j = input.length - 1;

for(i = 0; i < j; j--) {
while (i < j && input[i] == 'R') {
i++;
}
if(input[j] == 'R') {
input[j] = input[i];
input[i] = 'R';
}
}

return input;
}

Theodor on Nov 29, 2014
0

// Use partition Algorithm

char ch[]=str.toCharArray();

int i=-1;
char q='r',temp;
for(int j=0;j<ch.length-1;j++){
if(ch[j]<q){
i++;
temp = ch[j];
ch[j]=ch[i];
ch[i]=temp;

}

}

temp = q;
ch[ch.length-1]= ch[i+1];
ch[i+1]=temp;

System.out.println(ch);

Anonymous on Apr 15, 2017