3 ms·

The author of the initial post did make some technical mistakes. Here's one that jumped out at me - "What will you do in the event of hash collisions?" the pro

by lacker 17y ago

The author of the initial post did make some technical mistakes. Here's one that jumped out at me - "What will you do in the event of hash collisions?" the professor asked. "How do you know there will be any?" I said. "Look, the English language only has a million words. 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. This is intuitive but incorrect. The principle is also known as the birthday paradox - http://en.wikipedia.org/wiki/Birthday_paradox http://en.wikipedia.org/wiki/Birthday_paradox If you hash a million words into a 4-billion table, you do expect collisions. You expect to get collisions when you insert on the order of the square root of the size of the table, and the square root of 4 billion is much less than a million.

patio11 17y ago
If we're getting collisions it means we need a better hash algorithm. It would hardly be the first time. The hash function which is the default for Java strings, for example, sucks. int hash = 0; for (int i = 0; i < length(); i++) { hash = 32 * hash + charAt(i); } return hash; (Lots of collisions on any English dictionary unless you use huge numbers of buckets.) This actually had important implications for a project I once worked on, in exactly the manner you would expect it to have implications for this interview. The difference was that, in meetings about this issue, I did my best to a) give the customer what they needed and b) did not give the impression I was saying "Screw what you want, I'll tell you what you need". The birthday paradox problem, by way of comparison, is negligible for this use case. Words in English follow a zipf distribution (you may hear "long tail" more these days). If there is a collision, it is overwhelmingly likely to be between two words on the long tail (no impact to first 10k words) or between a word on the fat head and the long tail, in which case you're overwhelmingly likely to encounter the fat head word first, and even if you don't, whoopsie 1/100th of a percent of your output was corrupted. Wow, twice in one day natural language processing has reared its head. Thats more than in my last two years! Booyah, old interests.

by lacker 17y ago

patio11 17y ago

If we're getting collisions it means we need a better hash algorithm. It would hardly be the first time. The hash function which is the default for Java strings, for example, sucks. int hash = 0; for (int i = 0; i < length(); i++) { hash = 32 * hash + charAt(i); } return hash; (Lots of collisions on any English dictionary unless you use huge numbers of buckets.) This actually had important implications for a project I once worked on, in exactly the manner you would expect it to have implications for this interview. The difference was that, in meetings about this issue, I did my best to a) give the customer what they needed and b) did not give the impression I was saying "Screw what you want, I'll tell you what you need". The birthday paradox problem, by way of comparison, is negligible for this use case. Words in English follow a zipf distribution (you may hear "long tail" more these days). If there is a collision, it is overwhelmingly likely to be between two words on the long tail (no impact to first 10k words) or between a word on the fat head and the long tail, in which case you're overwhelmingly likely to encounter the fat head word first, and even if you don't, whoopsie 1/100th of a percent of your output was corrupted. Wow, twice in one day natural language processing has reared its head. Thats more than in my last two years! Booyah, old interests.