3 ms·
My personal favorite solution to this problem is to use a trie. When asked to reduce the memory usage, you can recognize that the trie is actually a DFA and ap
by Adrock 16y ago
My personal favorite solution to this problem is to use a trie.
When asked to reduce the memory usage, you can recognize that the trie is actually a DFA and apply a DFA-minimization algorithm. There are several other interesting approaches here:
http://en.wikipedia.org/wiki/Trie#Compressing_tries http://en.wikipedia.org/wiki/Trie#Compressing_tries
- dangoldin 16y agoThat's actually pretty neat - no one has really suggested this approach yet. I don't think that this will work as memory keeps on decreasing - is there a way to make a trie probabilistic?
- Adrock 16y agoInstead of being probabilistically wrong, you can save memory by removing some branches of the trie and becoming deterministically wrong. You could remove the largest branches that correspond to the fewest words. Alternatively, you could remove the branches that correspond to the least queried words if you know something a priori about the query pattern.
- alok-g 16y agoInstead of making it probabilistic, I would rather add more memory to the system. The idea of making it probabilistic seems to me to be entirely for leading the interview candidate to the solution you have in mind.