Amazon Interview Question
SDE1sCountry: India
I am not quite getting how you are forming the HashTables.
For H1 - key is the username and the value stored is ??
For H2 - key is the pageString, then where are you storing the days in both H1 and H2??
H1 is a nested hashmap. Its key is username and value is the H2 Hashmap.
and H2 has pagestring as key and day count as value.
What I am not understanding in this solution is, if we encounter the same pagestring more than once in a single day, will this algo ignore the day count? how to trace that on which date the day count has been increased?
We can use HashMap to store the user information. Here the key will be username and value will be another hashmap like: Map<String, Map<Date, String>> userInfo = new HashMap<String, HashMap<Date,String>>();
the userInfo will map user with their activity. the innermap will store user activity for a particular day. inner map will map particular date with the unique page visit for the particular day.
at the end of the 3rd day iterate through the map for each user and check for the unique visit on a particular day.
I think this satisfies the requirement.
I will use a map something like Map<String,Map<Date,List<String>>> userInfo = new HashMap<String, Map<Date,List<String>>>(); where I will add the date of the users visit as key and the list of page id of the pages visited by the user as the value in the inner Map. In the outer Map I will put this inner map as the value against the UserId as the key.
So its up to you how do you want to process the criteria. If you wants to search for 5 days out of 12 days as mentioned by "rmn" you are free to do that.
I think this is more generalized solution for this problem.
Question - About the 2 visits in 3 days
suppose user visits on 1st, 2nd and 3rd, so he is not to be tracked.
But on 4th he doesn't visit the site, so as per 2 visits in 3 days he should be tracked
i.e. visited on 2nd, 3rd and not on 4th
Is this assumption correct? also can you clarify around 3 days, are those need to be consecutive?
First of all, you should not come up with a solution that is specifically designed for this particular problem, i.e. 2 out of 3 days. Your solution should also work for, let's say 5 out of 12 days case.
Second, I think here the interviewer wants to hear something about distributed computing, rather than conventional data structures. We're talking about a huge amount of data, so my answer would be using a distributed database to store all this information and use database operators to find which customer visited how many pages for how many days.
I get what the other answers are doing but in the real world, this information is going to be in a database somewhere. Is it wrong to say we have something like the following -
Customer
----------------------------------------------
id | name | password
VisitHistory
-----------------------------------------------
id | customer_id | product_id | timestmap
And do some SQL reports on it?
We can use hashmap HashMap<String, Integer> dayCountMap where key is userid and value is no of days visited and hashmap of set HashMap<String, Set<String>> pageVisited where key is userid and value is set of pages visited by the user.
For day 1, we put <userid,1> in dayCountMap if entry for key <userid> does not exist in it. Also, if entry of key <userid> does not exist in pageVisited, we create a new set with the page string and put it in pageVisited as <userid,pagevisitedset>. If the entry of the key <userid> exists, we just add the page to the set (it'll be discarded if it is duplicate).
For day 2, we increment the value integer in dayCountMap by one if key for <userid> exists or put an entry <userid,1> in it if it does not exist. We follow same process as in previous day for adding entries in page visited.
For day 3, we repeat the process as for day 2.
Finally, for all users we check if the integer value in dayCountMap ie. dayCountMap.get(<userid>) == 2 (ie, user visited exactly for 2 days) and pageVisited.get(<userid>).size() > 3 (ie more than 3 unique pages visited) and add the user to contact list if it satisfies both conditions
{
Map<String, User> map = new HashMap<>();
String[] lineArray;
String line;
int userCount =0;
int i =0;
while(i < length) {
//Read the lines
//Split the line with a space delimiter
lineArray = arr[i].split("\\s+");
User user;
if(map.containsKey(lineArray[1])){
user = map.get(lineArray[1]);
if(user.getDate().equals(lineArray[0])){
}else{
if(!user.isMark()){
userCount++;
}else{
user.setMark(true);
}
}
}else{
user = new User(lineArray[1], false, lineArray[0]);
map.put(lineArray[1],user);
}
i++;
}
System.out.print(userCount);
}
class User{
private String name;
private boolean mark;
private String date;
public User(String name, boolean mark, String date) {
this.name = name;
this.mark = mark;
this.date = date;
}
public String getName() {
return name;
}
public boolean isMark() {
return mark;
}
public void setMark(boolean mark) {
this.mark = mark;
}
public String getDate() {
return date;
}
}
{
Map<String, User> map = new HashMap<>();
String[] lineArray;
String line;
int userCount =0;
int i =0;
while(i < length) {
//Read the lines
//Split the line with a space delimiter
lineArray = arr[i].split("\\s+");
User user;
if(map.containsKey(lineArray[1])){
user = map.get(lineArray[1]);
if(user.getDate().equals(lineArray[0])){
}else{
if(!user.isMark()){
userCount++;
}else{
user.setMark(true);
}
}
}else{
user = new User(lineArray[1], false, lineArray[0]);
map.put(lineArray[1],user);
}
i++;
}
System.out.print(userCount);
}
class User{
private String name;
private boolean mark;
private String date;
public User(String name, boolean mark, String date) {
this.name = name;
this.mark = mark;
this.date = date;
}
public String getName() {
return name;
}
public boolean isMark() {
return mark;
}
public void setMark(boolean mark) {
this.mark = mark;
}
public String getDate() {
return date;
}
}
{
Map<String, User> map = new HashMap<>();
String[] lineArray;
String line;
int userCount =0;
int i =0;
while(i < length) {
//Read the lines
//Split the line with a space delimiter
lineArray = arr[i].split("\\s+");
User user;
if(map.containsKey(lineArray[1])){
user = map.get(lineArray[1]);
if(user.getDate().equals(lineArray[0])){
}else{
if(!user.isMark()){
userCount++;
}else{
user.setMark(true);
}
}
}else{
user = new User(lineArray[1], false, lineArray[0]);
map.put(lineArray[1],user);
}
i++;
}
System.out.print(userCount);
}
class User{
private String name;
private boolean mark;
private String date;
public User(String name, boolean mark, String date) {
this.name = name;
this.mark = mark;
this.date = date;
}
public String getName() {
return name;
}
public boolean isMark() {
return mark;
}
public void setMark(boolean mark) {
this.mark = mark;
}
public String getDate() {
return date;
}
}
I would go with a hashtable approach. create a hashtableH1 for storing username(key of H1) , hashtable H2 of pagestrings(key of H2), day(value of H2) which will be the value of H1.
- sang December 26, 2013For day 1 store info for all usernames in H1 and H2.
For day 2 for each username check if entry exists in H1. If so check if the pagestring is same . If so this means the same user visited the page twice in 2 different days. so increase the day count by 1.
For day 3 for each username check if entry exists in H1. If so check if the pagestring is same . If so this means the same user visited the page twice in 2 different days. so increase the day count by 1.
Now check the hash H1. For each username check the pagestring and day count. if the days is 1 or 2 for more than 3 pages this means he has visited more than 3 unique pages in 2 different days. hence output that username.