Most Common Three-Website Sequences
Learn this problem
AmazonNEW GRADPHONE SCREENProblem statement
The parallel arrays timestamps, customers, and webpages describe webpage visits. Record i means that customers[i] visited webpages[i] at timestamps[i].
A three-website sequence chooses any three visits by the same customer in strictly increasing timestamp order; the visits do not need to be consecutive. A sequence's score is the number of distinct customers who produced it. Repeating the same sequence multiple times for one customer contributes only one point.
Return up to the three highest-ranked sequences. Rank by descending score, then lexicographically by the three website names. Serialize each result as "first>second>third".
Function
topWebsiteSequences(timestamps: int[], customers: String[], webpages: String[]) → String[]Examples
Example 1
timestamps = [1,2,3,4,5,6]customers = ["u1","u1","u1","u2","u2","u2"]webpages = ["home","search","cart","home","search","cart"]return = ["home>search>cart"]Both customers produce home, search, cart, so it has score two and is the only sequence.
Example 2
timestamps = [1,2,3,4,5,6,7]customers = ["u1","u1","u1","u1","u2","u2","u2"]webpages = ["a","b","a","c","a","b","c"]return = ["a>b>c","a>a>c","a>b>a"]a>b>c has score two. The score-one ties are resolved lexicographically.
Example 3
timestamps = [8,2]customers = ["u1","u2"]webpages = ["home","cart"]return = []No customer has three visits, so no sequence exists.
Constraints
1 <= timestamps.length = customers.length = webpages.length <= 60.- All timestamps are distinct integers from
1through10^9. - Customer IDs and webpage names are nonempty lowercase alphanumeric strings of length at most
20. - Webpage names do not contain
>.