百度技术笔试试题及答案

1、 编程题
判断字符串 b 的所有字符是否都再字符串 a 中出现过，a,b都是可能包含汉字的字符串。b中重复出现的汉字，那么a中也要至少出现相同的次数。
汉字使用gbk编码（简单的所，用两个字节表示一个汉字，高字节最高位为1的代表汉字，低字节最高位可以不为1）。int is_include(char *a , char *b)返回0 表示没有都出现过，返回1表示都出现过。 见dev c is_inlude 效率版本暂时还没写出
2、 算法题
序列 seq=[a,b,…,z,aa,ab,…,az,ba,bb,…,bz,…,za,zb,…,zz,aaa,…]类似于excel的字母序排列，任意给一字符串 s=[a-z] (由a-z字符串组成的任意长度字符串)，请问s是序列seq的第几个字符串。

3、 系统设计
需求：需要引入用户对搜索结果相关性的评分，100分制。希望用户的打分能帮助搜索引擎排序，但又避免恶意投票、作弊等。请设计一个比较公平的评分系统。求两个链表是否有公共结点，如果有，求第一个公共结点O(1)空间，O(L1 L2)时间 见dev c share_list

4、往一个集合中不断加入元素，每次都打印加入之后的中位数 见dev c 中位数
5、一个<时间，ip>列表，求时间Y秒内ip出现次数超过指定数M的ip的列表 见dev c ip_list
6、n个7位电话号码，号码没有重复 请在2M的内存中对其排序 见dev c 外部排序
7、二叉树的叶子节点，从左到右把叶子节点链接起来 见dev c 链接叶子节点

8、一个字典，用户输入一个串，请在字典中找出所有和用户输入串是同组合串

9. 给定n个字符串s[0..n-1]，按照一定排列，首尾相连，连成一个长串。求出一种排列使得连成的长串是所有可能的长串中字典序最小的那个。打印出那种排列连成的长串。见dev c 最小字典序
10、把一个字符串转换成浮点数 见dev c atof
11、请实现两棵树是否相等的比较，相等返回，否则返回其他值，并说明算法复杂度。
数据结构为：
typedef struct_TreeNode{
char c;
TreeNode *leftchild;
TreeNode *rightchild;
}TreeNode;
函数接口为：int CompTree(TreeNode* tree1,TreeNode* tree2);
注：A、B两棵树相等当且仅当Root->c==RootB-->c,而且A和B的左右子树相等或者左右互换相等。见dev c 树相等

12、写一段程序，找出数组中第k大的数，输出数所在的位置。例如{2，4，3，4，7}中，第一大的数是7，位置在4。第二大、第三大的数都是4，位置在1、3随便输出哪一个均可。
函数接口为：int find_orderk(const int* narry,const int n,const int k)
见dev c 第k大的数及位置
11、现有一组共计N个固定的集合（N为万量级），每个集合有个从0开始递增的集合ID，每个集合包含1~M个TERM（M为0~100的量级），希望设计一个程序能够持续对外服务，输入是一个TERM数组，输出其中任意一个集合ID（如果该TERM数组包含该集合的所有TERM），如果找不到输出-1。要求：1，时间复杂度最优，能够在短时间内对大量输入逐个输出
2，实现具体的代码（可以是伪代码），其中常用的数据结构可以采用标准库。
3，给出时间复杂度和空间复杂度。
TERM组合集合的文件格式举例：
TERM_1 空格 TERM_2
TERM_1 空格 TERM_3
TERM_1 空格 TERM_3 TERM_4
输入的为TERM数组（说明：TERM为一个词，可能是中文，固定字符串表示）

12、求两个整数集合的公共元素

13、给定一个大于10000的整数，求如何分割使得分割后的数乘积最小？如12345分成12×3×4×5

14、给定一个图，求该图中是否有环。

15、求M/N的小数表示，如果有循环节，写出循环节的位置；

16、求一个字符串中的最长回文前缀

17、给定一个二叉树，求其中N（N>=2）个节点的最近公共祖先节点。每个节点只有左右孩子指针，没有父指针。

18、滑雪问题：Michael喜欢滑雪百这并不奇怪， 因为滑雪的确很刺激。可是为了获得速度，滑的区域必须向下倾斜，而且当你滑到坡底，你不得不再次走上坡或者等待升降机来载你。Michael想知道载一个区域中最长底滑坡。区域由一个二维数组给出。数组的每个数字代表点的高度。下面是一个例子
1 2 3 4 5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9
一个人可以从某个点滑向上下左右相邻四个点之一，当且仅当高度减小。在上面的例子中，一条可滑行的滑坡为24-17-16-1。当然25-24-23-...-3-2-1更长。事实上，这是最长的一条。
长度是25

19、给定一个整数n 求其二进制表示中1的个数

20、判定两个无向无环图是否同构