News for hackers. Stuff that matters.
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.

There are no comments on this comment yet.