My toughest job-interview question ever(asserttrue.blogspot.com)
asserttrue.blogspot.com
My toughest job-interview question ever
http://asserttrue.blogspot.com/2009/05/one-of-toughest-job-interview-questions.html
74 comments
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.
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.
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!
The grand parent is right, this is a horrible programming solution but the author is not a programmer!
[deleted]
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.)
(((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.)
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.
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.
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))
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.
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.
[deleted]
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.
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.
[deleted]
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.
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.
[deleted]
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.
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.
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.)
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.
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.
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.
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.
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.
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.
I'd hire him in a heartbeat.
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 :)
But it depends on the job :)
What were these traps? I'd like to know.
- chasing an irrelevant point (the interviewer specifically wanted to move on. NEVER stop that, that is the one single that can cost you a 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.
- 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.
The idea of "traps" is ridiculous and shows us how little some companies understand about the interviewing process.
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.
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.
Well.. perhaps "trap" is the wrong word. Or rather "designed trap" is the wrong concept.
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 :)
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 :)
He was interviewing at (guess:) google.
My guess is that the culture there sortof enjoys these kinds of "traps".
My guess is that the culture there sortof enjoys these kinds of "traps".
You're right that he did "wrong" things from the perspective of trying to please the interviewer.
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.
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.
"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."
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.
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.
not at all: but flagging a point to death when I already made clear what you said registered with me is an instant turn off.
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.
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.
The problem is not real world. The data is not real world. The solution is not real world. The entire dialogue is a fantasy. So why even engage in it? Were you expecting something real-world from it?
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.
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.
Real world examples dont work because, as this post points out very well, there are just too many variables and factors to allow anyone to produce a viable solution in the space of an interview.
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)
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)
"The input data doesnt matter..."
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
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
I would disagree Errant. If the problem was "Organize a list of 1 million words", then I would agree with you. With no context, it becomes little more than an academic problem.
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
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
Im not sure though: the problem was as broken down as you can pretty much get. The dataset could have been anything - the problem was to order the top 10,000 words. The input data was, at the end of the day immaterial. It is a problem to be solved in another engineering "block" (im not suggesting, in case that was the miscommunication, that is shouldnt be solved).
The last 2 paragraphs of your reply I would agree with :)
The last 2 paragraphs of your reply I would agree with :)
That's "you're right." Engineers must have excellent writing and communication skills. You're fired.
Yay abuse.... you should see some of my other writing: dyslexia really takes it's toll when you cant see the difference between "many men" and "man ymen" (a mistake I made last night) even when you read it back. It makes teeny tiny grammar errors like that immaterial ;)
Take your abuse elsewhere: I am happy to debate my points but at least bring something constructive.
Take your abuse elsewhere: I am happy to debate my points but at least bring something constructive.
I'm not meaning to be abusive here, but I would highly recommend a spelling and grammar checker plug-in/add-on. There are many solid options available to both IE and FF. Being a person with dyslexia, and obviously knowing how critical clear communication is, it would be responsible of you to use such a tool to reduce the likelihood of confusion.
-Rick
-Rick
Ho ho! You fell into my trap!
"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.)
"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.)
chasing an irrelevant point
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.
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.
I agree with you and don't understand people who argue differently.
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.
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.
I disagree. This seems to suggest that no matter how stupid the interviewer is, you just need to make him feel better and you'll get hired. Which defeats the purpose of the interview. I'd walk out on that interview as the interviewee.
"- chasing an irrelevant point (the interviewer specifically wanted to move on. NEVER stop that, that is the one single that can cost you a job)."
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.
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.
Good arguments (apart from the insults: conversely I wouldnt employ you because you dont appear to see any subtlety in all of this).
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..
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..
Anecdotally, when a one-hour interview turns into a three-hour discussion of a side point, it is a really good sign that the interviewer has the ability to bounce of new ideas and discuss them while the interviewee has not.
This is all good advice if you know the social qualities you are looking for determine whether the person can do the job or not. This issue is actually a statistical nightmare because companies think they know exactly who to hire and they try to prove it by showing off the people they have hired. But they need to compare their current employees to people they turned away. Any study on this has shown companies have no idea who to hire after the basic the basic personally and technical filters.
I would appear to have missed those traps too. From my reading, he appears to have avoided many traps of assumption, traps that the interviewer blundered into without even noticing. IE, there is no average corpus, language is dynamic, hash functions aren't all equal, etc.
Perhaps you could enlighten me?
Perhaps you could enlighten me?
>From my reading, he appears to have avoided many traps of assumption, traps that the interviewer blundered into without even noticing.
In my experience, if the interviewer seems to be trapped by assumptions, they aren't. ;)
In my experience, if the interviewer seems to be trapped by assumptions, they aren't. ;)
Ditto, funnily enough, but the defensiveness portrayed differentiates my experience from that of the OA.
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".
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?
(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 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.
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?
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?
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.
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.
> 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.
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.
I see your point, but I don't think the questions were particularly insane.
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.
That said, it was quite obvious that guy was trying to avoid the question. That wouldn't have sat well with me.
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.
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.
I didn't give nearly as much pushback as the author, though, since I assumed that wasn't the point.
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.
Just use sort and uniq.
Or if it's slow, sort in parallel, then merge into one stream, and extract the frequencies.
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.
Along similar lines, as I was reading along, I was saying to myself something like, `my %word_count; for (@words) { ++$word_count{$_} }`...
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.
Maybe this is why most technical documentation sucks, particyularly helppages oriented towards end-users.
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...
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.
Both Yahoo and Google offer services interesting to programmers; presumably they want documentation of a similar quality.
"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.
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.
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.
[deleted]
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.
Either you love it and want to hire the guy in a moment, or you think he's an unbearable smartass.
Why would he want to implement a frequency-sorted list as a hashtable!?
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.
Interview != QuizActually 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.)
(at least the stereotypical "interview" at the stereotypical tech company. Then again, I think Wall Street/financial firms probably do the same. exact. thing.)
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.
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.
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.
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.
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).
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).
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.