Amazon Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: In-Person
You can use Priority Queue (represented by Doubly linked List), having pointers to both head and tail. Also maintain a hashtable which maps to nodes based on URL.
Foreach entry
{
if(URL is in hashtable)
{
Delete node from temp position, update count;
insert into head
}
else
{
Insert Node into head of DLL and set count to 1
}
}
GetTop3()
{
Retrieve first 3 nodes from the DLL, since they were accessed most recently.
}
I think you still misunderstood the question. It asks for top sequence of 3 urls, not top 3 urls.
Create a hash map with the user Ids as a key(s), the value of a particular user would point to another hash map with indexes representing the sequence of {3} websites and a value that is the count of that sequence. After generating the data structure, simply iterate through the users and their sequence of {3} values and store the maximum sequence until you've gone through both hash maps.
there is one log entry per user?
- Johann January 24, 2014