VMware面试题目总结

一面中主要有三道题:

1. 实现strcpy。函数原型:char strcpy(char dest, const char* src)。

后来发现自己实现的有问题。正确的实现应该如下:

char* strcpy(char* dest, const char* src)
{
    assert(dest!=NULL && src!=NULL);
    char* ret = dest;
    while((*dest++ = *src++) != '\0');
    return ret;
}

这个题目做得不好,我对自己很失望啊。

2. 给2n+1个数,其中n个数均出现了2次,有1个数只出现了1次,如何找出这个数?

如果用python的dict数据结构来实现会很简单,一次遍历统计每个数出现的次数就可以了。如果是这样的话,就不需要将题目限制为只有一个1个数只出现了一次了,所以肯定有更好的算法。

其实更好的方法是这样的:

int findAppearOnce(int *array, int len){
    int result=0;
    for(int i=0;i<len;i++)
        result^=array[i];
    return result;
}

因为两个相同的数异或的结果是0。

3. Linux内核态和用户态的区别?进程与线程的区别?

二面主要考察英语口语和听力,不记得是否有算法题了,好像没有。英语说得结结巴巴的,幸好交流还不是很困难。

除英语外,还有问题:

1. 项目中遇到过的有难度的问题有哪些?

三面的面试官感觉各种懂啊,根据我的简历中涉及的相关知识进行提问,各种不会,我真是弱暴了。

1. 网络数据包如何从网络结点A经过路由器到达结点B?数据包的MAC header和IP eader各主要包含了什么数据?在经过路由器时发生了什么变化?

2. git merge?因为我说没用过git的merge功能,因为我github上的项目都是个人项目,所有代码都在master主干上提交的,所以面试官就没在继续问,估计是想问问merge的原理吧?

3. 有三个文件,找出在三个文件中均出现过的byte。返回的结果是一个byte类型的数组。

我当时的基本思路和一面中第2道题目的思路差不多,也是遍历三个文件,dict的key为byte值,value为出现过该byte的文件。但这样占的内存有点大。(后来想想,其实还好啦,byte就8位,也就256个不同的值)

另一个稍微改进一点的方法是:在三个文件中均出现过的byte,也就是三个文件中byte集合的交集。所以可以选取最小的文件,以其中的byte做key,遍历第二个文件,对在1,2文件中均出现的byte设置value标记。第二个文件遍历完成后,取出做过value标记的byte(设为集合X),然后遍历第三个文件,对在X和第三个文件中均出现的byte做标记,第三个文件遍历完成后,做过value标记的byte即为结果。但这应该不是最佳算法。还有待继续思考。

更新:同学给出的方案是-使用bitmap,每个文件弄个256位的bitmap,出现的byte就在相应的位上置1,然后三个bitmap按位与一下。靠谱!

4. 不使用微博的API,使用爬虫尽可能多地抓取某个人(比如李开复)的直接粉丝和间接粉丝(随便有多间接)?如何避免重复抓取相同的粉丝数据?

5. 前段时间有人说对于JAVA的hash函数(应该是hashCode()方法),一定规律的多个数都可以生成相同的hash值,对于这个问题,在应用中应该如何解决?

我的思路是在hash之前,对待hash的值加盐(salt)混合再hash。

6. TCP与UDP的区别?UDP主要用于哪些方面?TCP连接3次握手,断开连接4次握手,为什么要4次握手?

连接终止使用了四路握手过程(four-way handshake),在这个过程中每个终端的连接都能独立地被终止。因此,一个典型的拆接过程需要每个终端都提供一对FIN和ACK。而建立连接始终是由客户端发起连接的。

7. 访问某些网站时,请求结果是“连接被重置”的报告,那么连接被重置的原理是什么?

连接被重置的本质,是因为收到了破坏连接的一个 TCP Reset 包

具体可参考:

VMware的工作环境很不错,各种Mac,屏幕超大啊(这显得我很diaosi啊),面试官也很不错,问题也比较有水平。可惜我今天的状态实在不好,各种不会,铁定跪了。唉!diaosi的命。