Comment by cperciva | Hacker News Reader

Comment by cperciva | Hacker News Reader

Parent Full thread

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.

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.

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!

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.)

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.

    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))

This code processes 12Mb of text in less than 5 seconds on my laptop.

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.

Reply on news.ycombinator.com