This is a problem from Skiena's excellent book The Algorithm Design Manual:
Give an algorithm for finding an ordered word pair(e.g."New York") occurring with the greatest frequency in a given webpage. Which data structure would you use? Optimize both time and space.
We need to look at all the words, so clearly we can't do better than O(n)
time. One solution I can think of is inserting each ordered pair in a priority queue (O(n)
time and space), and then returning the top item. However, the official site has a solution which suggests using a Trie. I understand that words may be repeated, or may be prefix/suffix of other words, so a Trie would save space, but can't figure out how to answer the question using it.
Ideas?
O(n)
time so the only problem worth considering here is how to save some space. If you've a better algo that saves space and is faster thanO(n)
, you would be eligible for more than just some rep points here. $\endgroup$ – Abhijit Sarkar Feb 5 '19 at 9:38