Do you really need to be able to "invert a binary tree" to move a button in gmail to an even less convenient ___location? It's not even that you need to know all those things to work at many positions in FANGs. It's about making sure that someone who can do that does not, God forbid, go somewhere else and does something actually useful for the humanity.
I've never been asked to "invert a binary tree" while interviewing at Google, or anything of the sort; later, as an interviewer myself, these kind of questions were forbidden. Everyone knows they're stupid, and they've been forbidden for a long time. I'm starting to believe this is either a persistent myth, or something the other companies, but not Google, does.
In my experience, all the questions I was asked were fair game - all of them were about implementing a toy version of a real-life feature (simplified for the time constraints of the interview). All of them felt like "yeah, a competent engineer should be able to do this".
If anything, a myth that persistent must have something behind it. (I've zero interest in FAANGs so I would not know if they do or do not really ask it).
There's no question that a competent, well-rounded programmer should know about these algorithms' existence and when to use them. But whether testing if said programmer can implement them from scratch during an interview... that's a million dollar question whether these questions provide optimal outcomes. Anecdotally, yeah, sure, I did these things. In S/370 assembler at that. But did I use 90% of them since then(and that was when Apple was the only FAANG in existence)? No. So I think the feeling is that this kind of interview tests not so much how good, or experienced, or what not, you are at programming but rather how desperate you are to work at that kind of company to spend a good amount of time memorizing algos and data structures you've learned and forgotten years ago.
Sure, but there's a huge difficulty range between Fizzbuzz and that "come up with a dynamic programming algorithm on the spot" crap that Google and friends like to do. (And that range includes problems that are actually relevant rather than algorithms class homework.)
