腾讯2面试题

我想飞

一面的时候，问题一个比一个难，最后光荣牺牲了，据进入2面的朋友回来说题目更变态：
腾讯2面试题，你说会做几个？

1、设计一个魔方（六面）的程序。
2、有一千万条短信，有重复，以文本文件的形式保存，一行一条，有重复。请用5分钟时间，找出重复出现最多的前10条。
3、收藏了1万条url，现在给你一条url，如何找出相似的url。（面试官不解释何为相似）

iptton

什么职位？

zaijzhgh

第二题：如果用排序的话，不知道五分钟能不能排完？一千万条太多了。。。
感觉第三题和第二题会有相似的地方。。。

tremenpig

第二题可以先将文本里面的内容导入Oracle数据库，再用分组排序提取前10条记录

iptton

用数据库的话，还编什么程...直接考你SQL就得了

gyCai

看你短信多长了。
假设70个字符一条短信，那就hash计数，外加扫描冒泡留下前面10个。
开销最大的是1kw*70=700M字符串的值hash计算了。

gyCai

小于前十名的过，大于前十名的留下。
hash留下的为计数，然后......
空间开销很大。速度不计字符串读取的话秒级达不到，也应该能够达到5分钟内的要求了。

gyCai

url相似，会不会跟卷积牵扯上什么关系？
不懂。

zaijzhgh

原帖由 gyCai 于 2008-11-7 16:11 发表
看你短信多长了。
假设70个字符一条短信，那就hash计数，外加扫描冒泡留下前面10个。
开销最大的是1kw*70=700M字符串的值hash计算了。

hash计数的话发生碰撞的几率会很大，这样一来效率也会大打折扣的。。。不知道1KW条还能不能用hash表。。。

kids

第二个：排序 qsort      o(nlogn)     10^7*lg10^7  在统计一下，不会超过5分钟 一分钟都不用
第三：https://www.gdutbbs.com/thread-262473-1-1.html
          可以按协议排，再按区域网络排，再按网站名排
          再按子页排
         
魔方是个啥东西？

gyCai

1000W条记录，qsort，还要字符串，你试试看用不用5分钟.

DieIng

第一个不懂。
第二个如果nlgn可以过的话。可以用红黑树搞吧。就是模拟c++的stl的map。。
第三个。。后缀数组可以过吧。或者水一些的数据。求LCS都可以？

DieIng

原帖由 kids 于 2008-11-9 18:55 发表
第二个：排序 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的话。相似度极其高。你的算法会把他们分开的

kids

原帖由 DieIng 于 2008-11-19 21:18 发表

字符串的排序很慢的。nlgn*length(s)。。。。
第三个如果是http://aaa0aaa.com和htap://aaa0aaa.com的话。相似度极其高。你的算法会把他们分开的

第一个我错了，
第二个在协议处理的时候就把他们分开了，不过还是太慢

kids

找出长度一样并且 第一个字符一样 的 前 二十一种长度的，
再对每一种一样长的 随机抽取某些位 匹配

大概

大飞猪

一个都不会

[ 本帖最后由 大飞猪 于 2008-12-5 17:47 编辑 ]

kids

2、有一千万条短信，有重复，
以文本文件的形式保存，
一行一条，
有重复。请用5分钟时间，找出重复出现最多的前10条。

一千万条 的文本
hash会不爆，不会的话，直接hash

kids

2、有一千万条短信，有重复，
以文本文件的形式保存，
一行一条，
有重复。请用5分钟时间，找出重复出现最多的前10条。

想到一个，大家鄙视下。

文本保存的，直接当成读二进制文件出来，每一行（一行不会超过20字符）分割成 几部分，变成数字，直接做数字的处理

kids

1、设计一个魔方（六面）的程序。

这个不知道要求是不是 ，做一个魔方程序，而不是魔方求解程序。

[ 本帖最后由 kids 于 2008-12-5 20:03 编辑 ]

kids

直接用 Oracle 查询，给数据库去处理