CODEWITHSUNDEEP
c++stl
kadina
kadina

Reputation: 5372

Which data structure in C++ suits to implement webbrowser history?

In one of the interviews, I asked by one of the interviewers how to implement history of web browser but don't show duplicates and need to show in reverse order meaning from most recent till the 5th website visited.

I told we can use linked list. When user enters a website it will be checked against a list of nodes and if the site is already present in the list, we will remove it from the list and add it as head. If it is not in the list, it will be simply added as head of the list. But he told order of complexity is O(n*n) and he asked me are there any other data structures or combination of data structured we could use to make the order of complexity as O(n). I didn't get any clue at that time. Can any one please let me know if you have any idea.

Upvotes: 0

Views: 1590

Answers (3)

makar
makar

Reputation: 504

As others have mentioned, Using a list and an unordered map would be your best bet. When visiting a new page, if the user has never visited it, add it to the end. if they have visited, recall the iterator using the hash map and remove it. The last step is to then add the url to the start of the list and give it a fresh new iterator in the map.

#include <list>
#include <unordered_map>
class browser
{
public:
    void visit (const std::string& page)
    {
        auto location = locations.find(page);
        if (location != locations.end())
        {       
            pages.erase(location->second);
        }
        pages.push_front(page);
        locations[page] = pages.begin();
    }

private:
    using Pages = std::list<std::string>;
    using Locations = std::unordered_map<std::string, Pages::iterator>;

    Pages pages;
    Locations locations;
};

Upvotes: 1

5gon12eder
5gon12eder

Reputation: 25459

You could do it in constant time if you are using your linked list plus a hash table with pointers to the list items.

Upvotes: 1

James Curran
James Curran

Reputation: 103575

um... With a linked list, Add URL to the start of the list (O(1)), continue throught list, deleting if found (O(n))

Upvotes: 1

Related Questions