IT笔记.pdf

1. 十月百度:一个数组保存了 N 个结构,每个结构保存了一个坐标,结构间的坐标都不相
同,请问如何找到指定坐标的结构(除了遍历整个数组,是否有更好的办法)?
2. 百度最新面试题:现在有 1 千万个随机数,随机数的范围在 1 到 1 亿之间。现在要求写
出一种算法,将 1 到 1 亿之间没有在随机数中的数求出来。
3. Alibaba 笔试题:给定一段产品的英文描述,包含 M 个英文字母,每个英文单词以空格分
隔,无其他标点符号;再给定 N 个英文单词关键字,请说明思路并编程实现方法
String extractSummary(String description,String[] key words)
目标是找出此产品描述中包含 N 个关键字(每个关键词至少出现一次)的长度最短的子串,
作为产品简介输出。(不限编程语言)20 分。
4. 搜狗:有 N 个正实数(注意是实数,大小升序排列) x1 , x2 ... xN,另有一个实数 M。需
要选出若干个 x,使这几个 x 的和与 M 最接近。请描述实现算法,并指出算法复杂度(参
考:第五章、寻找满足条件的两个或多个数)。
5. 迅雷:给你 10 台机器,每个机器 2 个 cpu,2g 内存,现在已知在 10 亿条记录的数据库
里执行一次查询需要 5 秒,问用什么方法能让 90%的查询能在 100 毫秒以内返回结果。
6. 给定一个函数 rand()能产生 0 到 n-1 之间的等概率随机数,问如何产生 0 到 m-1 之间等概
率的随机数?
7. 腾讯:五笔的编码范围是 a ~ y 的 25 个字母,从 1 位到 4 位的编码,如果我们把五笔的
编码按字典序排序,形成一个数组如下:
a, aa, aaa, aaaa, aaab, aaac, ……, b, ba, baa, baaa, baab, baac ……, yyyw, yyyx, yyyy
其中 a 的 Index 为 0,aa 的 Index 为 1,aaa 的 Index 为 2,以此类推。
1)编写一个函数,输入是任意一个编码,比如 baca,输出这个编码对应的 Index;
2)编写一个函数,输入是任意一个 Index,比如 12345,输出这个 Index 对应的编码。
8. 百度笔试题(下述第 8-12 题):linux/unix 远程登陆都用到了 ssh 服务,当网络
出现错误时服务会中断, linux/unix 端的程序会停止。为什么会这样?说下 ssh 的原理,解
释中断的原理。
9. 一个最小堆,也是完全二叉树,用按层遍历数组表示。
1. 求节点 a[n]的子节点的访问方式
2. 插入一节点的程序 void add_element(int *a,int size,int val);
3. 删除最小节点的程序。
10. a)求一个全排列函数:如 p([1,2,3]) ,输出: [123],[132],[213],[231],[321],[323] 。
b)求一个组合函数: 如 p([1,2,3]) ,输出:[1],[2],[3],[1,2],[2,3],[1,3],[1,2,3] 。
这两问可以用伪代码(全排列请参考这里的第 67