Okay, so you admit he claims it did happen, but you say it didn't without supporting that claim at all. Do you have a source we can verify?
I'm not sure if there's anything public (and what I am even allowed to say.)
See https://www.quora.com/Whats-the-logic-behind-Google-rejectin... where he (at least partially) admits that he was bullshitting:
> I want to defend Google, for one I wasn't even inverting a binary tree, I wasn’t very clear what a binary tree was.
See also https://www.reddit.com/r/google/comments/7l5ibp/max_howell_h... for a discussion.
It's kind of silly. Most programmers out of school have a lot to learn about building product and actually getting a big project done - which they are supposed to learn on the job. At a place like Google. Somebody who knows this part already could probably spend some time on the job learning about data structures.
It's like these conventionally-taught programmers think they get to look down on somebody who actually built something cuz he's self-taught. (As a conventionally-taught programmer who is very comfortable with data structures I find that attitude aloof at best)
I'm also the guy that found low hanging fruit in a huge codebase to replace things like frequent linear array lookups with hash table lookups for 10x+ speed improvements in the build process. This is IMO precisely the type of capability that "Oh, that's O(n^2), surely we can do better. Is there any way to do this in O(1)?" is designed to tease out in the interview process. I did it! In a build process effecting 1000+ engineers, used to build for millions of shipped units! But talking about this in an interview makes eyes gloss over as we prepare to move on to sort algorithm trivia, how would I design search, or doubly linked list implementations.
Often people are interested in something like the 99.9999%ile case. And, of course, you can design hash tables with better worst case behaviour.
It's almost trivial to get a hash table with O(log n) worst case access: when you have a collision, just resolve it with a tree instead of a linked list.
With some more fancy math, you can also get O(1) amortized worst case behaviour with arbitrarily high probability that doesn't depend on your input data.
To be honest, drilling down on all the stuff they teach you in first year helps you more in getting a job at Google than having lots of practical experience.
I'm inclined to believe that this is a problem with Google. But I am not sure you should trust my opinion: I am sure Google spent much more time and money and figuring out the right approach here than I ever laid my hands on in my whole life.
See also https://sockpuppet.org/blog/2015/03/06/the-hiring-post/
My opinion of the guy just dropped hard.
> But ultimately, should Google have hired me? Yes, absolutely yes. I am often a dick, I am often difficult, I often don’t know computer science, but. BUT. I make really good things, maybe they aren't perfect, but people really like them. Surely, surely Google could have used that.
To me at least, being a dick is a negative that outweighs making good things, especially for a large organization. Maybe google made the right call.
But I could be remembering wrong.