首页 > 代码库 > 百度网页搜索部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),实现所过程:插入对应的链表,然后依次合并桶;
- bool isSeq(int array[],int len){//算法复杂度为nlogn,应该用unordered_map实现map
- map<int,int> mp;
- int minval = 55;
- int wcnt = 0;
- for(int i=0;i<len;i++) {
- if(array[i] == -1) {
- wcnt++;
- continue;
- }
- mp[array[i]] = 1;
- if(array[i] < minval) minval = array[i];
- }
- int cnt = 1;
- for(int i = minval+1;i<=minval+4;i++) {
- if(mp[i]) cnt++;
- }
- if(cnt==5) return true;
- if(cnt==4 && wcnt==1) return true;
- if(cnt==3 && wcnt==2) return true;
- return false;
- }
桶排序变形: 数组加链表;数组内元素可以是有序的,这样仅需要插入时对链表排序即可,然后把所有的链表链接起来即可;
如对数字排序,可以根据从左到右的数字来加入到桶内,分为10个桶,表示0,1,…9;前提输入数均匀且独立均匀分布在桶的范围空间内,所以一般不会有很多数落在一个桶中的情况。
4. 多个数中有两个数不相同,如何找出来?
- vector<int> getTwoNum(vector<int> & input) {
- int len = input.size();
- int res = 0;
- for(int i=0;i<len;i++) {
- res ^= input[i];
- }
- int j=0;
- for(int i=0;i<32;i++) {
- if( (res >> i)& 0x1){
- j = i;
- break;
- }
- }
- int left = 0;
- int right = 0;
- for(int i=0;i<len;i++) {
- if((input[i]>>j) & 0x1) {
- left ^= input[i];
- } else {
- right ^= input[i];
- }
- }
- vector<int> result;
- result.push_back(left);
- result.push_back(right);
- return result;
- }
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面试