[stonemetal]

There is this Shakespearean scholar who doesn't remember any of the works of Shakespeare. You ask him to recite a sonnet his response is they are written down he doesn't have to memorize them. Doesn't even own a print copy Google after all right? He is trying to come up with a new understanding of the works of Shakespeare.

You have to have the assumptions down cold before you can challenge them. You have to have the basics down cold before you can reshape them. Having the fundamentals down so cold that you can apply and work with them is the beginning of the path not the end.

[EliRivers]

A Shakespearean scholar who doesn't remember any of the works of Shakespeare? Does he have some kind of memory problem? He's spent years of his life examining the works of Shakespeare in detail, reading around the subject, probably watching play after play, travelling to see new interpretations being put on, and he can't quote me a single sonnet? Either he's incompetent, or he has some kind of memory problem.

Now extend to algorithms. I wouldn't hire a programmer like this Shakespearean scholar.

[eli_gottlieb]

The analogy would be perfect if "working programmer" and "algorithms researcher" were the same thing.

[eli_gottlieb]

Ok, you make a certain point, and I'm going to correct myself.

Google does not interview based on the material from Algorithms 1 & 2 in university. Merely having the fundamentals taught in undergrad down-pat will not actually help much on a Google interview.

Google interviews based on a database of Interview Questions, which are largely unique to the BigCo recruiting process. They're not real problems I've ever seen anyone actually have to solve; they're basically checks to see if you have studied the subject of BigCo coding interviews in itself.

To repeat my example from below: how do you find all the identical anagrams of words in a text, given the text? This is not a problem taught in Algorithms class, and in fact, there are several different ways to apply Algorithms 1&2 knowledge to the problem. Only one of those (tokenize and sort the tokens in lexical ordering to get a "canonical" form of the string, then build your own key-value map from canonical strings to bags of words) will get you the job, and in fact it's the one that involves pretending you can't build sets of characters and use them as keys to a hash table. In fact, if you could hash character-sets, it's much cheaper to do so rather than employ a counting sort followed by a key-value store.

Actually, as I remember, we didn't (and don't) do much with key-value data structures in Algorithms class at all, not as I took it, and not as I've TA'd it. The question is used precisely because it tests your knowledge of How to Play the Interview Game rather than your fundamental computing knowledge.

[DannyBee]

Err, plenty of answers would get you the job besides sorting, including order insensitive hash functions and tables, neat automata based solutions, etc.

FWIW: I've hired people who even never got an "optimal" answer, but had brilliant ways of thinking about it that didn't turn out to be better/faster.

In any case, they deliberately ask questions that require applying knowledge, and designing an algorithm, rather than memorizing the way to reverse a circular linked list or whatever. So they are questions designed to test whether you can solve problems you haven't seen before by applying basic computer science knowledge.

I get/can afford to spend 45 minutes with a candidate. If you've got a better way to understand whether a candidate can apply computer science knowledge, I'd love to hear it.

Most problems being worked on for real would take at least 20-30 minutes to introduce (probably a lot longer to explain constraints, etc) Nobody is going to have interesting insights in fifteen minutes, and engineers are too busy to spend hours per candidate.

If you can't see how the anagrams question tests basic data structure and algorithms knowledge, I don't know what to tell you.

[eli_gottlieb]

Err, plenty of answers would get you the job besides sorting, including order insensitive hash functions and tables, neat automata based solutions, etc.

I actually gave hashing/hash-table of a small character-bag of my own making as the first answer. The interviewer then told me to solve the problem "without any [standard-library] data-structures". I had to question that, and was told I had to come up with everything myself, as if writing my own standard library in C. The interviewer was then satisfied when I gave the sorting answer, and I did get the positive call-back.

It was a matter of giving him what he wanted, not necessarily just solving the problem.

[DannyBee]

Your interviewer was an idiot. Again, if this was at google, please let me know privately who it was, and i'll take care of it.

[andreasvc]

You seem to make the assumption that an interview question should be representative of the work you would do on the job. You could also see such questions as measuring a variable of interest to the interviewers; in this case that would be creative problem solving. The fact that it's neither something you did in algorithms class nor something you will do on the job is on purpose, it forces you to come up with something new.