8月28号下午电面百度,分享一下所有的题目吧,一共面2轮,offer还不知道,自我感觉面的很一般。
一面
1. linux进程通信的方法
2. 线程同步(我扯到了 signal 和 criticalsection 的区别那些)
3. 二叉树,找到最大距离的两个节点的距离
4. 疯子上飞机: http://www.linuxidc.com/Linux/2012-10/72409.htm
5. 如何给网页归类(我回答的是基于关键词库,然后kmp检索,后来又扯一会kmp)
第二题编码:
int longest_road(node_t *root){
if(root == NULL)return 0;
int left_depth = longest_road(root->lc);
int right_depth = longest_road(root->rc);
longest = max(longest, left_depth + right_depth);
return max(left_depth + right_depth) + 1;
}
二面
1. 自我介绍
2. 自己说自己做的比较好的项目
3. 介绍一个你最熟悉的排序算法,我说堆排序,然后如何构建,如何排序,举例说明何时不是稳定的
4. 堆,栈,全局数据的区别(包括生命周期,分配规则等)
5. 证明n 可以表示成 n = 3^k +/- 3^x .. n可以表示成 3 的幂的组合。
例如 4 = 3^1 + 3^0 5 = 3^2 – 3^1 – 3^0. 就是说系数只能是1或者-1, 不能是其他的。
写给出算法,然后证明这种表示的唯一性。
6. n个数,最少用多少次比较可以找到最大的两个数 http://www.linuxidc.com/Linux/2012-10/72408.htm
7. 10亿 大小的url集合 a和b 如何求 a – b( 我只是给出哈希算法的大概实现,感觉他不是很满意)
8. 开放题,如果给网站做内容质量评价,例如评定网站的健康度。
再补充一个同学面过的:
给出一个数组,判定这个数组内的元素,是不是BST后根遍历的结果。很经典 代码如下:
- bool PostOrderTraversal(int data[], int low, int high)
- {
- if(low >= high)
- {
- return true;
- }
- int split = -1;
- int i;
- bool found = false;
- //to see if the data can be splited as ABC where c is the last one, all members in A < c, B > c
- for( i = low; i < high; i++)
- {
- if(data[i] > data[high] )
- {
- if(split == -1)
- {
- split = i;
- found = true;
- }
- }
- if(data[i] < data[high] && split != -1)
- {
- return false;
- }
- }
- if(! found )//only A < c or B > c;
- {
- return PostOrderTraversal(data, low, high-1);
- }
- else //recursive way
- {
- return PostOrderTraversal(data, low, split – 1) && PostOrderTraversal(data, split, high-1);
- }
- }