Amazon Interview Question: Given a log of users visit to... | Glassdoor

Interview Question

Software Engineer Intern Interview

Given a log of users visit to a site for a day, how would

  you find returning users given the log visit for another day
Answer

Interview Answer

4 Answers

7

Put the user-ids of the first log file into a HashSet(so that there are no duplicates in case user visits twice on the same day). Iterate the second log file and check if the Hashset contains for the user. There may be multiple same user-id records in the second log file. So if a user is found once in the HashSet, print his user id and remove his username from hashset, so that its not printed twice.

Time Complexity would be O(n) and space complexity would be O(m) for the hashset(first log file).
where n is the total no. of user_ids in both the log files and m would be all the records of the first log file.

Varun on Mar 1, 2015
3

The above analysis is just wrong.
consider 'n' to be number of user id's in first log file.
consider 'm' to be number of user id's in first log file.
Each element needs to be searched in the hash set 'n' times in a linear search , and for 'm' user id's the
complexity comes to theta(mn) , worst case is when m = n where complexity becomes theta(n^2)

This is my solution.
Extract all the user ids from log file 1 into array 'a1' -> O(n)
Extract all the user ids from log file 2 into array 'a2' -> O(n)
Just sort the array 'a1' user ids using quick sort. -> O(nlogn) worst case
Now for each user id in array 'a2' perform binary search to find in array 'a1' -> cost per user id is theta(log(n)) worst case
For all the user ids in 'a2' , cost =O( m *logn)

Total time is dominated by O(mlogn)
Even if m = n , it would still be O(nlogn) which is anytime better than O(n^2).

Ans on Dec 29, 2015
0

Worst Case for quick sort is O(n^2). I think Mergesort will work better with order O(nlogn)

Anonymous on Feb 7, 2016
5

Searching in hashset is O(1)
So the given solution is optimal

Sujit on Feb 11, 2016

Add Answers or Comments

To comment on this, Sign In or Sign Up.