Amazon Interview Question for SDE1s


Country: India
Interview Type: In-Person




Comment hidden because of low score. Click to expand.
1
of 1 vote

Use a combination of a hash-table and a hash-set .

Map userVisits = new HashMap<Integer, VisitDetails> // Here customerId would be the key of type Integer, VisitDetails object is the value defined as below.

class VisitDetails = {
Set  visitedOnDates = new HashSet<Date>; // this holds dates visited on
Set  visitedWebPages = new HashSet<Integer>; // this holds web page ids 
}

Set reqdUsers = new HashSet<Integer> // this holds user id which satisfy the criteria mentioned in the question

When a user visits a webpage, the

userVisits

hashmap is consulted to get

VisitDetailsObject

object. Inside

VisitDetailsObject

the hashsets

visitedOnDates

and

visitedWebPages

are updated and then their sizes are checked.

If visitedWebPages.size() >=m and visitedOnDates.size() == k

, insert the user into

reqdUsers

[ which holds the users satisfying the criteria mentioned in the question]

If visitedWebPages.size() >=m and visitedOnDates.size() > k

remove the user from

reqdUsers

If visitedWebPages.size() >=m and visitedOnDates.size() < k

do nothing.

- Murali Mohan September 03, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Sorry for a botched-up formatting.

- Murali Mohan September 03, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Actually, the last condition

If visitedWebPages.size() >=m and visitedOnDates.size() < k
do nothing

is superfluous. It is not needed.

- Murali Mohan September 03, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 2 vote

User { 
	...
	List<HistoryRecord> browsingHistory;
}

HistoryRecord {
	Set<String> pages;
	Date date;
}

It's easy to map such structure on relational database and find required users with one query. Or just by iteration over list of users.

- amt September 03, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

class Visitor{
	Map<Long, HashMap<Date, HashMap<Long, Integer>>> m = new HashMap<Long, HashMap<Date, HashMap<Long, Integer>>>();
}

	//Map<visitorId, HashMap<Date, HashMap<pageId/pageName, countOfTimesVisited>>> m

- Jayesh. September 04, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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>();

- prashanth September 05, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- Rajesh September 05, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

The table is not showing properly..
The column dates are date-of-visit & number-of-pages & unique-pages-compared-to-previous-visits

- Rajesh September 05, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;

- nilukush September 08, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

struct person { 
	int pid;
	unordered_map<string,int> visit;
  	// string for webpage url.
  	// int for number of visits based on days.
}; 

// Create a newPerson. 
struct person* newPerson(int pid) 
{ 
	struct person* p = new person; 
	p->pid = pid; 
	p->visit.clear(); 
	return p; 
}

- Shinichi Kudo October 26, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

/**
 * 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 */
}

- june.pravin September 04, 2013 | 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