8 ms·

My toughest job-interview question ever

45 points by techdog 17y ago

ulf 17y ago
Why would he want to implement a frequency-sorted list as a hashtable!?
- derefr 17y 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 17y 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.
- derefr 17y 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 17y 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 17y 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.
  - ErrantX 17y 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 :)
    - yason 17y ago
      What were these traps? I'd like to know.
      - ErrantX 17y ago
        - 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.
        byrneseyeview 17y ago
        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.
- badger7 17y 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 17y 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 17y 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.
Tichy 17y 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.
- derefr 17y 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?
  - ErrantX 17y 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.
    - derefr 17y ago
      > 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.
mkelly 17y 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.
yason 17y 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 17y 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 17y ago
    Along similar lines, as I was reading along, I was saying to myself something like, `my %word_count; for (@words) { ++$word_count{$_} }`...
mixmax 17y 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 17y 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 17y 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.
cperciva 17y 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 17y 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 17y 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 17y 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!
TheSOB88 17y 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 17y 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 17y 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).
deleted 17y ago
[deleted]
brown9 17y 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.
- deleted 17y ago
  [deleted]
- edw519 17y 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.
- deleted 17y ago
  [deleted]
known 17y ago
Interview != Quiz Most interviewers are NOT aware of this.
- brown9 17y 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 17y ago
Who can forget this: http://exold.com/article/stupid-interview-questions 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 17y 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 17y 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 17y 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.

45 points by techdog 17y ago

ulf 17y ago

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

derefr 17y 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 17y 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.

derefr 17y 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 17y 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 17y 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.
- ErrantX 17y 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 :)
  - yason 17y ago
    What were these traps? I'd like to know.
    - ErrantX 17y ago
      - 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.
      - byrneseyeview 17y ago
        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.
badger7 17y 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 17y 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 17y 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.

Tichy 17y 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.

derefr 17y 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?
- ErrantX 17y 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.
  - derefr 17y ago
    > 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.

mkelly 17y 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.

yason 17y 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 17y 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 17y ago
  Along similar lines, as I was reading along, I was saying to myself something like, `my %word_count; for (@words) { ++$word_count{$_} }`...

mixmax 17y 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 17y 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 17y 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.

cperciva 17y 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 17y 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 17y 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 17y 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!

TheSOB88 17y 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 17y 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 17y 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).

deleted 17y ago

[deleted]

brown9 17y 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.

deleted 17y ago
[deleted]
edw519 17y 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.
deleted 17y ago
[deleted]

known 17y ago

Interview != Quiz Most interviewers are NOT aware of this.

brown9 17y 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 17y ago

Who can forget this: http://exold.com/article/stupid-interview-questions 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 17y 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 17y 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 17y 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.