首页 > 代码库 > 百度网页搜索部rank团队4S面试

百度网页搜索部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)特殊点点击,如天龙八部 视频

最后总结一下:

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

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