Given a very long list of URLs, find the first URL which is unique ( occurred exactly once ).
Must do it in one traversal.
Suggested by the top answer and second answer, using a combination of trie and linked list.
The leaf node of a trie maintains a flag to record duplicate urls and pointer to a node in a link list.
Use a doubly linked list to link all the unique ones
- Remove the URL from the list if its count goes over 1
- So after one traversal, the first one of your linked list is the desired one.
Alternatively, we can also use Hash instead of Trie.