Here's the problem I have with interviewing, speaking as someone already at a big 4 company and has gone through this process already. I know exactly what types of things I need to prep for and even as someone who's competed in competitions like ICPC and TopCoder, I'm always worried that I'll get the type of interviewer who will just ask obscure questions and not go to the level of depth you mentioned when it comes to working with the interviewer to assess their problem solving skills vs just checking to see if they know the solution to some trick question - the kind that most people not knowing the solution beforehand would almost never be able to figure out within 30-60 minutes.

I'm planning on interviewing with Google in a few months just because of all the great things I've heard about their infrastructure and engineering culture, but due to these concerns I've budgeted to use my current vacation time just to get back into prepping the way I did when training for ICPC just so that I'll have confidence knowing that most interviewers probably have never studied algorithms at that level and that I'll have more confidence in not being potentially tripped up by these types of interviewers.

Most of my friends, even those at Google, have tried to convince me that this plan is overkill but I just can't get myself to leave the fate of my future into the hands of some random interviewer and then regret not doing this level of preparation if I get rejected...