讨论一道面试题

* Problem statement: Given a list of shopping list(a list of products that customer purchased in one transaction), find out frequent itemset(K=2) and print them out ordered by frequency.
K is the size of the itemset.
Input example:
TID1: [P1, P2], TID2:[P2, P3], TID3:[P1, P2, P3], TID4:[P2, P3, P4]
Output example:
[P2, P3] => 3
[P1, P2] => 2
[P1, P3] => 1
[P2, P4] => 1
[P3, P4] => 1
**/


想问下大佬力扣有类似题的题号吗？谢谢

没遇到过特别类似的题目。我的解题思路是：

1，定义一个Map，遍历所有shopping list，记录每个product出现的频率。
P1->2
P2->4
P3->3
P4->1
2，用backtracking方法，得到一个item=K（题目中是2）的itemset的list。
[P1,P2]
[P1,P3]
...
3，每个itemset的fre就是itemset中每个product的fre最小值

hongkliu 发表于 2021-02-02 11:28:33
没遇到过特别类似的题目。我的解题思路是：

1，定义一个Map，遍历所有shopping list，记录每个product出现的频率。

想问下第二步怎么回溯得到itemset，以及第三步我看了下如果只是单纯按照每个p的最小值是不对的，是个排列组合问题不是单纯取最小值，比如p1p3就不是2而是1

我是这么想的
1. Build a hashmap where key is the product id and value is a list of order ids
2. Loop through all combinations of product ids, update the counter based on order id overlaps

可以试着遍历所有tids，在每一个tid中，找出所有pair，pair中两个数按序排一下，以pair作为key，建一个map统计出现次数，然后排序输出。时间复杂度为O(mn^2),m 为tid数目，n为最长tid长度。
不知道有没有更快的办法。另外这里k固定为2，还好说。如果k>=2且长度可变，要求找所有组合，那就麻烦了

shshrosh 发表于 2021-02-02 15:26:27
可以试着遍历所有tids，在每一个tid中，找出所有pair，pair中两个数按序排一下，以pair作为key，建一个map统计出现次数，然后排序输出。时间复杂度为O(mn^2),m 为tid数目，n

K是个输入变量，input variable