爱有几分 发表于 2008-12-22 11:16

好像挺难~

874 发表于 2008-12-25 10:53

第二个能不能用二叉排序树，也是n*logn*字符串匹配时间，不知道5分钟内能不能完成
菜鸟飘过

小飞侠 发表于 2009-1-4 12:21

QQ wants to do search engine?
1. I only know 粗鲁法

2. For approximate solution, use streaming algorithm like sticky sampling or lossy counting, 1 pass and O(logn) (n=10,000,000 here) space consumption. Use 128bit SHA1 hashing function set (using a hash function set to avoid collision) is the other solution I can come up with, still 1 pass, defficiency is using 32bit * 10million ~ 300MB space for maintaining counter space, not really bad for memory in nowadays.

For exact solution, I heard (not 100% sure) google using 'tries' (this is tree-like data structure) to index huge text record.

3. Typical application for dynamic programming.

These three are a little bit too difficult for undergraduate students. I do not think the testers can come up with a good answer without peeping the solutions on a research paper.

[ 本帖最后由 小飞侠 于 2009-1-4 12:37 编辑 ]

dreamfly 发表于 2009-1-9 19:26

太难了

kids 发表于 2009-2-13 20:44

分布式算法+自动机
logn

Mango 发表于 2009-3-5 00:04

真够变态的！！

nslk 发表于 2009-3-25 22:05

不懂...
页: 1 [2]
查看完整版本: 腾讯2面试题