/**
* 1152. Analyze User Website Visit Pattern
* We are given some website visits: the user with name username[i] visited the website website[i] at time timestamp[i].
*
* A 3-sequence is a list of websites of length 3 sorted in ascending order by the time of their visits.
* (The websites in a 3-sequence are not necessarily distinct.)
* Find the 3-sequence visited by the largest number of users. If there is more than one solution,
* return the lexicographically smallest such 3-sequence.
*
* Example 1:
*
* Input: username = [“joe”,”joe”,”joe”,”james”,”james”,”james”,”james”,”mary”,”mary”,”mary”],
* timestamp = [1,2,3,4,5,6,7,8,9,10], website = [“home”,”about”,”career”,”home”,”cart”,”maps”,”home”,”home”,”about”,”career”]
* Output: [“home”,”about”,”career”]
* Explanation:
* The tuples in this example are:
* [“joe”, 1, “home”]
* [“joe”, 2, “about”]
* [“joe”, 3, “career”]
* [“james”, 4, “home”]
* [“james”, 5, “cart”]
* [“james”, 6, “maps”]
* [“james”, 7, “home”]
* [“mary”, 8, “home”]
* [“mary”, 9, “about”]
* [“mary”, 10, “career”]
* The 3-sequence (“home”, “about”, “career”) was visited at least once by 2 users.
* The 3-sequence (“home”, “cart”, “maps”) was visited at least once by 1 user.
* The 3-sequence (“home”, “cart”, “home”) was visited at least once by 1 user.
* The 3-sequence (“home”, “maps”, “home”) was visited at least once by 1 user.
* The 3-sequence (“cart”, “maps”, “home”) was visited at least once by 1 user.
*/
See solution to the problem on github here: https://github.com/zcoderz/leetcode/blob/main/src/main/java/amazon/medium/UserWebsitePattern.java
Observation:
The question has a lot of detail to it. Best to take this question one piece at a time and ask interviewer for clarification regarding the requirements. The question wants to find the tuple of sites visited most often in order of time they were visited. If two tuple of sites has the same frequency of visits then the smaller lexicographical tuple needs to be returned.
Further observations:
- Finding tuple of 3 sites: The tuple of sites a person visited can be found by permuting the list of sites a person visited.
- The set of sites a person visits can be added to a map where the key is user id and list is pair of sites by time.
- We can sort the sites by time they were visited before creating tuples so the order of sites in tuple is consistent.
- We can store the tuples in a map that is keyed off of the tuple with value as number of visits
- We can create a priority queue of tuples and visits which is ordered first by number of visits and then by the lexicographical order of the sites.
- The first element in the PQ will be our answer.
Logic:
- Add sites to a map keyed by user and pair of timestamp and site
- Process tuple of sites by user visit count
- Create a map with key as tuple and value as count
- Iterate through users
- Sort the pair of timestamp and site visits by timestamp
- For the list of sites create a tuple via permuting over the sites
- Add the tuple of sites to the map
- Create a priority queue of tuple and count pair
- Order the priority queue by count first and then by site tuple
- The first element in the priority queue is our answer
Here is the code for most visited logic:
public List<String> mostVisitedPattern(String[] username, int[] timestamp, String[] website) {
Map<String, List<Pair<Integer, String>>> userToSites = new HashMap<>();
//create a map from user to list of sites by time stamp
for (int i = 0; i < website.length; i++) {
List<Pair<Integer, String>> webSites = userToSites.computeIfAbsent(username[i], (l) -> new ArrayList<>());
webSites.add(new Pair<>(timestamp[i], website[i]));
}
Map<Tuple<String, String, String>, Integer> tupleToCount = new HashMap<>();
for (Map.Entry<String, List<Pair<Integer, String>>> mapEntry : userToSites.entrySet()) {
//iterate through the sites a user visited
Set<Tuple<String, String, String>> tuples = new HashSet<>();
List<Pair<Integer, String>> sitesByTime = mapEntry.getValue();
//sort sites by time so the priority per spec is correct
Collections.sort(sitesByTime, Comparator.comparingInt(a -> a.first));
//convert the sites to a set of tuples. use set so repeated site combinations are not double counted
convertSitesToTuples(tuples, sitesByTime, new LinkedList<>(), 0, 3);
//process new tuples and aggregate total into the count of tuples across users
for (Tuple<String, String, String> tuple : tuples) {
Integer count = tupleToCount.getOrDefault(tuple, 0);
tupleToCount.put(tuple, count + 1);
}
}
//add to PQ that's sorted by count and then the lexical order.
PriorityQueue<Pair<Tuple<String, String, String>, Integer>> pq = new PriorityQueue<>(
(l, r) -> {
if (l.second.equals(r.second)) {
String a = l.first.toString();
String b = r.first.toString();
return a.compareTo(b);
} else {
return r.second.compareTo(l.second);
}
});
for (Map.Entry<Tuple<String, String, String>, Integer> entry : tupleToCount.entrySet()) {
pq.add(new Pair<>(entry.getKey(), entry.getValue()));
}
//get the first element from PQ which the question is asking for.
Tuple<String, String, String> tp = pq.poll().first;
List<String> data = new ArrayList<>();
data.add(tp.first);
data.add(tp.second);
data.add(tp.third);
return data;
}
Here is the code for generating the tuple of sites:
void convertSitesToTuples(Set<Tuple<String, String, String>> tuples, List<Pair<Integer, String>> sites,
LinkedList<String> siteComb, int index, int target) {
if (siteComb.size() == target) {
Tuple<String, String, String> tuple = Tuple.of(siteComb.get(0), siteComb.get(1), siteComb.get(2));
tuples.add(tuple);
return;
}
int finalIndex = target - siteComb.size();
for (int i = index; i <= (sites.size() - finalIndex); i++) {
siteComb.add(sites.get(i).second);
convertSitesToTuples(tuples, sites, siteComb, i + 1, target);
siteComb.removeLast();
}
}
The code relies on a utility Tuple class.