百度网页搜索部rank团队4S面试

1. du和df的区别？

 du统计文件的大小，需要遍历整个目录；df统计磁盘的使用情况； du -s /dir  du -ab /dir   ; df -h /disk1

正常情况下两者数值接近，但如果存在打开文件的进程，而该文件被rm或者mv出去，则统计该目录du空闲空间大于df的空间空间；因为df记录磁盘使用大小，进程没有关闭文件，df默认磁盘仍被使用；而du遍历目录，发现文件已经被移走，所以不记录这部分大小；

2. 软链接和硬链接区别

硬链接： 和原文件指向同一个inode，可以用ls -il查看，生成一个一模一样的文件，同等地位；inode的编号增加1；

缺点：无法跨文件系统，只有超级用户才能够给目录创建硬链接

软连接： 创建一个新的文件，文件内保存源文件的路径，ls -il能够查看到，新的inode编号，以及属性变为l，可以跨文件系统

缺点：如果原文件路径发生变化，则软连接失效；

3. 从扑克牌中抽出五张牌，大小王可以代替任意牌，判断是否是连续？  具体如何用桶实现，可以考虑一下。

可以用map实现；提示要用bucket sort实现，当时不知道啥是懂排序。 回来查看了一些，桶排序实际上是hash的实现，桶加链表，实现插入然后合并，桶排序的算法复杂度为O(n)，针对于以比较排序的最坏情况下的最好情况为O(nlogn),而桶排序不是基于比较的，所以算法复杂度为O(n)，实现所过程：插入对应的链表，然后依次合并桶；

1. bool isSeq(int array[],int len){//算法复杂度为nlogn，应该用unordered_map实现map
2. map<int,int> mp;
3. int minval = 55;
4. int wcnt = 0;
5. for(int i=0;i<len;i++) {
6. if(array[i] == -1) {
7. wcnt++;
8. continue;
9. }
10. mp[array[i]] = 1;
11. if(array[i] < minval) minval = array[i];
12. }
13. int cnt = 1;
14. for(int i = minval+1;i<=minval+4;i++) {
15. if(mp[i]) cnt++;
16. }
17. if(cnt==5) return true;
18. if(cnt==4 && wcnt==1) return true;
19. if(cnt==3 && wcnt==2) return true;
20. return false;
21. }

 桶排序变形： 数组加链表；数组内元素可以是有序的，这样仅需要插入时对链表排序即可，然后把所有的链表链接起来即可；

如对数字排序，可以根据从左到右的数字来加入到桶内，分为10个桶，表示0，1,…9；前提输入数均匀且独立均匀分布在桶的范围空间内，所以一般不会有很多数落在一个桶中的情况。

4.  多个数中有两个数不相同，如何找出来？

1. vector<int> getTwoNum(vector<int> & input) {
2. int len = input.size();
3. int res = 0;
4. for(int i=0;i<len;i++) {
5. res ^= input[i];
6. }
7. int j=0;
8. for(int i=0;i<32;i++) {
9. if( (res >> i)& 0x1){
10. j = i;
11. break;
12. }
13. }
14. int left = 0;
15. int right = 0;
16. for(int i=0;i<len;i++) {
17. if((input[i]>>j) & 0x1) {
18. left ^= input[i];
19. } else {
20. right ^= input[i];
21. }
22. }
23. vector<int> result;
24. result.push_back(left);
25. result.push_back(right);
26. return result;
27. }

5. 给出机器的word长度 

 sizeof(size_t) sizeof(int * ) uname -a

6. 求最小编辑距离？ （详见http://www.cnblogs.com/purejade/articles/3834883.html）

当时思考错误，利用每个数来进行删减，其实不是，编辑可以增加、删减以及替代；也只能通过这三种方式来行程下一个；

所以递推关系式应为 D[i][j] = min(D[i-1][j]+1,D[i][j-1]+1,(D[i-1][j-1]+(s1[i-1]==s2[j-1]?0:1));如果replace为2，则改为2；递归关系和前三者之间的关系可以很容易得到；

http://www.programcreek.com/2013/12/edit-distance-in-java/

如果s1[i-1]==s2[j-1]，则D[i][j] == D[i-1][j-1] 

如果s1[i-1] != s2[j-1]，则D[i][j] = min(D[i-1][j] + 1,D[i][j-1] +1,D[i-1][j-1]+1)

7.逻辑题

给一个数m，每次去1-3个，取最后一个为输； 先走的必胜策略；表示这道题当时想了很久，他给我个13，让我想必胜策略，我怎么都没想到，结果就发现这个肯定必输；面试官考察你的分析思路，给出必胜策略就可以了；先走的不管怎么走，我们都给它凑到4n+1的数就可以了，这样先走肯定输；因为先走就等价于从5开始；则必输；

8.query 语义分析的方法

如姚晨  -》姚晨相关图片　　天龙八部　－》　视频

1） log中点击提取

2）query聚类和高频分析

3）特殊点点击，如天龙八部 视频

最后总结一下：

这次面试，第一道题目答的不是很好，递推关系式有点问题；其余还可以；但都有一个问题，书写嫉妒不规范，想到哪里写哪里，这样对后来者评价很不利；以后要写的同时要学会总结，把重点工整的写出来。