百度面试题

百度面试题1.一个int数组,里面数据无任何限制,要求求出所有这样的数a[i],其左边的数都小于等于它,右边的数都大于等于它。能否只用一个额外数组和少量其它空间实现。这道题的解答请看下一篇日志2.一个文件,内含一千万行字符串,每个字符串在1K以内,要求找出所有相反的串对,如abc和

大家好,又见面了,我是你们的朋友全栈君。

1.一个int数组,里面数据无任何限制,要求求出所有这样的数a[i],其左边的数都小于等于它,右边的数都大于等于它。能否只用一个额外数组和少量其它空间实现。

这道题的解答请看下一篇日志

2.一个文件,内含一千万行字符串,每个字符串在1K以内,要求找出所有相反的串对,如abc和cba。

当时怎么想的忘记了,现在重新思考一下,文件的大小上限是10G,不可能在内存操作了。考虑设计一种hash使得如果两个字符串维相反串能得出相同的hash值,然后用该hash将文件中的字符串散列到不同的文件中,再在各文件中进行匹配。比如这样的hash函数对字符串上所有字符的ascii求和,因为长度在1K以内,因此范围在int之内。更进一步,可以在上面那个hash后面再加一个字符串长度,可以得到更好的散列效果。

在各个单独文件中匹配时,如果采用的是第二种hash函数,那么该文件中的所有字符串都有相同的长度。如果hash效果好,那么这个文件应该小到可以在内存中进行操作了。将文件拷贝为两份,分别按照不同规则hash:第一份按前k位哈希,第二份将字符串的头尾进行颠倒后按前k位哈希(只是对于排序算法颠倒,不必实际颠倒)。这里的按前k位哈希只需要前k位相同能得到相同结果就好,比如第i位的ascii乘以2^i。两份拷贝中hash值相同的就很可能是要求的相反串对了,再进行实际匹配,工作量应该就可以接受了。

3.STL的set用什么实现的?为什么不用hash?

是用红黑树实现的,红黑树是一种平衡性很好的二分查找树。要使用hash的话,就需要为不同的存储类型编写哈希函数,这样就照顾不到容器的模板性了,而是用红黑树只需要为不同类型重载operator<就可以了。

修改于2011.9.2

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/159881.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • Ubuntu Mobile Demo at IDF Shanghai (英文)

    Ubuntu Mobile Demo at IDF Shanghai (英文)

  • 学习成功:中学生成就梦想的15堂必修课

    学习成功:中学生成就梦想的15堂必修课管斌全:《学习成功:中学生成就梦想的15堂必修课》笛案:自信国内外成功学的著作看过不少,但我只向人推荐管斌全的作品。以下内容节选自网络,个人有渠道还是买书好,也算是对作者的支持。fygub0231@sina.com0571-63311953013567128396该书已经出版了4个版本。  第一个版本是由北京海潮出版社(2002年10月)出版,书名为《我信我能我

  • 画完三角形再画谢尔宾斯基地毯

    画完三角形再画谢尔宾斯基地毯照样废话不说,看代码看注释importjava.awt.Color;importjava.awt.Dimension;importjava.awt.Graphics;importjava.awt.Toolkit;importjava.awt.event.MouseAdapter;importjava.awt.event.MouseEvent;import…

  • Linux终止进程的工具kill/killall/pkill/xkill/skill用法区别(转)

    Linux终止进程的工具kill/killall/pkill/xkill/skill用法区别(转)

  • releasecapture 函数_整理怎么解释

    releasecapture 函数_整理怎么解释setCapture一.什么是setCapture函数?MDN解释:在处理一个mousedown事件过程中调用这个方法来把全部的鼠标事件重新定向到这个元素,直到鼠标按钮被释放或者document.releaseCapture()被调用。函数作用:程序中主要是要捕获onmousemove和onmouseup事件语法:element.setCapture(retargetToElement);如果被设置为true,所有事件被直接定向到这个元素;如果是false,事件也可以在这

  • Vim搜索关键字[通俗易懂]

    Vim搜索关键字[通俗易懂]有以下两种方法Method1:/content默认从上往下查找只读模式下输入/content后回车按n向下查找按N向上查找Method2:?content默认从下往上查找只读模式下输入?content后回车按n向上查找按N向下查找实例/content用Vim打开文件后,直接输入/关键字并回车,定位到第一个关键字,之后通过n向下查找,通过N向上查找?

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号