新浪微博笔试题:找出共有2个以上标签的用户对
题目:给定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 娱乐 新闻
- 目前新浪微博每个用户最多可设置标签10个;
- 目前有相当数量的用户是没有设置标签的。
删除没有标签的用户数据,这一操作可以先把一部分不需要纳入分析的数据给排除掉。具体数量未知。
建立标签到用户的倒排索引。从以上数据上来看,平均每个标签用户对应的用户ID链要小于10^8*10/30^4 = 3000,但同时要考虑热门标签的ID数量会非常的大。
去除倒排索引后只有一个用户数的标签,这个估计可以去除的量很少。
对于删除后没有标签的数据按ID大小进行排序。
对于用户依次取其标签,查找倒排索引,找到共有用户。(只查找倒排索引中比用户ID比自己大的用户)
{“userid”:123,”taglist”:[“体育”,”新闻”,”清华”,”百年校庆”]}
{“userid”:124,”taglist”:[“娱乐”,”新闻”,”清华”,”八卦”]}
{“userid”:125,”taglist”:[“娱乐”,”新闻”,”体育”]}
{“userid”:126,”taglist”:[“娱乐”,”新闻”,”八卦”]}
数据示例
输入
输出
接下来就一起来想办法解决上面的难题。基于对于新浪微博的了解,以下内容可能会在实现中起到一些作用:
解决问题思路:(自己整理的笨办法,自己能力有限暂时想不到更好的方案)
基于以上的想法,考虑的新浪微博应该采用了 NOSQL存储,我们先假定具体数据格式如下:
就上面的一些数据我尝试了下将上面的数据进行倒排索引。具体的Python实现方法(代码写的比较丑,对于python怎么使用MapReduce):
# -*- coding: utf-8 -*- tagDB = open('tag.txt','r') list = [s.strip() for s in tagDB.readlines()] result={} for i in list: data = eval(i) userid = data['userid'] taglist = data['taglist'] for tag in taglist: if result.has_key(tag): result[tag].append(userid) else: result[tag] = [userid] print result tagDB.close()
如果你有更好的解决方案,欢迎分享~
建议继续学习:
- 腾讯-1亿个数据取前1万大的整数-题解答 (阅读:8886)
- 谷歌(Google)2011年校园招聘笔试题 (阅读:8836)
- 你是那10%可以实现二分查找算法的程序员吗? (阅读:6388)
- 15道使用频率极高的基础算法题 (阅读:5375)
- 有道实习生笔试总结 (阅读:4479)
- 2014网易前端开发笔试题笔记 (阅读:3792)
- 《百姓网公开笔试题:查询条件的子集判断》的一份 PHP 答卷 (阅读:2675)
- 百姓网公开笔试题:查询条件的子集判断 (阅读:2527)
- 百姓网公开笔试题结果展示 (阅读:2253)
扫一扫订阅我的微信号:IT技术博客大学习
- 作者:标点符 来源: 标点符
- 标签: 笔试
- 发布时间:2013-01-08 13:35:14
- [11] 解决 ubuntu 的 /etc/hosts
- [9] 文言文白话文互转:文言文转白话文(现代文),
- [7] 领导需要比下属更懂技术吗?
- [7] Http/2知识图谱
- [7] 海量数据面试题举例
- [6] 活动 Web 页面人机识别验证的探索与实践
- [6] 近场通信 vs. 低功耗蓝牙:如何抉择
- [6] 一个 VLA (可变长度数组)的实现
- [6] arduino-蓝牙各种版本类型及费用对比
- [6] 聚类算法之ISODATA