google笔试题 不解
数据集有300多万条记录：每条记录的格式如下：
作者1： paper1 paper2 paper 5
作者2： paper3 paper7 paper 9 paper11 paper15 paper 21
作者3： paper100 paper201
也就是一个作者名后面跟的是他写过的paper名。每个作者最少一篇paper，最多400篇paper。数据集有约300W条记录，即300w个作者名，要求就是找出哪两个作者具有协作关系，也就是经常一起paper，（可以假设两个作者一起写的paper数超过5篇就可以算是经常一起写paper，即具有协作关系）
写出大致算法或者伪代码。要求是重点考虑时间复杂性，越快越好。在提出两个作者后，如何考虑三个、四个作者具有的协作关系。
[解决办法]
找出哪两个作者具有协作关系?这个就比较麻烦了,最少时间复杂度要为O(n^2*m)吧(n:作者数,m:论文总数).
[解决办法]
问题就相当于数据挖掘里面的频繁项集的挖掘，用FP-tree就很好了
[解决办法]
倒排索引？
[解决办法]
集合找并集 hash处理
[解决办法]
我的想法如下
原理:用两个MAP来处理
实现:
1.建立map<paper,queue<author> > m_p2a,保存所有的输入数据,这样就可以获得对于同样的paper有哪些author
2.遍历所有m_p2a的所有元素,对于同一paper的queue<author>的所有元素对 (ai,aj)(ai<aj),建立协同工作map<pair<author,author>,cnt> m_res,将queue中的所有(ai,aj)添加到m_res中(m_res[pair(ai,aj)]++)
3.遍历m_res,将value大于5的键(pair<author,author>)输出即可.
复杂度分析: 设author个数为m,paper总数为n,所有author的paper数之和为p(可以重复)
m_p2a插入的复杂度为:O(p*logn)
m_res插入的复杂度为:O(n*m^2*logm)
m_res查询的复杂度为:O(m^2)
pp:
原本以为能想出什么高效的算法...写出来才发现...各种搓比...
[解决办法]
循环两次就行了。
首先循环一次，建立以paper为索引的查找序列，即paper1：作者n1,作者n2...
其次建立一个二维矩阵，横纵向均代表作者，初始为0。
然后再循环一次原数据，作者1->paper1->根据第一次循环建立的倒排文档查找其对应的所有作者，然后填入二维矩阵中数值+1。
循环完的那个对称2维矩阵中得每个数值就是作者之间合作数据。
复杂度是线性的。
用算法思路说明比较方便，果然是国外公司，题目简单，1分钟就能解决。换成百度指不定扔给你一个他们自己都解决不了的难题来忽悠你。
[解决办法]
hash处理？
[解决办法]
2个好处理
转置一下，join一下，再group by
3个的比较麻烦，要想想
[解决办法]
为什么要两个map 我觉得一个map就能搞定
[解决办法]
最坏情况下，这些作者互相都认识，都经常一些水论文，那最后就得存C(300w,2)条记录
比较理想的情况是这些记录是闭合的，那么对每个作者扫一遍他水过的论文里合作作者的名字，超过五次的就认为两个作者有JQ，放到结果集里。结果集可以不用判重，因为你可以规定作者对的顺序（比如字典序）。
比较DT的是比如
Ming Li:article1(Meimei Han),article2(Meimei Han)
Meimei Han:article3(Ming Li),article4(Ming Li),article5(Ming Li)
那么你可以预处理一遍这个数据集使之成为
Ming Li:article1(Meimei Han),article2(Meimei Han),article3(Meimei Han),article4(Meimei Han),article5(Meimei Han)
Meimei Han:article1(Ming Li),article2(Ming Li),article3(Ming Li),article4(Ming Li),article5(Ming Li)
这种形式。
简单来说就是扫描每个作者的好基友的时候要hash，但结果集不用hash