My toughest job-interview question ever

http://asserttrue.blogspot.com/2009/05/one-of-toughest-job-interview-questions.html

by techdog • 17 years ago

45 78 17 years ago

asserttrue.blogspot.com

ulf• 17 years ago

Why would he want to implement a frequency-sorted list as a hashtable!?

derefr4• 17 years ago

The final list wasn't a hashtable—he said he "harvested" the values from the hashtable to construct the final list. The hashtable was for counting values: every time you read a word from the corpus you're going to increment a value on an almost-random, complex key. Sounds like a job for a hashtable to me.

spitfire• 17 years ago

Wow. Arrogance. He wouldn't have been hired with me.

I particularly like the jab at the interviewer for not having instant recall of every single CS algorithm. I keep TAOCP on my desk, and /because/ I don't know every single algorithm.

derefr4• 17 years ago

He said the interviewer had never heard of cuckoo hashing. That's a slightly different matter than a "not having instant recall", especially for someone asking questions about how to implement hashtables in the first place (they should have looked at the relevant reference before going in to do the interview, as they were obviously following a very fixed format, instead of letting the discussion range.)

vicaya• 17 years ago

Cuckoo hashing is a relatively new but underperforming hashing scheme due to the fact it's not cache friendly for modern processors: "despite its constant worst-case look-up cost, the bucketized cuckoo hash table was demonstrated to be the slowest hash table, far inferior to both the chained and array hash tables."

No, they're not asking for details of hash table implementation. The main goal is to see if you can scale the algorithm, for which they're the real experts. The hash table discussion is a mere diversion. The "expected" progression of the particular discussion is: 1. hash table implementation (simplest map container) when you have enough RAM to see if the candidate gets cs basics. 2. sort | uniq -c when you have enough disks on a single node to see if the candidate has experience with non-trivial amount of data (larger than RAM.) and understanding of modern disk performance characteristics (random vs sequential I/O) 3. map-reduce on multiple nodes for the entire internet; see if the candiate has experience and understandings with distributed computing. So the author didn't make very far. His attitude and mindset were also getting in the way of interviewers' steering the interview. It's a classic case of impedance mismatch in interviews.

visitor4rmindia• 17 years ago

He appears to be good at algorithms, has a feel for the actual space and time requirements, is able to think under pressure, and has a sense of humour.

I'd hire him in a heartbeat.

ErrantX14• 17 years ago

he fell into every trap laid out for him... (all of them classic interview traps). That would at the very least worry me...

But it depends on the job :)

badger73• 17 years ago

One definition of arrogance is "making undue claims in an overbearing manner". You know, like turning "never having heard of" into "not having instant recall of every single CS algorithm".

wglb• 17 years ago

Attitude is good, but it seems misdirected. For example, are you really sure that the 10,000 frequency list is going to be all that different day to day?

While I like to hire people smarter than I am, I rather like to draw that conclusion myself, rather than have somebody try to wrestle me to the ground to prove it.

huhtenberg• 17 years ago

The attitude was actually quite bad considering this was an interview and not a lazy chat between two colleagues. This guy plainly failed to demonstrate that he can understand the context of the question, which was not an offer to ramble about the question not making much practical sense.

Tichy3• 17 years ago

I don't think I would have been so patient as an interviewer. He tried very hard to evade the questions several times. I would expect "fun" meetings in the future, dragging on for hours.

derefr4• 17 years ago

He didn't evade the question; he asked the question that actually needed to be asked. If I ask you how to code a performant 3D shooter in PHP, you don't explain it, you stop me, possibly bitchslap me, and tell me that that's not what I should be doing, or, more kindly, ask "why do you think you should be coding it in PHP?"

I think I might inject this kind of thing into an interview just to weed out the people unwilling to stand up to insanity. If you can't tell me when I'm going too far down the wrong path, how can I be sure you'll know if you're doing the same thing?

ErrantX14• 17 years ago

That's not a relative example though: looking at the original question the interviewer wanted to see how he would approach the problem of analysing and sorting the words.

At the end of the day he petulantly (his words) stuck to a point that could have been made in a simple sentence (well, assuming we agree there is no way this could work in the real world because of the fluidity of language and the poor behaviour of web crwlers then I would.....). If the interviewer is looking for a discussion on that he will pick up and ask for more. If not he will let it pass (and probably note that your recognised the issue).

In an interview you must dangle relevant information in front of the interviewer and wait for him to pounce on things he wants more information on :)

Also: NEVER assume a concept the interviewer has "never heard" of IS something he/she has never heard of. That is a simple mistake to fall into.

Tichy3• 17 years ago

I see your point, but I don't think the questions were particularly insane.

ilitirit• 17 years ago

I agree, but it was partly the interviewer's fault. He should have just said "assume static pages" and/or "assume everyone speaks the same dialect of english and uses the same vocabulary". In cases like these interviewer should always try to eliminate fluffy answers as far as possible. How else would an interviewee know what his intent is? Perhaps the interviewer wants him to critically assess the question? On the other hand, I always make a habit of asking things like "is it safe to assume such and such?". Then I don't have to go into detail unless they ask "Why?".

That said, it was quite obvious that guy was trying to avoid the question. That wouldn't have sat well with me.

Tichy3• 17 years ago

I would have expected the candidate to bring up something like "OK, let's assume the work of Shakespeare or another fixed body of text" if he was worried about that issue. Instead he said "that question does not make sense", which would have annoyed me.

mkelly• 17 years ago

The best interview question I've ever had or thought about was also of this style: one concise question that requires knowledge of many different domains, and spawns a conversation that lasts the whole interview. The interviewer also pursued the same strategy of pulling actual numbers (for storage requirements) out of me. It was a tremendously enjoyable and satisfying interview (as far as interviews go). Also given by a well-known search company, interestingly enough.

I didn't give nearly as much pushback as the author, though, since I assumed that wasn't the point.

yason2• 17 years ago

While the interviewer probably wanted a typical "programming answer", I wonder how large a dataset you could do by simply using the command line. That's programming, too.

Just use sort and uniq.

Or if it's slow, sort in parallel, then merge into one stream, and extract the frequencies.

bayleo• 17 years ago

Given the wording of the question this is the route I would have taken; give him the engineering solution, not the comp sci solution. I guess this question has a certain merit for weeding out theorists from pragmatists.

torr• 17 years ago

Along similar lines, as I was reading along, I was saying to myself something like, `my %word_count; for (@words) { ++$word_count{$_} }`...

mixmax• 17 years ago

Interesting that a candidate for a post as technical writer needs to be grilled so hard on the technical stuff. IMO a good technical writer needs to be much better at psychology, explaining and people-skills than the technical side of it.

Maybe this is why most technical documentation sucks, particyularly helppages oriented towards end-users.

ScottWhigham• 17 years ago

I also wondered why someone who had such a knowledge of algorithms would be interviewing for a tech writer position. Just doesn't seem right...

maw• 17 years ago

Read the documentation of Java's Collection framework sometime; it's gloriously well done. Somebody had to write it.

Both Yahoo and Google offer services interesting to programmers; presumably they want documentation of a similar quality.

cperciva2• 17 years ago

The author is an idiot. He suggests using an excessively slow algorithm while using a ridiculously large amount of RAM (he would do better to use a tree structure, sorting-and-aggregating, or at very least a more appropriately sized hash table). I was willing to accept this as merely being a sign that he was a one-trick pony -- someone who knew one data structure and tried to apply it everywhere -- but he completely lost me when I reached this point:

We're hashing a million words into a table that can hold four billion. The load factor on the table is negligible. If we're getting collisions it means we need a better hash algorithm.

There is absolutely no excuse for using a hash table without understanding the birthday paradox. If you hash a million words to four billion values, you WILL get hash collisions -- a few hundred of them.

The author is right about one thing, though; this is a good interview question. It identified him as someone who picked a poor algorithm yet didn't even understand that algorithm properly, marking him -- in my opinion at least -- as an immediate no-hire.

brk• 17 years ago

He was interviewing for a tech-writer position.

I'm somewhat amazed that he could answer it even to the extent he did. Most tech writers I've worked with do not have the (apparent) level of technical knowledge this guy has.

Retric• 17 years ago

He prattled on at lenght when he had little real understanding of the toppic at hand. He ignored cleaning up the data and assumed you needed a complex hash for words when you could just the digtits of the word for the same thing.

(((A * 27) + B) * 27)+C) then a datastructure for count and the next Hash table if needed. Use this recursivly and you can handel just about any word and get there with (Length/3) looks at main memory. And you can still alocate all that memory in a few large chunks so that's still fast.

Then optomize for speed or memory as need. (If you don't mind sacrificing space you use 32bits per letter and then bit shift etc.)

biohacker42• 17 years ago

Yeah that's what struck me about this, who drills tech writers on hash algorithm? There's tough interview questions, and there's stuff that's hardly relevant.

The grand parent is right, this is a horrible programming solution but the author is not a programmer!

dagobart• 17 years ago

because of that a shortcut answer would have been to delegate the issue to the CS department as sorting words is not a task for a tech writer. Nice that he identified the question as being off-topic. Poor that he didn't dismiss it because of that.

ntoshev• 17 years ago

What is the tree (trie?) structure and sorting-and-aggregating that you mean?

Assuming the corpus is not too big, the solution can be thrown together in Python in a few minutes.

    import re, collections

    def words(text): return re.findall('[a-z]+', text.lower()) 

    def train(features):
        model = collections.defaultdict(lambda: 1)
        for f in features:
            model[f] += 1
        return model

    NWORDS = train(words(file('corpus.txt').read()))

    import heapq, operator
    freq_words = heapq.nlargest(10000, NWORDS.iteritems(), key=operator.itemgetter(1))

This code processes 12Mb of text in less than 5 seconds on my laptop.

cperciva2• 17 years ago

What is the tree (trie?) structure and sorting-and-aggregating that you mean?

The tree structure: Put all the unique words into a tree. You could use a trie, but considering how dense the tree is likely to end up, a traditional split-26-ways-on-each-byte tree would probably work just as well.

The sorting-and-aggregating option: Run a traditional mergesort, but attach counters (initialized to 1) to each word; and every time you find yourself comparing two identical words, replace them by a single record with the sum of the counters.

TheSOB88• 17 years ago

What's up with that weird hash function? Seems to me you could just convert the string into its base 26 representation.

Edit: I would actually like to know if/why the method used is more useful than the one I gave. I'm not just trying to be arrogant.

amalcon• 17 years ago

First, the function he gave wasn't particularly weird; it's a pretty standard thing. Second, the value resultant from said function is independent of the length of the word, which is exactly the sort of thing you want with a hash function.

If you have a hash space large enough to hold the longest English word converted to base 26, then you might still need to be concerned with clustering properties. It's considered undesirable to have large stretches within the hash space with no associated key; my understanding is that this somehow impairs the distribution from the modulus step in most hashtable implementations.

alextp• 17 years ago

The problem with hashing is that you do not just want a number, but a number that is between 0 and the size of your table and that, over a reasonable distribution of objects, gives numbers that are uniformely distributed in that interval. You also want to avoid some obvious collisions (say, if you just add the letters of a word then all anagrams will hash into the same place, which is bad).

Converting a word into base 26 will give you a huge number. Over six or seven characters and your hash does not fit into a 32-bit integer, and over 13 characters it will not fit into a 64-bit word.

So he chooses to multiply by number that is prime in relation to the table size because that would definitely avoid cycles (say, if you've got a table of size 16 and double the number each time there are many positions into which words with that prefix will never hash, which can be a very bad idea).

brown92• 17 years ago

Am I the only one that read this and was left wondering what the heck was up with the interviewer, not the candidate?

Why drill a candidate for a technical writer position on hash functions and memory needs and speed and all that?

It seems to me like whichever company this was (I'm guessing Google) that the interviewer only knows how to ask one type of question, almost as if he/she was reading from a script.

edw519• 17 years ago

You weren't the only one.

People tend to forget that every interview is 2-way, not just 1-way.

If I was this candidate, I would have rejected this company and (possibly) sent them a nice form letter later that week.

known• 17 years ago

    Interview != Quiz

Most interviewers are NOT aware of this.

brown92• 17 years ago

Actually I would say that some/most interviewers believe that this is the purpose, and like to use the interview as a chance to show how smart they think they are

(at least the stereotypical "interview" at the stereotypical tech company. Then again, I think Wall Street/financial firms probably do the same. exact. thing.)

pookleblinky• 17 years ago

Who can forget this: http://exold.com/article/stupid-interview-questions

Either you love it and want to hire the guy in a moment, or you think he's an unbearable smartass.

trevelyan• 17 years ago

I think the focus on algorithms and data storage is totally misguided. You don't need to count every single word on the Internet. This is a question about statistical inference:

(1) Use Zipf's law (or a more suitable distribution) to identify how many times we expect the 10,000th word to occur in a random distribution of documents. That gives us the maximum interval at which the 10,000th word will repeat itself at any level of statistical confidence.

(2) Don't count every word. Only track the top 10,000 words plus a tail of whatever size is necessary to capture this maximum interval. With Zipf's law this means less than 20,000 words. The exact number can be calculated easily enough.

(3) Store words in a data structure that provides fast access by alphabetical search (tree) and also by frequency of occurrence (list). Bump words up the list as we run into them. When you run into a word that isn't in your tree, grab the entry at the bottom of the frequency list and re-insert it as your new word by repositioning. There is no need to traverse much data

(4) Lower frequency content will naturally drop off the list. Higher frequency content will naturally move up. And we've structured our program so that we can make statistical inferences about the words that are left....

(5) Remember to normalize incoming data with a Porter-Stemmer algorithm or something. Lots of small details like that, but it is really just icing on the cake.

Result? You get a statistically significant test you can run multiple times at whatever level of accuracy you desire. The software doesn't require huge computational muscle power or massive amounts of memory, since we throw out the long tail of statistically irrelevant content on an ongoing basis. That coupled with our elegant data structure - we're mostly swapping pointers - keeps the software small and fast.

Is there a better approach?

menloparkbum• 17 years ago

Although the author is interviewing to be a tech writer, and this question may or may not be relevant to the job, it sounds like he knows a lot about computer science and even why this question would be asked at an interview. It's a typical programming interview question and is asked so the interviewer learns how you solve problems. I got the feeling the interviewee knew all this and decided to be a pain in the ass about answering it, anyway.

asmdsr• 17 years ago

"What will you do in the event of hash collisions?" the professor asked.

The interviewer was priming for this particular answer: Keep the buckets in a linked list. Each time you increment a bucket, move it to the front of the list. When you're counting frequencies, this approach will mean that the most frequently occurring keys will be closer to the front of the list.

I know this because I was asked a similar question in an interview with a certain well-known PC software company. I didn't know the answer either, but still got an offer.

My toughest job-interview question ever

Related Stories