首页 新闻 论坛 群组 Blog 文档 下载 读书 Tag 网摘 搜索 .NET Java 游戏 视频 人才 外包 培训 数据库 书店 程序员
中国软件网
欢迎您:游客 | 登录 注册 帮助
    • 百度面试题 很有学习意义 各位讨论讨论哈。。。。 [已结贴,结贴人:wjc_hit]
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    发表于：2008-05-21 23:59:43 楼主
    1给你a、b两个文件，各存放50亿条url，每条url各占用64字节，内存限制是4G，让你找出a、b文件共同的url。、

    2给你一个单词a，如果通过交换单词中字母的顺序可以得到另外的单词b，那么定义b是a的兄弟单词。现在给你一个字典，用户输入一个单词，让你根据字典找出这个单词有多少个兄弟单词。  （这道题面试官说有O(1) 的解法，。。。。。）

    3五桶球，一桶不正常，不知道球的重量和轻重关系，用天平称一次找出那桶不正常的球。


    20  修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • oo
    • 等级:
    发表于：2008-05-22 09:28:181楼 得分:0
    2,可以对字典做预处理吗？

    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    发表于：2008-05-22 09:49:132楼 得分:0
    2肯定需要预处理；

    兄弟单词的每个字母的个数是一样的；每个字母的个数一样的单词互为兄弟；
    兄弟单词的数目以 “ 每个字母的个数”为key 使用hash来保存，就可以做到o(1)


    3能有解？
    文字游戏？


    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • oo
    • 等级:
    发表于：2008-05-22 10:16:143楼 得分:10
    把单词里的字母排序后的串做HASH也可以
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    发表于：2008-05-22 11:32:234楼 得分:0
    1也是要预处理的。
    一个比较笨的方法：
    先对a，b分别进行外排序，然后顺序遍历比较a和b……
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    发表于：2008-05-22 11:35:005楼 得分:0
    1，如果用hash的话，4G的内存不够啊，怎么搞？一个url我们认为是128个字节，那4G内存就只能存1024*1024*1024/128=800万条url
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • oo
    • 等级:
    发表于：2008-05-22 13:05:266楼 得分:0
    1,内存放不到，可能需要借助外存
    （1），读取文件，计算HASH，按HASH值分段放入不同的文件，文件数可以比较多，两个文件的URL，分开不同的文件放（a1，a2,...，b1，b2，...），保存时可以把HASH值也保存进去，避免再次计算HASH值
    （2），对每一个HASH段，读出两个文件中的一个，比如a1，对HASH值有冲突的放一个连表里，然后读b1文件，取HASH值和URL，如果HASH值在a1中有，则进一步判断URL是否相同。
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    发表于：2008-05-22 14:04:337楼 得分:0
    你好啊 字典可以预处理
    你说的 兄弟单词的每个字母的个数是一样的；每个字母的个数一样的单词互为兄弟；
    兄弟单词的数目以 “ 每个字母的个数”为key 使用hash来保存，就可以做到o(1) 是什么意思 不是很明白。。。。
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    发表于：2008-05-22 14:16:438楼 得分:0
    关注一下
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    发表于：2008-05-22 15:08:009楼 得分:0
    一般都会想到hash  像你这样分段  是否  a1 要和b1,b2,...bn 都比较看看是否有交集，  a2 也要和b1,b2,...bn 都比较看看是否有交集， 。。。。
    这样好像效率不是很高  百度的面试基本上都要求给出最优的方法。。。
    各位 再想想哈  。。。
    对你们表示感谢。。
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    发表于：2008-05-22 15:16:3310楼 得分:0
    什么意思？？、

    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    发表于：2008-05-22 15:20:0311楼 得分:0
    我的想法是把 字典建成树（26种字母  26棵树） n个字母的单词有n！ 中组合 遍历树。。。。。
    不是很好。。。。 大家多提宝贵意见。。。。
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • oo
    • 等级:
    发表于：2008-05-22 15:30:1612楼 得分:0
    引用 9 楼 wjc_hit 的回复:
    一般都会想到hash  像你这样分段  是否  a1 要和b1,b2,...bn 都比较看看是否有交集，  a2 也要和b1,b2,...bn 都比较看看是否有交集， 。。。。
    这样好像效率不是很高  百度的面试基本上都要求给出最优的方法。。。
    各位 再想想哈  。。。
    对你们表示感谢。。


    a1只需要跟b1比较，因为a1和b1的HASH值在一个段，跟其他的HASH值不在一个段，肯定不会相同的。
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    发表于：2008-05-22 15:31:4813楼 得分:0
    分段的意思是说，根据同一个hash算法的结果来划分，比如采用0x0-0xFFFFF作为hash值，将a和b分别拆成1M个文件a_0-a_FFFFF和b_0-b_FFFFF个文件。如果a和b中有相同的url，它们必然处在相同的段里。这样只要a_0和b_0比较，a_1和b_1比较就可以了。平均每个文件包含5000个url，远远低于内存的限制，可以放在内存中运行。此时再使用什么方法，hash也好，排序也好，都不是问题了。该方法中，每个url在硬盘上读2次，写1次，是很高效的。

    如果因为数据分布问题，造成某个段特别大、超出内存范围的话，可对该段再hash一次（当然得换一个hash算法）。如果还不行（比如数千万条相同的url），就对这部分采用硬盘排序等方法。因为它们仅占很小的比例，不会对整体效率造成大的影响。
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    发表于：2008-05-22 19:38:1914楼 得分:0
    mark


    hash
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    发表于：2008-05-22 21:01:4115楼 得分:0
    引用 12 楼 oo 的回复:
    引用 9 楼 wjc_hit 的回复:
    一般都会想到hash  像你这样分段  是否  a1 要和b1,b2,...bn 都比较看看是否有交集，  a2 也要和b1,b2,...bn 都比较看看是否有交集， 。。。。 
    这样好像效率不是很高  百度的面试基本上都要求给出最优的方法。。。 
    各位 再想想哈  。。。 
    对你们表示感谢。。


    a1只需要跟b1比较，因为a1和b1的HASH值在一个段，跟其他的HASH值不在一个段，肯定不会相同的。


    哦 明白 高手  是否有更优的？
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    发表于：2008-05-23 09:30:5816楼 得分:0
    mark
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    发表于：2008-05-23 10:31:4517楼 得分:0
    第二题不知用位图能否解决：
    定义一个int型变量，将其初值设为0，26个字母，如果单词含有其中一个字母，就将对应位设为1，例如am，它对应的值就是0X1001，然后查找，对每个单词的对应的位图进行设置，如果结果和要查找的单词的位图相等，找到.
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • oo
    • 等级:
    发表于：2008-05-23 10:41:1518楼 得分:0
    引用 17 楼 ybConfi 的回复:
    第二题不知用位图能否解决：
    定义一个int型变量，将其初值设为0，26个字母，如果单词含有其中一个字母，就将对应位设为1，例如am，它对应的值就是0X1001，然后查找，对每个单词的对应的位图进行设置，如果结果和要查找的单词的位图相等，找到.

    一个字母在一个单词里可能有多个，只用一个int做位图的话无法表示

    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    发表于：2008-05-23 11:02:1219楼 得分:0
    谢谢楼上更正！
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    发表于：2008-05-23 11:14:2820楼 得分:0
    可不可以用26个元素的int数组呢？那样性能差一些，应该能解决！
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    发表于：2008-05-23 12:38:0621楼 得分:0
    ls的那种方法应该不是o1吧？
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    发表于：2008-05-23 15:38:1022楼 得分:0
    引用 17 楼 ybConfi 的回复:
    第二题不知用位图能否解决：
    定义一个int型变量，将其初值设为0，26个字母，如果单词含有其中一个字母，就将对应位设为1，例如am，它对应的值就是0X1001，然后查找，对每个单词的对应的位图进行设置，如果结果和要查找的单词的位图相等，找到.


    am为什么对应0x1001 ？？？？？ 什么意思 请具体点
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    发表于：2008-05-23 16:55:1623楼 得分:0
    引用 18 楼 oo 的回复:
    引用 17 楼 ybConfi 的回复:
    第二题不知用位图能否解决： 
    定义一个int型变量，将其初值设为0，26个字母，如果单词含有其中一个字母，就将对应位设为1，例如am，它对应的值就是0X1001，然后查找，对每个单词的对应的位图进行设置，如果结果和要查找的单词的位图相等，找到.

    一个字母在一个单词里可能有多个，只用一个int做位图的话无法表示

    该方法行不通
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    发表于：2008-05-24 11:31:5524楼 得分:0
    貌似第三题。。。。至少要称两次吧，不懂。。。。。
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    发表于：2008-05-24 15:57:2425楼 得分:0
    回答： 3五桶球，一桶不正常，不知道球的重量和轻重关系，用天平称一次找出那桶不正常的球
    从五桶里分别取出1，2，3，4，5个球。重量如果是16说明是第一桶，如果17说明是第二桶。。。。
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    发表于：2008-05-24 23:32:1426楼 得分:0
    引用 25 楼 longzhanyuye2008 的回复:
    回答： 3五桶球，一桶不正常，不知道球的重量和轻重关系，用天平称一次找出那桶不正常的球
    从五桶里分别取出1，2，3，4，5个球。重量如果是16说明是第一桶，如果17说明是第二桶。。。。



    注意：不知道球的重量和轻重关系
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    发表于：2008-05-25 11:06:3327楼 得分:0
    3五桶球，一桶不正常，不知道球的重量和轻重关系，用天平称一次找出那桶不正常的球
    从五桶里分别取出1，2，3，4，5个球。重量如果是16说明是第一桶，如果17说明是第二桶。。。。
      怎么算出来的？
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    发表于：2008-05-27 09:52:1628楼 得分:0
    第三个题如果有一桶全都不正常且重量一样就有戏
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    发表于：2008-05-27 16:51:5929楼 得分:0
    学习了
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    发表于：2008-05-27 20:35:2930楼 得分:0
    引用 25 楼 longzhanyuye2008 的回复:
    回答： 3五桶球，一桶不正常，不知道球的重量和轻重关系，用天平称一次找出那桶不正常的球
    从五桶里分别取出1，2，3，4，5个球。重量如果是16说明是第一桶，如果17说明是第二桶。。。。

    天平有砝码吗？
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    发表于：2008-05-27 22:05:1131楼 得分:0
    mark

    第二题
    不能够对字典做操作

    求单词的全排列，通过字典查是否存在
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    发表于：2008-05-28 09:00:4232楼 得分:0
    1给你a、b两个文件，各存放50亿条url，每条url各占用64字节，内存限制是4G，让你找出a、b文件共同的url。
    这个关键要减小IO次数，先排序再找需要遍历4次，是线性的，应该可以接受。具体实践时再考虑对4G的充分利用优化一下。

    2给你一个单词a，如果通过交换单词中字母的顺序可以得到另外的单词b，那么定义b是a的兄弟单词。现在给你一个字典，用户输入一个单词，让你根据字典找出这个单词有多少个兄弟单词。  （这道题面试官说有O(1) 的解法，。。。。。）
    构造特征向量：v=II pi
    II为连乘，pi为第i素数，i为字母序号

    3五桶球，一桶不正常，不知道球的重量和轻重关系，用天平称一次找出那桶不正常的球。
    造币厂问题，5太小了，easy.
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    发表于：2008-05-28 09:21:2233楼 得分:0
    mark
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    发表于：2008-05-28 20:05:1834楼 得分:0
    第三题真的是造币厂问题吗？请注意“不知道球的重量”。
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    发表于：2008-05-29 12:09:1635楼 得分:0
    引用 34 楼 Vitin 的回复:
    第三题真的是造币厂问题吗？请注意“不知道球的重量”。

    呵呵，没看清题。

    3五桶球，一桶不正常，不知道球的重量和轻重关系，用天平称一次找出那桶不正常的球。
    天平称一次，可以有两种情况：
    1、平衡 ；2；不平衡
    平衡时，如想鉴别异常球，只有一种可能，即正常的4桶均有球参与了称重，而异常的没有球参与称重。
    所以称重时，天平上至少有来自4个桶的球。
    不平衡时，无妨设同一桶只在一侧。至少有一侧有两种以上球。故无法判别。
    即使知道球的轻重，一次应该也无法判别
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天