#Starting thread for my google r2

1 messages · Page 1 of 1 (latest)

gentle quiver
#

for google r2 i got a question on checking if a number is prime and then doing some calls on that

i completely blanked on sieve of eratosthenes and mixed it up with euclidean algo 💀 i kept saying i know there’s some efficient way to generate primes (like sieve of something) but couldn’t remember the name, so i just coded brute force n²

finished part 1, and the follow up was basically just wrapping it in a loop

then interviewer said there was no more follow up (which was cap, i later found online there was one for huge input sizes). so i tried to come up with a better approach myself, and eventually he told me sieve of eratosthenes + how it works. i coded it, had a small bug, he pointed it out, and we wrapped up

idk if i’m cooked bc the whole point was to use sieve for efficiency. like i knew prime gen was the bottleneck and kept saying that, just couldn’t remember the actual algo 😭

#

also, the dfs() algo i made did have optimal runtime of o(N) where n is num of digits but i was at first string casting and then splicing off last digit so on runtime analysis i realized my error and told him it was n^2

then i blanked on how to remove only the last digit and he was like can't we use division and then i blanked for a few seconds and them realized

#

so not sure if this is LH or LNH

molten quarry
#

uhh you can get prime check down to sqrt(n) even just in the brute force loop method

frigid flume
#

are you done with both rounds?

molten quarry
#

is this ft or intern?

frigid flume
molten quarry
#

imma say outlook not good
but if you had an understanding interviewer and you really did just blank out (hpns), you might scrape by

gentle quiver
gentle quiver
# molten quarry ??? you forgot modulo 10 to get the last digit?

Kinda yeah but we were ignoring the last digit so we wanted to just splice off that last digit so it’s divided by 10 and I was originally using a string cast to do it then I realize that way that’s the wrong long run time so then I was blanking on how to do it instantly and you said what if we use divided by 10

molten quarry
#

splice it off is just floor div then

gentle quiver
#

I just panicked the whole time because I couldn’t figure out the sea method and I was panicking because I had no idea how to do it. I was still in the kitchen sink at the wall trying to remember the algorithm.

#

You know, I caught that when I analyze the runtime manually

#

I think my main kind of issues was just prime number generation cause I couldn’t do that optimally

molten quarry
gentle quiver
#

Also, there was a follow up that I had for the loop apparently he didn’t tell me the constraint and I didn’t ask about it, but it would’ve made my four loop inefficient to do which meant that I would have to come with the new algorithm because it becomes a backtracking problem where you need to generate them

gentle quiver
gentle quiver
frigid flume
gentle quiver
#

300 something

frigid flume
#

damn

tidal nacelle
#

its unreasonable they expected u to know sieve off rip

#

so you are probably good if you were able to come up with a solution on your own and talk through optimizations

molten quarry
#

Is this a USA curriculum thing?
Cuz we get taught sieve in middle school

gentle quiver
#

I was taught see in my discreet math class and maybe my intro DSA class so I knew it existed and I have taken a competitive programming course at my school however, I just forgot the actual implementation cause I’ve never had to code it up

tulip ivy
#

@gentle quiver did you get any update after r2?

gentle quiver
tulip ivy
gentle quiver
#

TP