[ww520]

Also, while trie looks better on paper than hashtable in regarding to complexity analysis, in reality hashtable can be 2X~3X faster than trie. This is because the hash key can be computed very fast with the key data fitted in a L1 cache line and with much less branching jumps in the hashing function, while trie does a separate memory load on each node going down the tree plus each character comparison causes a branching jump. It's always good to benchmark before settling on a scheme.

[kolbe]

Both of your answers in this thread are great, but it doesn't sound like what behdad was looking for. I think the unfortunate reality is that you're supposed to try to figure out what he wants to hear, which is that his answer is the most correct one in his mind to this awesome question that's so great he violates his company's rules in order to keep asking it. This just lead to cheating, where a smart person with connections learns from a friend what behdad wants to hear, and is able to give it to him, while people who don't have these connections give a more correct answer like yours and get rejected.