-1
$\begingroup$

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?

Improve this question
$\endgroup$
  • $\begingroup$ I am not sure to understand how you use the priority queue and perform O(n) in time. Can you give details ? $\endgroup$ – Optidad Feb 4 '19 at 13:21
  • $\begingroup$ @Vince You simply insert each pair in the max PQ with frequency 1 if not already present. If present, you increment the key. $\endgroup$ – Abhijit Sarkar Feb 5 '19 at 2:11
  • $\begingroup$ and you access on key (pair of word) in a maxqueue in O(1) ? With finally no real interest on the maxqueue as you only need one maximum. $\endgroup$ – Optidad Feb 5 '19 at 9:03
  • $\begingroup$ @Vince That's right. Clearly, you can't do better than 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 than O(n), you would be eligible for more than just some rep points here. $\endgroup$ – Abhijit Sarkar Feb 5 '19 at 9:38
2
$\begingroup$

In an $n-$word text you have exactly $n-1$ ordered word pairs (not distinct of course). If you use a Trie, you don't need to represent all $n-1$ pairs separately. Take for a example the following text:

A new puppy in New York is happy with it's New York life.

You first start looking at the words in the text as pairs where the first pair is (a,new), the second is (new,puppy), (puppy,in), ... ,(York,life). The resulting trie will look something like this:

trie

In order to find which pair appears the most times you need to count how many times you reach each leaf.

Improve this answer
$\endgroup$
  • $\begingroup$ What you showed isn't a Trie because words shouldn't be repeated: Instead of saving space, you use more space. This tree has no advantage over a max priority queue, and takes more time to find out the most frequent pair (counting leaves). $\endgroup$ – Abhijit Sarkar Feb 3 '19 at 22:48
  • 1
    $\begingroup$ It is a trie. Consider the case you insert the word "haha" letter by letter. Wouldn't each letter occupy one node even though they are repeated? Also, I don't use more space. You have to store each pair at least once, you can't do better than that! Of course you can store only once the pairs that appear multiple times but my represenation does exactly that. Finally, I don't think counting how many times you reach each leaf is slower than what you propose. After all, you need to check that the pair is already in the trie! That being said I agree that counting might not be the optimal way $\endgroup$ – phan801 Feb 4 '19 at 21:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.