Jim
BAN USER- 0of 0 votes
AnswersYou have a web server's log that records for each user the URL that he accessed.
Example format:Time-stamp User-id URL
How to find the maximum common (sub)sequence of visited URLs from all users? Write code in java
Log entries are ordered based on timestamp.
Example log (omitting timestamp for clarity):
John URL1
John URL2
Jim URL2
Mary URL1
John URL4
etc
Update:
Example:User-id URL 186 A 187 B 186 C 188 B 186 C 187 A 186 B 188 A 188 C 189 A 189 D 187 C 189 B 186 A 187 C 189 A 189 C
So the max common URL sequence is A,C,C (URL A followed by URL C, followed by URL C)
- Jim in United States| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Java
@freshboy:I told him to use suffix tree but he said to much space find another way.I did not tell anything about DP version.But did something similar to what you side, i.e. use a map of user-id to sequences and then iterate over all sequences to find the longest one.At least that was the idea. I was rejected though
- Jim January 27, 2013@vik:It seems this is a valid corner case (@Hua can verify for sure since he understands this very good).I think that if we sort the sequences prior to the algorithm then, Hua's algorithm would work since we would have after sort:
186: a,b,x
187: a,b,x
188: d,e,x
189: d,e,x
And we would get x as result. Runtime would not increase i.e. O(kmn + klogm)~ O(kmn).
Am I right?
@Hua:"However we don't need to create this array, since we already have it as the values in hashtable". But to find the LCS of 2 strings the DP algorithm needs extra space.I haven't read a version of the algorithm not needing extra space.So I am not sure why you say we don't need the extra array
- Jim January 22, 2013
I am not sure I understand what you say.First of all the question is about URL sequences.How do you get it if in your HashMap you use as key a single URL? Also I am not sure what you store in the 2 HashSet<String>.In the first you say "the number of unique user who have visited this site".Is it a number then? And what is the use of the other HashSet?
- Jim February 04, 2013