Analyze User Website Visit Pattern

设计题, 给三个array, 分别是用户名, 访问时间和网址. 定义一个3seq是连续3个访问的网址, 求独立用户访问最多的3seq.

这个题超级tricky, 首先要构造3seq, 然后还要注意给的数据不是排序好的, 还要先排序. 最后求3seq的时候,我用”-“作为分隔符来方便给3seq做hash.

class Solution {
    class Pair {
        int c;
        String s;
        public Pair(String s, int c) {
            this.s = s;
            this.c = c;
        }
    }
    class Triple {
        int t;
        String s;
        String w;
        public Triple(String s, int t, String w) {
            this.s = s;
            this.t = t;
            this.w = w;
        }
    }
    public List<String> mostVisitedPattern(String[] username, int[] timestamp, String[] website) {
        int n = username.length;
        List<Triple> t = new ArrayList<>();
        for(int i = 0; i < n; i++) {
            t.add(new Triple(username[i], timestamp[i], website[i]));
        }
        Collections.sort(t,(a, b) -> (a.t-b.t));
        Map<String, List<String>> map = new HashMap<>();
        for(Triple tt : t) {
            map.putIfAbsent(tt.s, new ArrayList<>());
            map.get(tt.s).add(tt.w);
        }
        Map<String, Set<String>> countMap = new HashMap<>();
        for(Map.Entry<String,List<String>> e : map.entrySet()) {
            countMap.putIfAbsent(e.getKey(), new HashSet<>());
            countMap.get(e.getKey()).addAll(getSeq(e.getValue()));
        }
        Map<String, Set<String>> countMapRev = new HashMap<>();
        for(Map.Entry<String,Set<String>> e : countMap.entrySet()) {
            for(String s : e.getValue()){
                countMapRev.putIfAbsent(s, new HashSet<>());
                countMapRev.get(s).add(e.getKey());      
            }
        }
        List<String> res = new ArrayList<>();
        PriorityQueue<Pair> pq = new PriorityQueue<>((a, b) -> (a.c == b.c ? a.s.compareTo(b.s) : b.c - a.c));
        for(Map.Entry<String,Set<String>> e : countMapRev.entrySet()) { 
            pq.add(new Pair(e.getKey(), e.getValue().size()));
        }
        String ss = pq.poll().s;
        String[] strs = ss.split("-");
        for(String s : strs)
            res.add(s);
        return res;
    }
    private Set<String> getSeq(List<String> myArray) { 
        Set<String> res = new HashSet<>();
        for(int i = 0; i < myArray.size() - 2; i++) {
            for(int j = i + 1; j < myArray.size() - 1; j++) {
                for(int k = j + 1; k < myArray.size(); k++) {
                    res.add(myArray.get(i)+"-"+myArray.get(j)+"-"+myArray.get(k));
                }
            }
        }
        return res;
    } 
}