Re:Tough Crowd
by patio11 on Thursday May 14, 2009 @02:56AM
(#608367)
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.
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.