10月17日,360校招测试开发一面

  1、写一个单例模式

  2、怎么样对一个hashmap里的根据key进行排序?

  3、给出一个路径“D/test/test.txt”,其中记录了一个搜索结果“百度,关键词,结果1-10,360,关键词,结果1-10”,用程序实现把这两个搜索结果中出现相同关键词的搜索结果存入另一个文件中。

  4、对一个数组中找出第二大的数

  5、TCP的三次握手是怎样的过程,如果是两次握手会怎么样,四次握手呢?

  美团2014校招二面

  假设已有10w个敏感词,现给你50个单词,查询这50个单词中是否有敏感词。

  点评:换句话说,题目要你判断这50个单词是否存在那10w个敏感词库里,明显是字符串匹配,由于是判断多个单词不是一个,故是多模式字符串匹配问题,既是多模式字符串匹配问题,那么便有一类称之为多模式字符串匹配算法,而这类算法无非是kmp、hash、trie、AC自动机、wm等等:http://stblog.baidu-tech.com/?p=418。

  那到底用哪种算法呢?这得根据题目的应用场景而定。10w + 50,如果允许误差的话,你可能会考虑用布尔过滤器;否则,只查一次的话,可能hash快,但hash消耗空间大,故若考虑tire的话,可以针对这10w个敏感词建立trie树,然后对那50个单词搜索这颗10w敏感词构建的tire树,但用tire树同样耗费空间,有什么更好的办法呢?Double Array Trie么?请读者继续思考。

  谷歌面试题:输入是两个整数数组,他们任意两个数的和又可以组成一个数组,求这个和中前k个数怎么做?

  点评:引用朋友Ben博客http://blog.csdn.net/tnndye/article/details/12857577 内的分析,“假设两个整数数组为A和B,各有N个元素,任意两个数的和组成的数组C有N^2个元素。

  那么可以把这些和看成N个有序数列:

  A[1]+B[1] <= A[1]+B[2] <= A[1]+B[3] <=…

  A[2]+B[1] <= A[2]+B[2] <= A[2]+B[3] <=…

  …

  A[N]+B[1] <= A[N]+B[2] <= A[N]+B[3] <=…

  问题转变成,在这N个有序数列里,找到前k小的元素”:http://blog.csdn.net/v_JULY_v/article/details/6370650。

  阿里巴巴二面:

  两个字符串A、B。从A中剔除存在于B中的字符。比如A=“hello world”,B="er",那么剔除之后A变为"hllowold"。空间复杂度要求是O(1),时间复杂度越优越好。

  点评:微博上一朋友@kanrence留言到:把B对应的字符在asc码表上置1,然后扫描A,表上置1的A上删掉。或者如@齐士博Go所说asc的bitvector, O(m+n); 先把B映射到vecotr,再遍历A。这两种方法因为都是常数空间127,所以可以认为是空间复杂度O(1),此外,还有别的什么方法么?位运算?更多讨论请见这:http://weibo.com/1580904460/AeNifo3tI?mod=weibotime。

  创新工场面试

  1、有一个int型数组,每两个相邻的数之间的差值不是1是-1.现在给定一个数,要求查找这个数在数组中的位置。

  2、一个字符数组,里面的字符可能是a-z、A-Z、0-9.现在要求对数组进行排序,要求所有小写字符放在前面,所有大写字符放在中间,所有数字放在后,而且各部分内部分别有序。

  点评:面试中纸上coding能力尤为重要,且答题之前一定要跟面试官交流以彻底弄清楚题意,题目来源:http://blog.csdn.net/xiajun07061225/article/details/8882981。

  10月17日,网易2014校招雷火游戏一面

  1、i)

  [cpp] view plaincopyprint?

  Class A{

  ...

  };

  A *pa = new A();

  A *pas = new A[NUM]();

  1.delete []pas; //详细流程

  2.delete []pa; //会发生什么

  3.delete pas; //哪些指针会变成野指针

  Class A{

  ...

  };

  A *pa = new A();

  A *pas = new A[NUM]();

  1.delete []pas; //详细流程

  2.delete []pa; //会发生什么

  3.delete pas; //哪些指针会变成野指针

  ii)、为什么不建议经常手动new和delete而以内存池取代

  iii)、malloc函数本身涉及的几种系统调用

  iv)、内存分配算法伙伴算法

  整理自:http://www.itmian4.com/forum.php?mod=viewthread&tid=3753。