Amazon Interview Question


Country: India
Interview Type: In-Person




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

lets number every sequence like 1->3->8 = 138, so every sequence will be unique
Now let say the sequence with time is 1->3->6->3->5->4....
So the sequence combinations can be 136,363,635,354,........
Now counting the sequence which occurs most can be the answer

Please do let me know if I am wrong here.

- DashDash December 19, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

You haven't taken into account the user. Every sequence should have same user for it

- perlscar December 19, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Its a great and simple idea.
you can use Hashmap to save frequency of page sequence with this idea.That gives o(1) for lookup

@perlscar:User info not needed as per the question

- sriramMS December 20, 2012 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

In your algo, sequence 100->11->12 and 1001->1->12 would have the same key. So use any special character b4 each n every page.

- dhineshkumar007 December 20, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

No the sequence should be specific to one user.

- perlscar December 20, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Even if the sequence were specific to a user from the table we can generate
User 1 : 1 -> 2 -> 4 -> 1 -> 6
User 2 : 1 -> 2 -> 4
.
.
During the generation of this data itself we can find the frequency of the sequences.

All pages can be mapped to unique numbers :) as there are only 8 pages.

- amit December 22, 2012 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

use GSP Algorithm.

Its a datamining technique to find sequential patterns.

set limit to 3

- sriramMS December 19, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

What is the time complexity for the GSP ? I bet its high
Correct me if im wrong

- alekar123 February 11, 2013 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

Assuming that the log file is sorted by time.
eg:
Time user page
1 dk 2
1 sp 2
2 dk 3
3 dk 5
2 sp 3
3 sp 5

Approach with Minimal memory usage:

Step1 : Find and store all users O(n)
Step2 :For Each user, Iterate through the file. (users * O(n))
Create a string with page seq like A2B3C5
use this string as Hashkey and increment the value for each time the seq occurs.

Step3: In the HashMap, find the key with the highest value and extract the page sequence from the key. eg: 2->3->5 from A2B3C5

For less time complexity,
step1: store all the records in a structure Array { char *name, int page,} , and sort the structure array by name.
Step2 : Iterate through the structure array only once. (O(n))
Create a string with page seq like A2B3C5
use this string as Hashkey and increment the value for each time the seq occurs.
Step3: In the HashMap, find the key with the highest value and extract the page sequence from the key. eg: 2->3->5 from A2B3C5

- dhineshkumar007 December 19, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

For a single user, if there are more than 3 page visits , then calculate the sequence as follows:
1 2 3 4 5
12 3
234
345

- dhineshkumar007 December 19, 2012 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

Create a counter array of 778 elements (each representing a 3 digit number that represents a 3-page sequence 111 to 888)

Create a hash map of (user:current_sequence) where current sequence is an integer representing the current 3-page sequence. After a page "p" is read for a user, reset the hash value to (cur_seq%100)*10+p. When the resultant number is >100, increment the corresponding index (cur_seq-111) in the counter array.

O(num_users + 800) space complexity. O(n) time complexity, where n is the total number of records.

- Jagat January 17, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Create a hash where you use a key made from 3 page ids like 23_145_9806 where 23, 145 & 9806 are 3 consecutive page ids.
In the parsing loop get next 2 page ids also, make this key and see if it exists. If yes, increment the count, if not add this new key to hash with value as 1. At the same time you can store the key with highest count. Every time you increment the count, just check whether incremented count is greater than the biggest count stored. If yes, then replace the biggest counter with this one.

In single loop you will get count of all the page ids as well as the biggest one of them.

Any comments??

- Jitender Mann December 20, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

The log file has logs for all the loops, so this iteration has to be done for all the users.

If you are doing it in single loop, then the sequence would be wrong unless the no of users is one.

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

as the site only has 8 pages, the possible page sequence is limited to 8x7x6. allocate an counter array to hold 8x7x6 integers.
1. create a Hash map witch each sequence as the key;
2. Parse the file to get the viewing page sequences grouped by each user , sequences are ordered by timestamps as this is a log file. O(N)
user sequences
---------------------------
A 1-2-3-4
B 2-3-5
C 4-3-5-8

3. iterate all the sequences in the hash map , increment the corresponding counter in the 8x7x6 array by 1.O(M*N)
sequeces counter
-----------------------------
1-2-3 1
2-3-4 1
2-3-5 1
4-3-5 1
.....

4. found the largest counter.

- angeloyz December 21, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

My first approach would be to create a HashMap<key = page number, value = number of times the page is opened>. This will be done in O(n).

Next, create an array of size 3 which we will return as a solution (at the end).

We will initialize the array with the first 3 keys from the HashTable.
Ex: A: 1, 2, 3

Now for every other key K in HashMap:
- compute the minimum value between the values assigned to those 3 keys stored in HashMap, and remember the key assigned to the min in Min_key
- check to see if the min is greater or equal to HashMap.get(K) ; if so.. ignore
else replace the Min_key with K
This will be done in O(5 * 3) = O(15)

So the total time : O(n) + O(15) = O(max(n,15)) = O(n)

At the end we have obtained in O(n) time complexity the 3 pages which were frequently used by the users.
Of course we can check , and reorder the values of the array to have in A[0] the most visited page, A[1] less visited, A[2] the least visited page, without changing the complexity.

- Kamy December 20, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

For the following sequence,
7-8-4-3-6-3-6-3-6-3-6-1-9-12-9-12-9-12-9-12-9-7-8-4-7-8-4 we do not need the maximum page visit but only the sequence. Your algo will get 3,6 and 9 which is not required at all but the seqnce req is 7-8-4

- dhineshkumar007 December 20, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

In the question itself it is given there are only 8 pages in the website so the sequence cant contain pages with page number >8

- akb December 21, 2012 | Flag


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