Amazon.com
3.4 of 5 2,795 reviews
www.amazon.com Seattle, WA 5000+ Employees

Amazon.com Software Development Engineer Intern Interview Question

I interviewed in Seattle, WA and was asked:
"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."
Add Tags [?]
Answer Flag Question

Part of a Software Development Engineer Intern Interview Review - one of 4,129 Amazon.com Interview Reviews

Answers & Comments

2
of 3
votes
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 Flag Response
0
of 0
votes
How about using Merge Sort? It would be done in O(nlogn).
- Rahul on Jan 7, 2013 Flag Response
0
of 0
votes
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 Flag Response

To comment on this question, Sign In with Facebook or Sign Up


Tags are like keywords that help categorize interview questions that have something in common.

Glassdoor is your free inside look at Amazon.com interview questions and advice. All interview reviews posted anonymously by Amazon.com employees and interview candidates.