Good morning! Here's your coding interview problem for today.
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'].
Other urls found in this thread:
en.wikipedia.org
twitter.com
Swap B for R and G for B when there are neighboors.
not a linear time solution since you will have to do mutliple passes
Ruth Bader Ginsburg confirmed dead
At last I see
Doing multiple passes is irrelevant to linear time.
[1,2,3].map(some_fn)
[1,2,3].map(some_other_fn)
is still linear.
pass once and put the Rs first. pass again through the rest and put the Gs first. too ezy
Easy.
#include
void RGB_homework(char *, int);
int main(void)
{
char test_array[] = {'G', 'B', 'R', 'R', 'B', 'R', 'G'};
int test_array_length = 7;
RGB_homework(test_array, test_array_length);
for (int i = 0; i < test_array_length; ++i)
putchar(test_array[i]);
putchar('\n');
return 0;
}
void RGB_homework(char * ptr_array, int len)
{
int nb_G_char = 0;
char * ptr_array_bis = ptr_array;
for (int i = 0; i < len; ++i) {
if (ptr_array[i] == 'R')
*(ptr_array_bis++) = 'R';
else if (ptr_array[i] == 'G')
++nb_G_char;
}
while (nb_G_char-- != 0)
*(ptr_array_bis++) = 'G';
ptr_array += len;
while (ptr_array_bis != ptr_array) {
*(ptr_array_bis++) = 'B';
}
}
Pass one time putting every R first and every B last.
Wtf
cant you just loop through once, record the frequencies, and generate a new array? or does that not count as "in-place"
You could also just write over the original array for in-place sorting.
Can someone explain if is better than for performances?
Doing several passes is linear. 10*n is linear over n.
Two pointers one for red counting from the beginning and one for blues form the end. Walk along the array, when you find a red or blue swap with element at the pointer and increment the pointers. That will leave the greens in the middle.
I got one that's a little easier.
Design a data structure that has the following operations and requisite time complexities.
>push O(1)
>pop O(1)
>max O(1)
Space complexity must be O(1).
>multiple passes
As plenty of others have pointed out, a constant number of passes is still linear. 10 * n is linear.
Consider the following function f(x) = 10 * x
f(x) is a linear function.
It's not fixed. I can give you a perfectly unsorted list and it will take n**2/2 swaps. You are basically doing bubble sort, its n**2.
>It's not fixed.
It is, you can solve this in two passes if you count frequencies (as suggested). Or you can do it in three passes, the first one shuffles the 'R's, the second the 'G"s and the final one sets the 'B's.
>in-place and swap only
You broke the rules. But gathering counts and doing an in place replacement is probably just as quick. And a whole lot easier to understand/read.
would a modified quicksort style algo like this work:
you have two pointers. one at the start (left) and one at the end (right) of the array.
do this as long as the pointers don't overlap. the moment they do break out as the loop is over
if the left pointer is not on 'R', move the right pointer down until it encounters an 'R'. when it does, swap the elements at left and right and move them both in their respective directions
if left is on 'R' move left to the next element
at the end of this, all of the 'R' should be to the left of the other elements.
repeat similar partitioning for 'G' and 'B'
d-did I do it uwu? I'm not very smart :c
who tf is this
Dont know. Some (other) guy was handing out his photo in the caf one day.
#!/usr/bin/env python3
import random
def swap(array, i,j):
array[i], array[j] = array[j], array[i]
def rgb_sort(array):
start=-1
end=len(array)
i = 0
while i < end:
while i < end-1 and i > start+1 and array[i]!='G':
if array[i] == 'R':
start+=1
swap(array, start, i)
elif array[i] == 'B':
end-= 1
swap(array, end, i)
i+=1
array = random.choices(['R', 'G', 'B'], k=100)
print (array)
rgb_sort(array)
print (array)
You didn't follow the rules.
rather than solving the problem you should take to social media and call out Google for their bigotry
and even thinking that using the word "segregate" would ever be ok.
Because you think it's not in linear time? In each iteration of the i < end while loop if we hit array[i]=='G' then we complete in a single iteration.
If we hit array[i]=='R' we do a single swap, after that we're guaranteed to hit array[i]=='G' and finish the iteration.
If we hit array[i]=='B', then we do a swap and need to recheck, but we lowered the end variable so the total number of iterations hasn't changed.
so i made a file titled 'letters'
# cat letters | sort | tac
gib google monies pls
>sort | tac
instead of
>sort -r
RTFM
It's not the number of iterations. It's total number of checks you have to perform for every element. The time of your algorithm is element order dependent, which won't give it O(N) time.
fuck i forgot about that option
The number of checks per iteration has a constant bound so it's still O(N)
Dude. You dont know what you're talking about. Making a finite number of checks for each index isn't exceeding O(N).
fun doAThing(input : CharArray) {
val queue = Dequeue()
fun swap(i: Int, j: Int) {
val oldI = input[i]
input[i] = input[j]
input[j] = oldI
}
for(i in 0 until input.size) {
when(input[i]) {
'G', 'B' -> queue.addBack(i)
'R' -> (queue.popFront())?.also { swap(i, it) ; queue.addBack(i) }
}
}
val queue2 = Dequeue()
for(i in 0 until input.size) {
when(input[i]) {
'B' -> queue2.addBack(i)
'G' -> (queue2.popFront())?.also { swap(i, it) ; queue2.addBack(i) }
}
}
}
The number of passed needed is proportional to the input size for almost every pass based approach I came up with. The only algorithm I can think of off the top fo my head that does passes but the number of passes is independent of input set size would be radix sort (where the number of passes is relative to the size of the largest input element).
To clarify, swap based algorithms for reordering input lists.
Actually I think any swap-with-neighbor based sorting algorithm will be O(n^2).
let a = ['G', 'B', 'R', 'R', 'B', 'R', 'G'];
function correctRGB(arr){
for(let i = arr.length-1; i >= 0; i--){
if( arr[i] == 'G' )
arr.push( ...arr.splice(i,1) );
}
for(let i = arr.length-1; i >= 0; i--){
if( arr[i] == 'B' )
arr.push( ...arr.splice(i,1) );
}
console.log( arr );
}
correctRGB(a);
two passes, in-place.
Anyone for problem 2? I can keep this shit going.
Harder than you would think.
2 counters, r = 0 and g = 0. run through the array, if it hits an R, swap with element at position r, if G, swap with element at position g, then increment r or g, respectively.
It's literally one step of quicksort, with 3 ranges of numbers rather than 2.
*if G, swap with element at position r + g, my bad
only pass: count R's G's and B's
then just make an empty list and append that many R's B's and G's in that order.
How can you store N data elements with constant space?
reverse (sort ['G', 'B', 'R', 'R', 'B', 'R', 'G'])
Haskell
Fuck me O(N) space.
Yeah this what's wrong with a solution like this?
>count Rs, Gs and Bs
>from counts, you can calculate indexes of first Rs, Gs and Bs in sorted array
>read the unsorted array
>for every letter, find its index in sorted array (we can do that because we know first indexes and can just increment when we read that letter)
>swap the current letter and letter at the index in sorted array (the one from point above)
There, all linear and since permutation is just a bunch of swaps, it satisfies the swap-only requirement.
Also in-place, with O(1) memory complexity.
In no sense is it swapping and in no sense is it "in place." It's a fine solution to a narrowed down problem, but it doesn't meet the criteria of the problem as posed.
I had an idea but it didn't work so I gave up. Hard work made me quit.
are you retarded?
i agree passes matter in the practical sense but these meme leetcode interviews rely on runtime as defined by whatever oy vey big Harvard / MIT book publishers are plugging these days.
if you sincerely think that's runtime in the context of a fruitcake "Software Engineering" position you should probably reevaluate the concept of runtime
source: i'm a homo special snowflake that passed 3 of these 'interviews' and now have a comfy job and can see ladyboys march down the street every afternoon before I eat my sack lunch :o)
if the optimal solution to this problem is single pass wouldn't they ask you to reduce the pass count in the interview?
a-also are the traps cute?
Not necessarily; it's not an extremely complicated problem. It's a pretty low-level filter. Besides, growth rates are real. O(N) vs O(N^2) is the difference between your product failing in production and not. N vs N*2 is really not that big of a deal for most applications. And it's exponentially more difficult to analyze same-growth-rate optimization. Just because you do it in one pass vs 2 passes doesn't mean it's faster if the pass takes twice as long.
func main() {
test := []byte{'B','B','R','R','G','R','R'}
retarded_faggot_homework_sort(test)
fmt.Printf("%c\n", test)
}
func retarded_faggot_homework_sort(a []byte) {
m := map[byte]int{'R': 0, 'G': 1, 'B': 2}
for i := 1; i < len(a); {
if m[a[i]] < m[a[i-1]] {
a[i], a[i-1] = a[i-1], a[i]
i = 1
} else {
i++
}
}
}
t. new to programming
dont need to count shit, just keep track of front and back of the array with 2 vars and loop normally. see
This was my answer but with pointers instead of indexes.
So in other words worse.
The same.
I also skipped any leading Rs, and stopped when I reached the 'back' index in the code snippet.
I'm being "cute." Of course it will perform the same. That's why you should use something more self-describing and type-safe rather than using pointers because pointers make your dick hard.
>type safety
I like to live dangerously.
based
>cleanest, most elegant, most efficient solution thus far
based
>3 loops
cringe
>3 for loops
cringe
cringe, settling for mediocrity
if 10*x = O(n) then where do you draw the threshold? 2147483647*10000*(n) is still O(n) then?
Yes, It's inefficient as fuck but it's linear.
Here's a cleaned up version that makes the linear runtime more apparent, but the big-O runtime should be the same for both.
#!/usr/bin/env python3
import random
def swap(array, i,j):
print(i,j)
array[i], array[j] = array[j], array[i]
def rgb_sort(array):
insert=-1
start = 0
end=len(array)
while start < end:
if array[start] == 'R':
insert += 1
swap(array, insert, start)
start += 1
elif array[start] == 'B':
end -= 1
swap(array, start, end)
else:
start += 1
array = random.choices(['R', 'G', 'B'], k=100)
print (array)
rgb_sort(array)
print (array)
orginal = ['G', 'B', 'R', 'R', 'B', 'R', 'G']
for i in orginal:
if i == "R":
orginal.append(i)
orginal.pop(orginal.index(i))
for i in orginal:
if i == "G":
orginal.append(i)
orginal.pop(orginal.index(i))
for i in orginal:
if i == "B":
orginal.append(i)
orginal.pop(orginal.index(i))
for i in orginal:
print(i)
something like this? how to use code container in g?
1. COUNT 'G', 'B', 'R'
2. WRITE 'G', 'B', 'R' IN ORDER WITH COUNTED AMOUNT
>in place
Haskell is pure with no mutation
The problem explicitly requires mutation
>interview question designed to make the interviewer feel superior
typical google gotards
That’s the most straightforward implementation, but you’re required to do this with in-place swaps only.
I know there's a video of this robotchicken walking