This is for the amazon interview Round 3, Question 2. http://www.geeksforgeeks.org/amazon-interview-experience-set-149-campus-internship/
Design an efficient data structure which supports queries like the following:
Which page was visited by exactly 2 users in day?
Which page was visited by only one user exactly 2 times in a day?
Which page was visited by ‘User 3? more than 5 times in a day?
The basic idea is to use cross linkedlist to store the data. There are 3 types of class: User, Page, InfoNode.
Initial User[] user, Page[] page. user[] and page[] are the entries to find infoNode. Each element in user[], page[] will point to a infonode by the nextNodeByUser pointer or nextNodeByPage pointer.
The cross linkedlist are contructed by the following rules:
1. Elements in page[] are ordered by visitedUserNum parameter. In this way, it can use binary search to find “Which page was visited by exactly 2 users in day?”
2. For those page element with same visitedUserNum, they are sorted by visitedTimes. In this way, it can use binary search to find “Which page was visited by only one user exactly 2 times in a day?”
3. Elements in user[] are sorted by their userId. For InfoNodes which are under same user, they are linked by nextNodeByUser. They are sorted by descended visit times. In this way, it can easily find “Which page was visited by ‘User 3? more than 5 times in a day?”
Please correct me if I’m wrong!
- /*
- * Q2. Given a log file of page visits of a website by different users for a day.
- * Entry in the log file is like this:
- * User 1 visited Page 4
- * User 3 visited Page 2
- * User 7 visited Page 9
- */
- class User{
- int userId;
- InfoNode firstUserNode;
- }
- class Page{
- int pageId;
- int visitedUserNum; //indicate this page is visited by how many users; pages are sorted by visitedUser.
- int visitedTimes; //indicate this page is visited by how many times in total; pages with same visitedUser are internally sorted by visitTimes.
- InfoNode firstPageNode;
- }
- /*
- * UserNode LinkList is sorted by visiting times. From large to less. To solve question 3.
- */
- class InfoNode{
- int pageId; //indicate the page it belongs
- int userId; //indicate the user it belongs
- int times; //indicate how many times has this user visit page_belong
- InfoNode nextNodeByUser;
- InfoNode nextNodeByPage;
- }