Bloomberg LP Interview Question
Country: United States
I solve the problem in following ways
Create a b+ tree,use dates are separating elements,
first level is used for year,
second is for months
and third is day,
and at day store each URL by linked list which is both way, after linked list use hash table to directly file the URL,
this is used to maintain the constrain that each url can only comes only once,
actually this does not happens, like in google crome, they don't have above constrain.
Now when every user click on a url ,
first we check weather the clicked url is present or not ?,
if not present then we insert it into tree and create new entry in hash table,
It is like two indices on a database. so data is same for both indices.
Now if url already present then we remove that element from linked list and create new node at first node and join it.
so this require constant time for insertion, searching , deletion etc.
You can create a hashtable with key as integer and value as string.
When hashtable is empty insert the url as string with key as maxofInterger (2,147,483,647) and decrement the key for every new and latest entry but if the entry exists delete it and create new with new hash value or change the key to the latest key.
It would help if someone points out if my solution is right or wrong!
We could add each entry where the key is a timestamp specifying when the user clicked on the URL and the value being the URL itself and the hashtable could implement a comparator to order the items based on key in descending order.And returning topmost element in the hastable would give the most recently used URL
Since the question specifies it has to be an implementation with hash table,solutions such as using a queue or maxheap would mean it can be done only with a queue or max heap alone and hashtable would not be required!
I agree that browser needs time stamps (for displaying the history and erasing some of it). So I guess, I would have an unordered map (which is based on hash-table) of URL's with time stamps as keys, and I also would have a list of the same time stamps (or pointers to them in the map) in chronological order. The end of the list would be considered the "top" of it mentioned in the task.
Maintain a Doubly liked list along with the HashMap. See java docs for How LinkedHashMap is used implementing the LRU.
- balani.kunal June 10, 2013