News for hackers. Stuff that matters.
Re:My toughest job-interview question ever by ntoshev on Tuesday May 12, 2009 @10:29AM (#605411)
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.
Re:My toughest job-interview question ever by cperciva on Tuesday May 12, 2009 @12:22PM (#605647)
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.