2013百度校招笔试真题以及解析(二)

本文涉及的产品
云解析 DNS,旗舰版 1个月
全局流量管理 GTM,标准版 1个月
公共DNS(含HTTPDNS解析),每月1000万次HTTP解析
简介: 1、一个单词单词字母交换,可得另一个单词,如army->mary,成为兄弟单词。提供一个单词,在字典中找到它的兄弟。

1、一个单词单词字母交换,可得另一个单词,如army->mary,成为兄弟单词。提供一个单词,在字典中找到它的兄弟。描述数据结构和查询过程。


思路1:使用hash_map和链表

(1)首先定义一个key,使得兄弟单词有相同的key,不是兄弟的单词有不同的key。例如,将单词按字母从小到大重新排序后作为其key,比如bad的key为abd,good的key为dgoo。
(2)使用链表将所有兄弟单词串在一起,hash_map的key为单词的key,value为链表的起始地址。
(3)开始时,先遍历字典,将每个单词都按照key加入到对应的链表当中。
(4)当需要找兄弟单词时,只需求取这个单词的key,然后到hash_map中找到对应的链表即可。

这样创建hash_map时时间复杂度为O(n),查找兄弟单词时时间复杂度是O(1)。

引用:原文链接

思路2:同样使用hash_map和链表

(1)将每一个字母对应一个质数,然后让对应的质数相乘,将得到的值进行hash,这样兄弟单词的值就是一样的了,并且不同单词的质数相乘积肯定不同。

注解: 根据数学定理:任何一个大于1的自然数N,都可以唯一分解成有限个质数的乘积 N=(P_1^a1)*(P_2^a2)……(P_n^an) , 这里P_1小于P_2小于…小于P_n是质数,且唯一。

例如 a=2 b=3 c=5 d=7 e=11… f(abcd)=2*3*5*7=210

然后字典里找乘积210的位数相同的一定是这5个字母组合的单词就是兄弟单词
(2)使用链表将所有兄弟单词串在一起,hash_map的key为单词的质数相乘积,value为链表的起始地址。
(3)对于用户输入的单词进行计算,然后查找hash,将链表遍历输出就得到所有兄弟单词。

这样创建hash_map时时间复杂度为O(n),查找兄弟单词时时间复杂度是O(1)。

引用:原文链接


2、一个url指向的页面里面有另一个url,最终有一个url指向之前出现过的url或空,这两种情形都定义为null。这样构成一个单链表。给两条这样单链表,判断里面是否存在同样的url。url以亿级计,资源不足以hash。


本题可以抽象为有环和无环情况下的链表交叉问题:

情况一:两条单链表均无环
  最简单的一种情况,由于两条链表如果交叉,他们的尾节点必然相等(Y字归并),所以只需要判断他们的尾节点是否相等即可。

情况二:两条单链表均有环
  这种情况只需要拆开一条环路(注意需要保存被设置成null的节点),然后判断另一个单链表是否仍然存在环路,如果存在,说明无交叉,反之,则有交叉的情况。

情况三:两条单链表,一条有环路,一条无环路
  这种情况显然他们是不可能有交叉的。


附:如何判断一条单链表是否存在环路,以及找出环路的入口

快慢指针:在表头设置两个指针fast与slow,fast指针与slow指针同时向前移动,但是fast每次移动2个节点,slow每次移动1个节点,若fast指向null或者fast==slow时停止,这时如果fast指向null,则说明没有环路,若fast==slow则说明有环路。

找环路入口:当fast==slow时,将fast重新指向表头。slow原地不动。然后fast和slow在同时以每次一个节点的速度向前移动,当他们再次重合时,就是环路入口。证明如下:

1.证明fast和slow肯定会重合
在slow和fast第一次相遇的时候,假定slow走了n步骤,环路的入口是在p步的时候经过的,那么有slow走的路径: p+c = n; c为p1和p2相交点,距离环路入口的距离;fast走的路径: p+c+k*L = 2*n; L为环路的周长,k是整数。显然,如果从p+c点开始,p1再走n步骤的话,还可以回到p+c这个点同时p2从头开始走的话,经过n步,也会达到p+c这点。

2.fast和slow在p+c点会重合,显然他们从环的入口点就开始重合。

转自http://iam42.iteye.com/blog/1680444

相关文章
|
3月前
|
vr&ar
简单易懂的 全景图高清下载方法以及原理简要解析(支持下载建E、720yun、酷雷曼、景站、酷家乐、百度街景原图)
这篇文章介绍了一种简单易懂的全景图高清下载方法,使用在线网站全景管家,支持下载包括建E、720yun、酷雷曼等多个平台的全景图原图,并简要解析了全景图的原理和制作方法。
简单易懂的 全景图高清下载方法以及原理简要解析(支持下载建E、720yun、酷雷曼、景站、酷家乐、百度街景原图)
|
3月前
|
机器学习/深度学习 自然语言处理 算法
【数据挖掘】百度机器学习-数据挖掘-自然语言处理工程师 历史笔试详解
文章汇总并解析了百度机器学习/数据挖掘工程师/自然语言处理工程师历史笔试题目,覆盖了多分类任务激活函数、TCP首部确认号字段、GMM-HMM模型、朴素贝叶斯模型、SGD随机梯度下降法、随机森林算法、强连通图、红黑树和完全二叉树的高度、最长公共前后缀、冒泡排序比较次数、C4.5属性划分标准、语言模型类型、分词算法、贝叶斯决策理论、样本信息熵、数据降维方法、分箱方法、物理地址计算、分时系统响应时间分析、小顶堆删除调整等多个知识点。
41 1
【数据挖掘】百度机器学习-数据挖掘-自然语言处理工程师 历史笔试详解
|
3月前
|
机器学习/深度学习 自然语言处理 算法
【数据挖掘】百度机器学习-数据挖掘-自然语言处理工程师 2023届校招笔试详解
百度2023届校招机器学习/数据挖掘/自然语言处理工程师笔试的题目详解
77 1
|
3月前
|
分布式计算 并行计算 大数据
【数据挖掘】百度2015大数据云计算研发笔试卷
百度2015年大数据云计算研发笔试卷的题目总结,涵盖了Hadoop、Spark、MPI计算框架特点、TCP连接建立过程、数组最大和问题、二分查找实现以及灯泡开关问题,提供了部分题目的解析和伪代码。
52 1
|
5月前
|
JSON 前端开发 API
程序技术好文:百度网盘真实地址解析(告别下载百度网盘)
程序技术好文:百度网盘真实地址解析(告别下载百度网盘)
404 0
|
6月前
|
Android开发
Flutter完整开发实战详解(六、 深入Widget原理),2024百度Android岗面试真题收录解析
Flutter完整开发实战详解(六、 深入Widget原理),2024百度Android岗面试真题收录解析
|
6月前
|
Android开发
71,字节跳动历年校招Android面试真题解析
71,字节跳动历年校招Android面试真题解析
|
6月前
|
Linux
百度搜索:蓝易云【深入解析Linux进程内存:VSS、RSS、PSS、USS及查看方式】
通过以上方法,你可以深入了解Linux进程的内存使用情况,包括VSS、RSS、PSS、USS等指标,帮助你进行性能优化和资源管理。
133 12
|
6月前
|
编解码 算法 前端开发
往年 | 大疆雷达算法校招笔试题目解析
往年 | 大疆雷达算法校招笔试题目解析
468 1
|
27天前
|
缓存 Java 程序员
Map - LinkedHashSet&Map源码解析
Map - LinkedHashSet&Map源码解析
62 0

热门文章

最新文章

推荐镜像

更多