My toughest job-interview question ever
asserttrue.blogspot.com
asserttrue.blogspot.com
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.
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.
(((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.)
The grand parent is right, this is a horrible programming solution but the author is not a programmer!
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))
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.
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.
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.
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.
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.
I'd hire him in a heartbeat.
But it depends on the job :)
- assuming importance (his tone suggests he thinks he knew more than the interviewer. I imagine that might have come across in the interview)
- assuming ingorance (if it seems amazing the interviewer is clueless on something then it probably isnt true. Adjust appropriately.)
- chasing the wrong issue (if an interviewer needs to draw an answer out - even in a fluid way like that - it will be a black mark on your notes)
- assuming irrelevance (his opening remarks suggest he though the question was not relevant to the interview he was having, which suggests he possibly did not treat it with the same gravity. Everything is relevant - the more off the wall the question the more important your answer is).
There are more but those were the key points I picked up: not being there and only having his side of that short portion I cant say 100% he fell into every one. But it definitely looks that way :)
This is based on similar traps I set up for our interviewee's.
Anecdotally, when a one-hour interview turns into a three-hour discussion of a side point, it is a really good sign. If the interviewer isn't into it, give up -- but people who can bounce ideas off of each other tend to come up with more ideas.
Personally I would have walked out if I got a negative vibe from the interviewer during this. Questions like this are deliberately obnoxious bullcrap pulled by recruiters and interviewers who don't understand what they're actually after in a candidate.
Everything that you want from a good software engineer (requirement refinement, minimal-effort-maximum-payout planning, awareness of a large variety of domains relevant to your company's business) was expressed by this person's response. You want these things in a candidate because they are the hardest things to find in a good candidate. But the interviewer didn't actually want real-world skills and a real problem solution, they wanted some arbitrary, bullcrap pseudocode up on the whiteboard. This kind of bullcrap pseudocode doesn't actually tell you if the person can or can't code, so it's utterly pointless.
I've walked out of interviews and refused job offers for less egregious examples of this kind of nonsense. It doesn't bode well for the company when they're so scatterbrained and insecure that they can't handle someone who actually takes your question seriously.
His blog post seems to suggest he barely spent much thought on the solution to the actual problem (which we cant deny is important).
The data-set is not real world, that is obvious to everyone, but the solution IS.
It was an interview. You're being unreasonable to put someone under an already high-stress situation and then saying, "Now we're going to conduct an extremely difficult experiment where you try to come up with the solution to a difficult problem in one fell swoop without any of the usual access to reference and the opinions of your peers."
It is bullshit, plain an simple. A bizarre artifact of a world where people have extreme difficulty evaluating software engineering skills. It bears no resemblance to how people in the real world write code or engineer solutions.
If you wanted real world examples why not put a pre-requisite to the interview to bring in working code that does what something relevant, and then discuss it in the interview? That's a far more realistic scenario with far more useful data than this little play-acting show that you're describing.
When I operate as the interviewer, I look for responses like the one the blogger gave at the beginning, where they start to really analyze the problem domain. People like this save millions of dollars in software engineering costs because they can look at the scope of a request and start to refine it (or outright reject it if it is unreasonable and they can cogently explain why it is so). To say these qualities are a "turn off" blows my mind. This kind of attitude is nearly as bad as the attitudes expressed in the reviled modern-google-interview, and competent software engineers who are not desperate for a job would do well to refuse to tolerate it.
After all, an interview is as much for the interviewee as it is for the interviewer. Most of the time, getting to an interview like this means that the company in question thinks you might be a good hire, and they're hiring to fill a void in their ranks. The interviewee is far from powerless.
The problem IS real world though: I can think of several situations in our own company where a programmer would have to manipulate a set of data, find common occurences and order them. Of course each specific problem is complicated by the data and the data source but the fundamental problem stays the same: and so the question IS valid.
The input data doesnt matter (though briefly recognising it is flawed instils confidence).
In terms of your other point about how people write code.. im not 100% sure I agree. As an engineer I break a problem down into I/O machines. Where the input comes from is immaterial so long as it is in a form that is usable. The important consideration is engineering the output.
Your right: he did see the problem with the suggested data set and that is the kind of thing that saves companies money. BUT he hammered that like it was the only issue and (by his own admission) barely considered the actual practical engineering problem. To me that would tell me he is a fairly ok programmer and is bright enough to spot problems - but he is no engineer and I wouldnt hire him :) (that said it is only a small subset of the interview and based on other stuff I have read from the guy I suspect I would find him suitable to hire: he just screwed up the one question)
Take your abuse elsewhere: I am happy to debate my points but at least bring something constructive.
-Rick
"It's" is a contraction of "it is." You mean "its" -- the possessive form.
Another black eye for you; another feather in my cap!
(Seriously, though. You're demanding tolerance of your cognitive differences -- which is perfectly reasonable -- but also asserting that engineers should approach problems by breaking it into finite automata, GIGO be damned. This strikes me as odd.)
To defend my statement: I explained how I, as an engineer, break a problem down. Pretty much every other engineer I know uses much the same approach (and when I hire I look for the same skill because it fits into our team) - but it's, of course, not the only way. Each to his own.
Seriously: if your going to call out my english at least read and understand what is written ;)
Nit picking over language isn't making a point for you: it'simply suggesting you dont have a decent counter argument. Someone else posted a convincing one - you should give it a read :)
Your a "newish" commentor so I guess you havent learned the culture here :) I made the same mistake once. It's cool no harm done.
I am a software engineer and I do not work the way you are describing. I take the actual problem to be solved very seriously and try and solve that in the most minimal way possible while leveraging and reusing existing code. I suppose I am not hired because I work differently. I've fallen into your trap of not designing complex systems in a stressful situation the way you expect me to.
So in revenge all my interviews now require a properly spelled and gramatically correct 5k word essay. It's just as arbitrary as what you've proposed. It is my "trap", which is your code word for "unreasonable and inscrutable expectation."
EDIT: as I mentioned elsewhere people do do things in other ways (though you seem to be suggesting my approach might not take a problem seriously??) and there ain't anything wrong with that. At no point did I say there was :)
Whiteboards have spellcheck?
aka touche.
First, you're chasing an irrelevant point. My grammatical nitpicking has nothing to do with the topic at hand. I'm writing down "easily distracted by internet arguments."
Second, you're assuming importance. By bringing my "newish"-ness into play you're effectively asserting that hanging out in Hacker News makes you better at arguing your points, which obviously isn't true regardless of how high your karma is. I'm writing down "doesn't actually look up accounts' creation dates before tossing around seniority."
Third, you're assuming ignorance. I have no interest in talking about interviewing policies with you. I am trolling. You have been trolled. Do not feed the troll. I'm writing down "has been trolled."
Fourth, you're chasing the wrong issue. Actually, this is the same as the first trap. I'm not sure why you decided to list it as a separate bullet point. But hey! Traps! Bullet points! I'm writing down "overly fond of bullet points."
Fifth and finally, you're assuming irrelevance. Not in the "making an assumption about" sense of the word, but in the "acquiring the attributes of" sense. I'm writing down "GIGO."
Black eyes! Feathers in caps! Traps!
Wait no i cant be bothered: you've given up the charade so will I.
I know your trolling, it's amusing to feed trolls because (especially round here) it outs them from what they are for very little burn.
The ideal candidate for this job knows when -- as Kenny Rogers put it -- to "hold 'em" and when to "fold 'em." By not simply walking away from a fruitless discussion with a self-admitted troll, you've shown yourself to place pride above the minimax of effort in the pursuit of solution. This single-minded devotion to a stupid, stupid task is not a quality we look for in our engineers.
Instead of readjusting strategies and avoiding the sunken cost fallacy, you chose the classic 6th grade technique of pretending you knew all along and the decidedly modern approach of post-facto appointing yourself as head of Hacker News' Troll-Baiting Brigade (official motto: "We Get Made Fun Of So You Don't Have To," official song: "Nearer To Thee, PG"). When faced with a losing bet, you doubled up.
You can keep the dry erase marker you're holding, but I'm going to have to ask security to see you out.
Hard to find quality candidates these days...
Absolutely untrue. In the business world, software developers primary reason for existence is to improve the bottom line. Sure, writing good code for existing business processes is the primary route. But due to our nature of not being encased in the traditions of the departments we are creating applications for, and having knowledge and workings with various parts of the organization as a whole, we get to see a lot more of the big picture in minuet detail than almost anyone else in the company.
Numerous times have I been in situations where no one stopped to break down the problem before jumping to a solution. I've seen people so fixated on a solution that they cost the company hundreds of thousands of dollars for a problem that upon minimal scrutiny became apparent that it did not apply to our organization (hurray for tax codes.)
Users come to us describing a solution to the problem that they are experiencing. We can take their word for it, and hop to on making the solution. But it also presents an opportune moment to get people to wait a second, to look at the business process, and possibly to solve the problem through a minimal change in process as opposed to the creation of a whole new software application.
Pushing the issue in such a way takes a fair bit of self confidence and even a touch of ego. Maybe the original poster was a bit over zealous in his questioning of the problem, maybe he could have questioned the problem in a more constructive way. But the fact that he was questioning the problem, IMO, is the sign of a good developer.
It is a fine line though. And putting up too much resistance or negativity will quickly get your resume round filed.
-Rick
The last 2 paragraphs of your reply I would agree with :)
But by giving the problem a context, the interviewer is asking for a much larger answer. In the case of this question, dealing with the most common words in the English language, the consumption of words is likely going to be significantly more difficult and critical to the accuracy of the final product than the sorting and hashing algorithms.
If the goal of the question was to determine the applicants knowledge of sorting and hashing, then the question should have been stripped of context and presented as a purely academic "sort 1 million words by usage." question.
On the other hand, if the goal of the question was to determine how the application approaches a problem, then his act of questioning the problem was a success, although the etiquette of his approach may have been a failure.
-Rick
Especially if it's for a candidate for a tech writer position. In that case, I'd say that the interviewer was the idiot here.
As an interviewer meeting potential candidates YOU are representing your company. If you're acting false and laying little traps etc. and your candidate detects this, you could lose a very smart and productive person simply because acting falsely is a natural turnoff.
On the other side, if the candidate is answering questions in some sort of rehearsed way it'll be a turnoff for the interviewer.
Good interviews are no different than meeting people. As a candidate, be yourself, don't worry about silly traps. Your goal is to show them who you are and find out who they are to see if there's a fit. If you've already decided you want the job before meeting with their representatives then you're potentially making a bad decision and wasting your own and other people's time. If you're egotistical and feel a need to point out that a question is useless, then by all means do so! That way they know what they're getting and can make an informed decision about whether or not they can deal with that. You may want to work on the ego a bit in general, but not specifically for an interview... that would be fake.
Don't try to con your way into a job because there's a very god chance you'll be unhappy if you get it.
Don't be fake and cagey with candidates because ultimately you could scare away some really excellent employees. Intuition is important as an interviewer so you can detect when someone's being fake with you without being a weirdo yourself. Ask questions you actually want answers to instead of trap / fake questions.
The whole fake / fake thing just perpetuates itself and makes it next to impossible to find good fits. It should just be common sense without all this complicated trap nonsense.
But when answering a question there are, surely, natural traps an interviewee inevitably has to avoid. And not doing so is a potential black mark the interviewer has to watch out for.
That said your argument is fair - and I'd probably agree. But I di think laying intellectual traps can be appropriate. It really depends on your candidate and the interview: if you go into an interview (either as the interviewer or the interviewee) with any form of fixed agenda then, yes, things are going ot be fake and plastic (90% of the interviews I went to were like that). You adapt to the situation: if you candidate is showing intellect and sharpness you test that and start a sort of push-pull intellectual "battle of wills". If he detects that and doesnt like it he is not the candidate for me - I would hope he detects it, calls us on it and avoids the "traps". THAT is a good candidate, for me at least :)
My guess is that the culture there sortof enjoys these kinds of "traps".
The interviewer didn't ask: "Can I find a list of the top 10,000 words usages?" Which is the question the interviewee insisted on answering.
If I am a lead and I need a list of the top 10,000 words and I go to my co-worker and end up in a protracted argument about what that means philosophically I am going to be upset. I want him to say: "Here is how I'd do what I think you want. Oh, and by the way, I'm not sure an exact list of the top 10,000 words is possible .... here is how we can get as close as possible".
Sure, the list is a moving target. That fact is simply a bullet point in the risk assesement. Note it, move on and solve the actual problem that is presented.
Below you state 'everything is relevant'
"- assuming importance (his tone suggests he thinks he knew more than the interviewer. I imagine that might have come across in the interview)"
How can you assume the interviewer knows more?
"- assuming ingorance (if it seems amazing the interviewer is clueless on something then it probably isnt true. Adjust appropriately.)"
How can you assume that is true?
I would not want to work for ignorant douche bags like you. No wonder why this country is fucked up.
Look, I wasnt trying to say the interviewer is superior to the interviewee. Definitely not. But I am saying dont treat them like "ignorant douchebags" and dont assume you know more than them. Potentially you do - but assuming that is the case is a fallacy because you probably end up coming across wrong..
Perhaps you could enlighten me?
In my experience, if the interviewer seems to be trapped by assumptions, they aren't. ;)
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.
(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?
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?
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.
Of course, they just want you to explain the concept as if they've never heard of it. However, he was writing this after-the-fact, so I'm assuming it still seemed that he hadn't heard of the concept in retrospect, which is a much different beast.
That said, it was quite obvious that guy was trying to avoid the question. That wouldn't have sat well with me.
I didn't give nearly as much pushback as the author, though, since I assumed that wasn't the point.
Just use sort and uniq.
Or if it's slow, sort in parallel, then merge into one stream, and extract the frequencies.
Maybe this is why most technical documentation sucks, particyularly helppages oriented towards end-users.
Both Yahoo and Google offer services interesting to programmers; presumably they want documentation of a similar quality.
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.
Either you love it and want to hire the guy in a moment, or you think he's an unbearable smartass.
Interview != Quiz(at least the stereotypical "interview" at the stereotypical tech company. Then again, I think Wall Street/financial firms probably do the same. exact. thing.)
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.
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.
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).