新浪微博笔试题:找出共有2个以上标签的用户对

10 sec read

题目:给定sina微博的全部用户(1亿以上)和标签(uniq的标签30万左右)的关系, 系统找出共有2个或以上标签的用户对,并给出这些标签是哪些。

  • input:userid,taglist
  • output:userid,userid,con-taglist (sizeof(con_taglist)>=2)

数据示例

输入

  • AA,体育 新闻清华 百年校庆
  • BB,娱乐 八卦清华 新闻
  • CC,体育 娱乐新闻
  • DD,八卦 新闻娱乐

输出

  • AA,BB 清华 新闻
  • AA,CC 体育 新闻
  • BB,CC 娱乐 新闻
  • BB,DD 娱乐 八卦 新闻
  • CC,DD 娱乐 新闻

接下来就一起来想办法解决上面的难题。基于对于新浪微博的了解,以下内容可能会在实现中起到一些作用:

  1. 目前新浪微博每个用户最多可设置标签10个;
  2. 目前有相当数量的用户是没有设置标签的。

解决问题思路:(自己整理的笨办法,自己能力有限暂时想不到更好的方案)

  1. 删除没有标签的用户数据,这一操作可以先把一部分不需要纳入分析的数据给排除掉。具体数量未知。
  2. 建立标签到用户的倒排索引。从以上数据上来看,平均每个标签用户对应的用户ID链要小于10^8*10/30^4 = 3000,但同时要考虑热门标签的ID数量会非常的大。
  3. 去除倒排索引后只有一个用户数的标签,这个估计可以去除的量很少。
  4. 对于删除后没有标签的数据按ID大小进行排序。
  5. 对于用户依次取其标签,查找倒排索引,找到共有用户。(只查找倒排索引中比用户ID比自己大的用户)

基于以上的想法,考虑的新浪微博应该采用了 NOSQL存储,我们先假定具体数据格式如下:

  • {“userid”:123,”taglist”:[“体育”,”新闻”,”清华”,”百年校庆”]}
  • {“userid”:124,”taglist”:[“娱乐”,”新闻”,”清华”,”八卦”]}
  • {“userid”:125,”taglist”:[“娱乐”,”新闻”,”体育”]}
  • {“userid”:126,”taglist”:[“娱乐”,”新闻”,”八卦”]}

就上面的一些数据我尝试了下将上面的数据进行倒排索引。具体的Python实现方法(代码写的比较丑,对于python怎么使用MapReduce):

如果你有更好的解决方案,欢迎分享~

打赏作者
微信支付标点符 wechat qrcode
支付宝标点符 alipay qrcode

K-近邻算法KNN学习笔记

什么是K-近邻算法? K近邻法(k-nearest neighbor, k-NN)是1967年由Cover T
2 min read

使用Prophet进行时间序列预测

Prophet是Facebook开源的预测工具,相比ARIMA模型,Prophet真的是非常的简单。只要读入两
1 min read

采用时间序列预测股价变化

时间序列简介 在数学上,随机过程被定义为一族时间随机变量,即{x(t),t∈T},其中T表示时间t的变动范围。
5 min read

One Reply to “新浪微博笔试题:找出共有2个以上标签的用户对”

  1. 1. 第一步可以删除标签数目小于2的所以用户;
    2. 能否直接用频繁集挖掘?apriori

发表评论

电子邮件地址不会被公开。 必填项已用*标注