Comment by gefh

You may well be asked how a distributed sort would work in principle, and be asked to code a small part of it. Any reasonable answer that shows you can think on your feet would be evidence in favor of hiring. It sounds like you didn't get hired, and I'm sorry about that. Interviewers' preferences are of course diverse, but for at least the last 5 years, probably 10, Google interviews favor practical solutions to problems we face every day. Some of those are theoretical CS, many are not.