The OP has written some great apps, sure, but there is a huge difference between writing a package manager for Mac (among other Mac/iOS apps and utilities) and writing incredibly complex, highly performant algorithms for say search indexing, machine learning, ai, etc...
In that context, knowing CompSci basics like Binary Trees (usually taught to pre-major CompSci students) has a lot of relevance. It's clear Google was looking for a Computer Scientist here, not just another developer.
I am also put off by the extreme display of non-professionalism here. It's like the OP took this personally as an insult. "I've written popular things, how dare you not hire me if I want to work for you!". That's not a professional I'd like to work on a team with. Rather, that's a throw-back to the "Rockstar" programmer that nobody wants to work with.
This boils down to a person who was personally offended a company did not hire them at a drop of a hat, as-if he was "blessing" Google with his presence.
I'd say, Google (and other companies) are better off without this type of ego.
They made the proper choice to weed this individual out.