Amazon.com

  www.amazon.com
  www.amazon.com

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

Interview Answer

4 Answers

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

Add Answers or Comments

To comment on this, Sign In or Sign Up.