This problem was asked by Google.
Given an array of strictly the characters 'R', 'G', and 'B', segregate the values of the array so that all the Rs come first, the Gs come second, and the Bs come last. You can only swap elements of the array.
Do this in linear time and in-place.
For example, given the array ['G', 'B', 'R', 'R', 'B', 'R', 'G'], it should become ['R', 'R', 'R', 'G', 'G', 'B', 'B'].
Below are the 2 ways I tried to solve, one is in-place & other one is not.
In one relative order is maintained & in other is not maintained.
The solution is not efficient one & neither it is in Linear time, so if anyone knows the
answer, pls comment.
Given an array of strictly the characters 'R', 'G', and 'B', segregate the values of the array so that all the Rs come first, the Gs come second, and the Bs come last. You can only swap elements of the array.
Do this in linear time and in-place.
For example, given the array ['G', 'B', 'R', 'R', 'B', 'R', 'G'], it should become ['R', 'R', 'R', 'G', 'G', 'B', 'B'].
Below are the 2 ways I tried to solve, one is in-place & other one is not.
In one relative order is maintained & in other is not maintained.
The solution is not efficient one & neither it is in Linear time, so if anyone knows the
answer, pls comment.
Swap Elements
If we see in such problems, primitive type data is used & there order shouldn't matter like this
'R' should come before that 'R'. If interviewer is putting this constraint then that person has
seen the similar problem in different context & trying to use the same constraint to confuse you
& show him/herself as smarter person.
Even in Google like companies, such questions for certain scenario are prepared after some
analysis and preparation which they expect the candidates to solve during interviews.
So never assume that MAANG companies have higher standards, rather it is more like
marketing strategy to place itself as unique one.
Well, for this problem to solve in linear time & in-place, & without doing swapping like shown
above, we can do the counting & the populate the existing array, like shown below.
And this way it is quite faster than the above ways, means it is applicable if you are having
primitive type data. Plus this way will work for other problem where you will be asked to have
0s & 1s in similar order.
'R' should come before that 'R'. If interviewer is putting this constraint then that person has
seen the similar problem in different context & trying to use the same constraint to confuse you
& show him/herself as smarter person.
Even in Google like companies, such questions for certain scenario are prepared after some
analysis and preparation which they expect the candidates to solve during interviews.
So never assume that MAANG companies have higher standards, rather it is more like
marketing strategy to place itself as unique one.
Well, for this problem to solve in linear time & in-place, & without doing swapping like shown
above, we can do the counting & the populate the existing array, like shown below.
And this way it is quite faster than the above ways, means it is applicable if you are having
primitive type data. Plus this way will work for other problem where you will be asked to have
0s & 1s in similar order.
Counting Swap
Just thinking if I can avoid some iteration part...
So tried like shown below, please comment-
So tried like shown below, please comment-
Counting Swap
