Amazon Interview Question
SDE1sCountry: India
Interview Type: In-Person
We can create a Data structure using 2 Map's, such that First map's data is for 24 hrs basis, where as 2nd map data is permanent.
-> Map<Customer cus,Linked List with website and pages>()
Every overnight, it collects that particular day data, and checks if the customet visited pages > m, then it updates second map
-> Map<string website,Map<Date date, ArrayList Customers>();
The question is about finding people having atleast "m" number of unique page visits. It is also important to store the unique pages visited on a daily basis. Plus, only those who have visited the website exactly "k" number of days.
So we can create a HashMap with key as customer name and value as a two dimensional array as given below:
date of visit number of pages visited unique pages compared to previous visits
04/09/2013 10 10
05/09/2013 12 6
The total number of unique visits now is 16. We can also store the information about pages visited to find out if the new pages visited are unique or not.
I will approach the problem a little differently and conclude on the design of data structure required to support request as per question.
Let us assume that there is a server component which is going to serve the request. Assuming a client / server architecture, let us assume following plain old objects (poo) specification (Meaning - below will also have corresponding DB representations) :
class poo_user
{
long user_id; // maybe MD5 hash
// other details
}
class poo_ws_page
{
long ws_page_id; // maybe MD5 hash
}
class poo_website
{
long website_id; // maybe MD5 hash
sequence<poo_ws_page> list_ws_page; // may translate to ws_page_id in DB code
sequence<date> date_visited;
}
// data structure in code to support the request based on above specification
unordered_multimap<poo_user, poo_website> user_website;
/**
* Returns a Set of customers who have visited the website on exactly given days and should have visited at least given distinct pages altogether.
* @param days the number of days a customer visits
* @param distinctWebPageVisitCount the minimum number of distinct web pages visited by the customer.
*/
Set<Customer> getCustomers(int days, int distinctWebPageVisitCount) {
/** First find all customers who have exactly 'days' entries in the mapping class's set. Then from this set, return only those instances who's webPage count is >= 'distinctWebPageVisitCount' */
}
/** Many to Many mapping between customers and webpages. Each mapping denotes a customer's visit to a webpage on a particular date. The tuple (customer, webPage, date) is unique */
class CustomerWebPageMapping {
id;
Customer c;
WebPage webPage;
Date date;
/** other details */
}
class Customer {
id;
/** other details */
}
class WebPage {
id;
/** other details */
}
Use a combination of a hash-table and a hash-set .
When a user visits a webpage, the
hashmap is consulted to get
object. Inside
the hashsets
and
are updated and then their sizes are checked.
, insert the user into
[ which holds the users satisfying the criteria mentioned in the question]
remove the user from
do nothing.
- Murali Mohan September 03, 2013