腾讯面试题1-蒲公英云

一看就知道TX不是搞.net的,如果你想去的话有几条路:
1,C(底层,成功率70%)
2,Javascript(网页,特别是ajax,纯手写,不用流行框架,成功率50%)
3,linux(网络,成功率40%)
4,oracle(数据库,成功率60%)
5,flash(主要是美工部分,成功率30%)
6,熟人(成功率90%)

1.某个大型的论坛系统，比如csdn论坛，或者网易论坛等，论坛发帖需要对内容进行过滤，已经知道过滤词表有3W个词汇。请设计比较优化的过滤系统。

以下是不好的方案
1.通过js在前台过滤，如果过滤词少的话是可以，3w个过滤词太大，不太适合在前台过滤。2.后台过滤，把论坛内容和3w个过滤词一对一比较，这样要循环3w词，效率是非常慢的。
2。腾讯面试的职位是QQ安全管家部门
初试时，首先通过手机聊了一堆，问了线程、进程等很多问题，比如：多进程的线程同步、共享内存的用法等。

笔试题1：
struct student{
virtual void fun(){
m_i = 0;
}
static int m_i;
};//…1
struct student{
void fun(){
m_i = 0;
}
static int m_i;
};//…2
int student::m_i = 0;
int _tmain(int argc, _TCHAR* argv[])
{
student *m_p = 0;
m_p->fun();
return 0;
}

1和2两种情况谁会崩溃
我的答案：1崩溃，2不会。原因1会根据m_p的指向的类型，再根据该类型的虚指针去虚函数获取函数指针，
可以写成该伪代码：m_p->ptr->fun(),显然ptr是未知的崩溃。

笔试题2：
有个byte字节（8位），统计1的次数，如1011 0010 1出现的次数是4（最大限度的优化）
我的答案：
int i=0;
for(int j=0;j<8;j++)\{ if(\_byte&1)i++; \_byte>>1;
}

最后就是上机题：
给个文件：文件里无数个单词，
用MFC编个对话框，在编辑框中输入字母，然后再下面的编辑框里能显示出最佳匹配的前100个单词
时间2小时

我的思路就是首先根据首字母读一次文件，将首字母符合的所有单词放入一个vector里，在根据排序需求对vector进行sort排序，根据后续的字母针对vector进行操作，每次输出仅从vector里取前100个。

做出来后，面试官问如果该文件里的单词已经排好序是否有其他更优方法，
当然有，空间换时间，对每个最近匹配的做个标记，开始标记、结束标记，

比如以a开头的做个标记以aa开头以aaa开头的都做标记，有点类似于广义表的形式，大集合包含小集合，小集合再包含集合。

不过面试官离开时没说消息通知的时间，所以回去后就接受另一家公司的offer。
面试大公司就这点烦心，没小公司来的爽快。
在这里总结一下，给后来的面试者提供点经验- -

3.QQ数据库的用户信息表现在有5亿多条记录，现在请给出怎么样设计，使通过QQ号码查询QQ用户信息的速度更快。。用怎么样的算法算出查询大概需要多少的系统开销。。

答：1.首先根据QQ号码的位数分段存储，不同位数的QQ号码再根据首位数字来分，比如，首位数字是1的放在一起存储，首位数字是2的一起存储。然后再根据第二位数字来存储，比如首位数字是1，第二位数字为1 的放在一起，以此类推，11，12，13，14，15.。。。。。。。

21，22，23，24，25.。。。。。

查询的时候首先根据QQ号码位数查询，其次根据号码的首个数字查询，然后在首个数字里面查到这个QQ号码，就可以了！时间是10的（位数-2）次方，然后再。

2.能不能用这样的方法来算。
1.先按位数分段
2.在当前段中排序，按QQ号的前2位查找。
3.在2的结果中，在按QQ号的后两位查找。
4.最后在3的结果中就能很快的找到，你要查找的号码，建议用视图，不要SQL语句，效率会快写。

3.仅仅考虑输入一个用户QQ号码，来查到数据库对应的其QQ号码的情况
（假设用户注册的时候,代码通过计算QQ号码是否为偶数和N的倍数的情况，在插入数据库）
QQ表(三个字段)
QQ号码是否为偶数 N的倍数
… … …
查询用户输入的号码是否为偶数且对应N的倍数的情况。
首先是否为偶数可以排除2.5亿种情况；
其次，如果令N=10W，则可以把查询范围缩小到10W内查询(当然，N取值的情况不知道10W是否为最佳值)
4.因为QQ号会存在长度和次序（密集型,比如一个号码段会有顺次规律）
第一索引：长度
第二索引：第一位数和最后一位数组合
符合第二索引则进行查找算法：第一位（HeadTag）与最后一位（TailTag）联合成两位数进行比较，
HeadTag—;TailTag++,继续比较…
example：112001，112002，112003，112004，112005，112006，112007
目标：112005，HeadTagTailTag=15
则进行一次遍历就可以查到目标。O（1），T（1）

4.这栋楼有很多公司，大家多是9点上班，只有4部电梯，如果你是电梯管理员怎么样合理安排他们上楼。。

答：1.可以安排一部电梯只到单层，一部到双层，还有一部三层以下不到，还有一层只到顶层。

2.三楼以下不可以做电梯，自己走楼梯，一部到4层，一部到5层，一部到6层，一部到7层。

3.分“班车” 假如办公楼30层。
班车1：3-11层，单数层停（人数>6人，开）
班车2：12-22层，单数层停（人数>12，开）
班车3：23-30层，单数层停（人数>12，开）
班车4：混乱行，1-30任意停。可用于紧急情况.等

5.两个整数数组，a[n]、b[m],n>m,找出数组a[n]中有，b[m]中没有的数。大家来讨论讨论，用几种方法解决，看看哪种方法最好，效率最高

答：1.a,b 两数组都做升序排序（降序也可以）
2.比较A，B两数组中第一个数大小，如果A>B，则B++（取B的下一个元素）；如果A<B，则A++（取A的下一个元素），直到比较相等的时候，这样可以舍掉前面的部分，使各数组的大小减少
3.然后递归2
目的是不断的缩小数组的范围，达到减少比较的次数的目的

对b数组搞快速排序……然后依次去a数组里面的数，在b数组里面玩二分折半查找…

6.给你一批电话号码，每个电话号码都有它的归属地，让你设计一个系统，能够跟据电话号码得到个的归属地。
1我给的答案是这样的：
定义一个电话号码以及归属地的结构体，然后以电话号码为关键值，这个结构体为值建立一个哈西表，需要的时候就用电话号码为关键值去查找就行了。
可是面试官让我换一种思路，用另外的方法实现，然后我问他是不是不可以用到标冷库，算法全部自己写，他却说可以用，于是我的理解就是不应该用key-value的方式来实现了，那应该用什么方法来实现这个查找呢？请同学们给个思路，谢了

2如果可以用STL，那就用mutimap，或者set什么的，一个归属地一个集合，给号码时，直接遍历所有集合（不是遍历元素）进行查找

3我觉得可以定义一个电话号码以及归属地的结构体，这个电话号码只是其电话号码的段数，首先找到要查询号码的段数，然后就可以找到其归属地了！

7.数据库中有两个字段 id, sorce.假设sorce的取值范围是 5-10.

　　按照以下概率实现sorce数据的更新。

　　5(25%) => 6 5(25%) => 7

　　6(20%) => 7

　　7(25%) => 8 7(25%) => 6

　　8(10%) => 6 8(25%) => 9

　　9(15%) => 8 9(20%) => 10

　　10(25%) => 9

要求考虑性能及扩展性。写出概率分布相关代码。

functiongetChangeNum($oldNum){

if($oldNum<5||$oldNum>10){ returnfalse; }

$randArr=array(5=>array(25=>6,50=>7),6=>array(20=>7),7=>array(25=>8,50=>6),8=>array(10=>7,35=>9),9=>array(15=>8,35=>10),10=>array(25=>9),);

$arr=$randArr[$oldNum];

$random=rand(1,100);

foreach($arras$k=>$v){ if($random<$k){ return$v; } }returnfalse; }

或者：

$updateArray=array(‘5.25’=>’6’,’5.25’=>’7’);foreach($updateArrayas$k=>$v){ $ks=explode(‘.’,$k,2);$sql=”update table set field=’{ $v}‘ where field={ $ks[0]} and round(rand(),2) <={ $ks[1]}“;$db->query($sql); }

8.今天去腾讯实习生面试，面试官给了一个题目。
现在有30张表，每张表记录了当天的登录用户信息（一个用户由于时间不同可以有多项），每张表大约有8亿项。现在要求使用SQL操作查找出这个月登陆次数最多的前N个用户。8亿数据，不建索引，那查询起来得花多少时间呀，太恐怖了！
答：1、海量数据，需要归并排序吧。任一数据结构的教材里都有吧
首先在每一张表内合并同类项（统计每一个帐号的登录次数）然后再依次两两比较30张表格，如有相同的表项，合并之，——把同一个帐号的登录次数加起来，（不同的则不管）。也就是各个表格之间做一下数据同步。最后将30张表格的前十名都提出来，单独比较。

2、1、如果一个月中每天一张表的话，记录每天登陆的次数id,每天登陆的时间date,把每天的汇总结果汇总到中间的表中，然后汇总每张表的数据数据在做查询汇总了。这样的效率也不会太低。
2、最好每张表都要建立索引了,id主键索引了。
3、数据量大的最好还是放在中间表处理。

3、把任务分发给N台服务器分别处理数据量，然后再把每台统计出来的结果综合一下，估计速度很快。

4、首先我这样做一个统计；
1、做一个中间表，每一天到23：59：59 这个点中执行一个job 做个统计，将这一天登录次数最多的用户的用户插入到这个中间表里去，每一天到23：59：59都会去执行一次这个job ，所以到这个月底我们在针对这个中间表做一次统计，数据应该不会很多！直接就可以做个统计，查询出来这个月登录次数最多的用户！

5、我觉得每天做一个统计，比较靠谱，虽然有8亿个数据，将每天的都做一次统计。但是不能每天都取前N个，因为有可能有的人前一天登陆很少，后一天登陆很多，但是你把他前一天的登陆次数没有统计到，到后一天的时候怎么办？所以我觉得每天统计完了，就保存到临时表当中，不要取前N个，然后统计完这个月的每一天，再统计整个月的，再取这个月的前N个。

6、createtablelog1 ( idintidentity(1,1), uidint, logTimedatetimedefault(getdate()) )

createtablelog2 ( idintidentity(1,1), uidint, logTimedatetimedefault(getdate()) )

--create……

createtablelog30 ( idintidentity(1,1), uidint, logTimedatetimedefault(getdate()) )

selecttop10uid,sum(logCount)aslogCountfrom(

selecttop10uid,count(1)aslogCountfromlog1wheredatediff(year,logtime,getdate())=0anddatediff(month,logTime,getdate())=0groupbyuid

Union

selecttop10uid,count(1)aslogCountfromlog2wheredatediff(year,logtime,getdate())=0anddatediff(month,logTime,getdate())=0groupbyuid

--union ……….

Union

selecttop10uid,count(1)aslogCountfromlog30wheredatediff(year,logtime,getdate())=0anddatediff(month,logTime,getdate())=0groupbyuid )

UloggroupbyuidorderbylogCountdesc

7、貌似大伙说的大部分是每天统计的办法，说下我的想法

这些表里，基本的索引还是必须的
要查出最多登陆的N个人，可以把表根据不同条件拆成多个部分，然后查出每个部分的最多登陆的N个人，最后把所有子集的数据合并统计下，得出最终的排行列

--合并统计
select SUM(cou) as sum,userid from (

--根据不同条件统计表数据子集的前N个人
select * from (
SELECT TOP N COUNT(1) as cou,userid
FROM userlogin_table1 where logintime > stateMonth and logintime < endMonth
--就当是QQ号吧，要不然根据其它条件划分子集，不过一定要有索引
and userid like ‘100%’
group by userid
order by cou desc) as temptable1

union

select * from (
SELECT TOP N COUNT(1) as cou,userid
FROM userlogin_table1 where logintime > stateMonth and logintime < endMonth
and userid like ‘101%’
group by userid
order by cou desc) as temptable1

union
…
…
)as table1
group by userid

…
…

什么多线程并发运算啊，能用的也都用上

9、20亿个无符号int数(应该存在文件里吧)，范围0~2^32-1 ,给2G内存，如何排序，不要用写入硬盘文件之类的辅助办法

答：根据位图算法来，编程珠玑2里面有详解。

这个不是讨论过了的问题么。
512M内存，一个位对应一个正整数，
依次读书40E个正整数，设置相应的标志位
然后为1的就是存在的位0的就是不存在的

20/8=2.5亿-—只需要256MB内存

40亿个只需要512MB内存。

10、hibernate级联更新的目的和好处？（级联的目的和好处）

hibernate，我很久没用了！
hibernate级联更新，如果设置了级联更新cascade，它的取值有：
1：all,对所有操作级联
2：none,对所有操作都不进行级联(设这个就没含义了)
3：save-update,对更新操作时级联
4：delete,对删除操作级联
两个有关联的对象就会设置这个属性，比如两张表中有主外键关系，那么在删除主表里的数据时就要删除相应子表中的数据，所以这个时候设置了cascade为delete，那么就会自动删除！如果不设置那么我们就要手动的删除！我看了下书，就这样理解的。

hibernate级联，是cascade 级联的目的：
cascade=’delete’
举一个blog的例子：
如果你删除某用户，那么这个用户发表的日志、留言什么的都要跟着删除，
不要我们再一个一个的删除

好处就在级联更新让程序员在做更新操作的时候只需要关心最重要的表，例如删除父表信息被删除，子表信息不需要程序员手工去删除，级联更新的话就会帮你自动删除。一般选项是建议用Save-Update，不建议使用All。如果你希望一个操作被顺着关联关系传播,你必须在映射文件中指出这一点。