百度面试题

百度面试题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)


相关推荐

  • 6.5——ADRC学习

    6.5——ADRC学习深刻理解PID1.    典型的传递函数——一阶惯性环节一个储能元件(如电感,电容)与一个耗能元件(如电阻)的组合,就能构成一阶惯性环节。如一个RC电路特点:当输入量发生突变时,输出量不能突变,只能按照指数规律逐渐变换,这就反应了该环节具有惯性。(也就是说,惯性环节的输出一开始并不与输入同步按比例变化,直到过渡过程结束,y(t)才能与x(t)保持比例。)而惯性环节的时间常数就是惯性的量度。 我们的…

  • 光猫桥接网速降低了_光猫桥接网速降低了

    光猫桥接网速降低了_光猫桥接网速降低了解决电信宽带下,光猫桥接后使用路由器拨号时宽带降速的问题。

  • activiti流程引擎_发动机的主要结构是什么

    activiti流程引擎_发动机的主要结构是什么https://blog.csdn.net/LiMing_0820/article/details/113247459

    2022年10月30日
  • Qt Quick中的信号与槽

    在QML中,在QtQuick中,要想妥善地处理各种事件,肯定离不开信号与槽,本博的主要内容就是整理Qt中的信号与槽的内容。1.链接QML类型的已知信号QML中已有类型定义的信号分为两类:一类

    2021年12月29日
  • 2022最新前端经典面试试题[通俗易懂]

    1,阐述清楚浮动的几种方式(常见问题)(1)父级div定义height原理:父级div手动定义height,就解决了父级div无法自动获取到高度的问题。优点:简单、代码少、容易掌握缺点:只适合高度固定的布局,要给出精确的高度,如果高度和父级div不一样时,会产生问题(2)父级div定义overflow:hidden原理:必须定义width或zoom:1,同时不能定义heigh…

  • C#调用windows api示例

    这是运行结果:Api函数是构筑Windws应用程序的基石,每一种Windows应用程序开发工具,它提 供的底层函数都间接或直接地调用了Windows API函数,同时为了实现功能

    2021年12月21日

发表回复

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

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