Question

link

Given a very long list of URLs, find the first URL which is unique ( occurred exactly once ).

Must do it in one traversal.

Solution

Suggested by the top answer and second answer, using a combination of trie and linked list.

1. The leaf node of a trie maintains a flag to record duplicate urls and pointer to a node in a link list.

2. Use a doubly linked list to link all the unique ones

3. Remove the URL from the list if its count goes over 1
4. So after one traversal, the first one of your linked list is the desired one.

Alternatively, we can also use Hash instead of Trie.

Code

not written