123 / 3 页下一页

[算法] （讨论）百度2010校园招聘网络笔试题 [复制链接]

daily_2

白手起家

论坛徽章:: 0

11楼 [报告]

发表于 2009-11-09 16:01 |只看该作者

回复 #1 scu_guzo 的帖子

看来《数据结构》应该学好才行啊，这门课很重要。

实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？

pripor

丰衣足食

论坛徽章:: 0

12楼 [报告]

发表于 2009-11-09 16:59 |只看该作者

经常不用

早忘了

实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？

fromheaven

白手起家

论坛徽章:: 0

13楼 [报告]

发表于 2009-11-09 18:18 |只看该作者

回复 #2 scu_guzo 的帖子

第二部分第一题有待商榷。u_int64 ref[20000000000]就已经是150G了。
海量数据的存储和查询应该还是采取经典的B+ Tree结构。以id作为unique primary key，建立index。index和data page不一定要同时存在于memory中，这样扛不住的。一般的数据库和OS都是底层有专门的buffer和disk manager两大模块按照某种策略FIFO，MRU进行读写。

实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？

scu_guzo

白手起家

论坛徽章:: 0

14楼 [报告]

发表于 2009-11-09 19:25 |只看该作者

回复 #13 fromheaven 的帖子

谢谢提醒哈，我是用win下的计算器算的，少看了个0....

实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？

mcemil

小富即安

论坛徽章:: 0

15楼 [报告]

发表于 2009-11-10 11:42 |只看该作者

第2个就是字典树啊。16个单词，全是小写，估计内存占用不会超过64M。
对给定的字符窜枚举它的子窜，找出存在的且最长的即可。
运算次数就是，就是 C(16,16)+C(16,15)+....C(16,2)+C(16,1) ，也就十几万次循环。

实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？

shang2010

腰缠万贯

论坛徽章:: 154

16楼 [报告]

发表于 2009-11-10 16:38 |只看该作者

baidu给多少时间？

实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？

皇家救星

家境小康

论坛徽章:: 0

17楼 [报告]

发表于 2009-11-11 00:02 |只看该作者

第一题第二小问或许可以这样做

对于给出的16个字母排序去重，结果记为A
遍历字典表，对每个单词排序去重，结果记为B
对于每个B 看是否是A的子集(由于A和B均是有序的，很容易判断)

这样做的效率是应该是O(n)级

第二题可以考虑把文件按唯一标志进行排序排序完后再对排序结果做索引(10行做一个索引，索引主键是唯一标志，键值是唯一标志对应行在文件中的位置)

查询时把索引放到内存中，先通过内存查出索引范围，再在范围中的10行数据中查找