腾讯2面试题
一面的时候，问题一个比一个难，最后光荣牺牲了，据进入2面的朋友回来说题目更变态：腾讯2面试题，你说会做几个？
1、设计一个魔方（六面）的程序。
2、有一千万条短信，有重复，以文本文件的形式保存，一行一条，有重复。请用5分钟时间，找出重复出现最多的前10条。
3、收藏了1万条url，现在给你一条url，如何找出相似的url。（面试官不解释何为相似） 什么职位？ 第二题：如果用排序的话，不知道五分钟能不能排完？一千万条太多了。。。
感觉第三题和第二题会有相似的地方。。。 第二题可以先将文本里面的内容导入Oracle数据库，再用分组排序提取前10条记录 用数据库的话，还编什么程...直接考你SQL就得了 看你短信多长了。
假设70个字符一条短信，那就hash计数，外加扫描冒泡留下前面10个。
开销最大的是1kw*70=700M字符串的值hash计算了。 小于前十名的过，大于前十名的留下。
hash留下的为计数，然后......
空间开销很大。速度不计字符串读取的话秒级达不到，也应该能够达到5分钟内的要求了。 url相似，会不会跟卷积牵扯上什么关系？
不懂。 原帖由 gyCai 于 2008-11-7 16:11 发表 https://www.gdutbbs.com/images/common/back.gif
看你短信多长了。
假设70个字符一条短信，那就hash计数，外加扫描冒泡留下前面10个。
开销最大的是1kw*70=700M字符串的值hash计算了。
hash计数的话发生碰撞的几率会很大，这样一来效率也会大打折扣的。。。不知道1KW条还能不能用hash表。。。 第二个：排序 qsort o(nlogn) 10^7*lg10^7在统计一下，不会超过5分钟 一分钟都不用
第三：https://www.gdutbbs.com/thread-262473-1-1.html
可以按协议排，再按区域网络排，再按网站名排
再按子页排
魔方是个啥东西？ 1000W条记录，qsort，还要字符串，你试试看用不用5分钟. 第一个不懂。
第二个如果nlgn可以过的话。可以用红黑树搞吧。就是模拟c++的stl的map。。
第三个。。后缀数组可以过吧。或者水一些的数据。求LCS都可以？ 原帖由 kids 于 2008-11-9 18:55 发表 https://www.gdutbbs.com/images/common/back.gif
第二个：排序 qsort o(nlogn) 10^7*lg10^7在统计一下，不会超过5分钟 一分钟都不用
第三：https://www.gdutbbs.com/thread-262473-1-1.html
可以按协议排，再按区域网络排，再按网站名排
...
字符串的排序很慢的。nlgn*length(s)。。。。
第三个如果是http://aaa0aaa.com和htap://aaa0aaa.com的话。相似度极其高。你的算法会把他们分开的 原帖由 DieIng 于 2008-11-19 21:18 发表 https://www.gdutbbs.com/images/common/back.gif
字符串的排序很慢的。nlgn*length(s)。。。。
第三个如果是http://aaa0aaa.com和htap://aaa0aaa.com的话。相似度极其高。你的算法会把他们分开的
第一个我错了，
第二个在协议处理的时候就把他们分开了，不过还是太慢 找出长度一样并且 第一个字符一样 的 前 二十一种长度的，
再对每一种一样长的 随机抽取某些位 匹配
大概 一个都不会
[ 本帖最后由 大飞猪 于 2008-12-5 17:47 编辑 ] 2、有一千万条短信，有重复，
以文本文件的形式保存，
一行一条，
有重复。请用5分钟时间，找出重复出现最多的前10条。
一千万条 的文本
hash会不爆，不会的话，直接hash 2、有一千万条短信，有重复，
以文本文件的形式保存，
一行一条，
有重复。请用5分钟时间，找出重复出现最多的前10条。
想到一个，大家鄙视下。
文本保存的，直接当成读二进制文件出来，每一行（一行不会超过20字符）分割成 几部分，变成数字，直接做数字的处理 1、设计一个魔方（六面）的程序。
这个不知道要求是不是 ，做一个魔方程序，而不是魔方求解程序。
[ 本帖最后由 kids 于 2008-12-5 20:03 编辑 ] 直接用 Oracle 查询，给数据库去处理
页:
[1]
2