Amazon Interview Question for SDE1s


Country: India




Comment hidden because of low score. Click to expand.
2
of 4 vote

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.
For 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.

- sang December 26, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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??

- pulkit.mehra.001 December 27, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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?

- Heramb January 10, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

In H2 we can include some kind of time stamp so that we can figure out if the page was visited on the same day or not.

- pulkit.mehra.001 January 22, 2014 | Flag
Comment hidden because of low score. Click to expand.
1
of 3 vote

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.

- King007 December 27, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

the inner map should need a list of strings right? what if more than one page are accessed on a single day? Since your key for inner map is date, you need provision to add multiple strings as the page strings.

- Heramb January 10, 2014 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

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.

- tanmoy December 27, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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?

- KnowledgeSeeker December 26, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I think it means any two different days(not consecutive), if a user visits three different/unique pages, then his info should be stored.

- pulkit.mehra.001 December 27, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- rmn December 27, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Please check the question properly, the problem is not for database it is for data structure. Database approach will be completely different than using data structure

- Anonymous December 28, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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?

- Teja December 27, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Hi Teja, your perspective is right. But they are asking for a data structure so they might be looking for how you are tackling the problem, i.e., while designing the data structure your approach etc. I think that's the only reason such questions are asked.

- pulkit.mehra.001 January 22, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

its ia binary index tree problem where frequency is also added.

- HadoopUser December 28, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- biplap December 29, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

{
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;
}
}

- AmitDubey August 04, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

{
        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;
    }
}

- AmitDubey August 04, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

{
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;
}
}

- adubey31 August 04, 2017 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More