You are developing a web browser (something like e.g. Netscape, etc.) and need to display all visited links on a page. The visited links need to use a different color then that used to display scheme than the unvisited links. Now, given a history of links you have visited before, how would you go about writing the piece of code that makes the determination if you have seen this link before? Answer or not? The answer could be a simple string comparison, but then think about the time it will take for the client to render any HTML page. Alternatively, so, given a history of URLs, come-up with an elegant way (algorithm, data structures, etc.) to make the determination if a given link already exists in the history list?  

 

 

Solutions:

 

Using a Hash Table is probably the most efficient way to do this. You can use several hashing algorithms. For example, checksum of a link can be used as a key for hashing. This will ensure o (1) order provided a good checksum algorithm is used. Whenever a page loads, we can parse all URL's from the page, take their checksum, and compare them with the hash table. Whichever links match are then displayed in a different color.