BAT网易经典题_给出一个链表以及两个数n,k,输出这个链表中第一个值为n的元素的前面第k个元素的值

1. 8月15日，百度2道面试题：
   1、来自《编程之美》的概率题：一个桶里面有白球、黑球各100个，现在按下述规则取球：的
       i 、每次从通里面拿出来两个球；
       ii、如果取出的是两个同色的求，就再放入一个黑球；
       ii、如果取出的是两个异色的求，就再放入一个白球。
   问：最后桶里面只剩下一个黑球的概率是多少？
   2、算法题：给你一个自然数N，求[6,N]之内的所有素数中，两两之和为偶数的那些偶数。
   
2. 9月5日，华为2014校园招聘的机试题目
   通过键盘输入一串小写字母(a~z)组成的字符串。请编写一个字符串压缩程序，将字符串中连续出席的重复字母进行压缩，并输出压缩后的字符串。
   压缩规则：
       1、仅压缩连续重复出现的字符。比如字符串"abcbc"由于无连续重复字符，压缩后的字符串还是"abcbc"。
       2、压缩字段的格式为"字符重复的次数+字符"。例如：字符串"xxxyyyyyyz"压缩后就成为"3x6yz"。
   要求实现函数： 
        void stringZip(const char *pInputStr, long lInputLen, char *pOutputStr);
       输入pInputStr：  输入字符串lInputLen：  输入字符串长度
       输出 pOutputStr： 输出字符串，空间已经开辟好，与输入字符串等长；
   注意：只需要完成该函数功能算法，中间不需要有任何IO的输入输出
   示例 
       输入：“cccddecc”   输出：“3c2de2c”
       输入：“adef”     输出：“adef”
       输入：“pppppppp” 输出：“8p”
   
3. 9月6日，网新恒天2014校园招聘笔试编程题
   已知memcpy的函数为： void* memcpy(void *dest , const void* src , size_t count)其中dest是目的指针，src是源指针。不调用c++/c的memcpy库函数，请编写memcpy。
   点评：老题，参考答案如下
   1. //copyright@July 2013/9/24  
   2. void* memcpy(void *dst, const void *src, size_t count)      
   3. {      
   4.     //安全检查  
   5.     assert( (dst != NULL) && (src != NULL) );      
   6.   
   7.     unsigned char *pdst = (unsigned char *)dst;      
   8.     const unsigned char *psrc = (const unsigned char *)src;      
   9.   
   10.     //防止内存重复  
   11.     assert(!(psrc<=pdst && pdst<psrc+count));      < span="" style="word-wrap: break-word;">
   12.     assert(!(pdst<=psrc && psrc<pdst+count));      < span="" style="word-wrap: break-word;">
   13.   
   14.     while(count--)      
   15.     {      
   16.         *pdst = *psrc;      
   17.         pdst++;      
   18.         psrc++;      
   19.     }      
   20.     return dst;      
   21. }    
4. 9月9日，迅雷2014校招笔试编程题：
   已知集合A和B的元素分别用不含头结点的单链表存储，函数difference()用于求解集合A与B的差集，并将结果保存在集合A的单链表中。例如，若集合A={5,10,20,15,25,30}，集合B={5,15,35,25}，完成计算后A={10,20,30}。
   链表结点的结构类型定义如下：
   
   1. struct node    
   2. {    
   3.     int elem;    
   4.     node* next;    
   5. };    
   请完成函数void difference(node** LA , node* LB)
   点评：参考答案或更多题目请参见：http://blog.csdn.net/hackbuteer1/article/details/11482103。
   
5. 9月10日，美团网2014校招研发笔试哈尔滨站
   1、链表翻转。给出一个链表和一个数k，比如链表1→2→3→4→5→6，k=2，则翻转后2→1→4→3→6→5，若k=3,翻转后3→2→1→6→5→4，若k=4，翻转后4→3→2→1→5→6，用程序实现
   点评：类似编程艺术第1章左旋转字符串，见：http://blog.csdn.net/v_JULY_v/article/details/6322882。
   2、一个m*n的矩阵，从左到右从上到下都是递增的，给一个数elem，求是否在矩阵中，给出思路和代码
   点评：杨氏矩阵查找，见编程艺术第23章：http://blog.csdn.net/v_july_v/article/details/7085669。
6. 9月14日，阿里巴巴2014校招笔试哈尔滨站
   1、宿舍内5个同学一起玩对战游戏。每场比赛有一些人作为红方，另一些人作为蓝方。请问至少需要多少场比赛，才能使任意两个人之间有一场红方对蓝方和蓝方对红方的比赛？答案为4场，参考如下图，作者doc_sgl：
   
   点评：其余题目请参见：http://blog.csdn.net/doc_sgl/article/details/11695671。
   2、一个有10亿条记录的文本文件，已按照关键字排好序存储。请设计算法，可以快速的从文件中查找指字关键字的记录。
7. 9月14日，阿里巴巴-系统工程师-北京站
   
8. 9月16日，创新工场2014校招笔试题
   
   点评：上面第3题还是杨氏矩阵查找，见编程艺术第23章：http://blog.csdn.net/v_july_v/article/details/7085669。既然这么多公司都喜欢考杨氏矩阵查找，那么再给出杨氏矩阵查找一题的扩展：给定 n×n 的实数矩阵，每行和每列都是递增的，求这 n^2 个数的中位数，分析详见：http://zhiqiang.org/blog/science/computer-science/median-algorithm-of-ordered-matrix.html。
9. 9月21日，百度2014校招-济南站
   
   
10. 9月21日，腾讯2014软件开发校招-简答题-广州
    
    点评：这里有一关于上面2题的题解：http://blog.csdn.net/thebestdavid/article/details/12056293，可以参考。
    
11. 9月22日，人人校招笔试题
    
    点评：上述第1题寻找满足条件的两个数，见编程艺术第5章：http://blog.csdn.net/v_JULY_v/article/details/6419466；上述第2题见编程艺术第21章：http://blog.csdn.net/v_july_v/article/details/6890054。
12. 9月22日，阿里巴巴北邮站
    
    
    
    点评：这里有一朋友关于上述3题的题解：http://blog.csdn.net/thebestdavid/article/details/11975809，大家可以参考。
    
13. 9月23日，网易电商部-社招面试
    HashMap与HashTable区别
    点评：HashMap基于Hashtable实现，不同之处在于HashMap是非同步的，并且允许null，即null value和null key，Hashtable则不允许null，详见：http://oznyang.iteye.com/blog/30690。此外，记住一点：hashmap/hashset等凡是带有hash字眼的均基于hashtable实现，没带hash字眼的如set/map均是基于红黑树实现，前者无序，后者有序，详见此文第一部分：http://blog.csdn.net/v_july_v/article/details/7382693。
    
14. 9月24日，去哪儿网2014校招西安站笔试题
    给定一个200MB的文本文件，里面存的是IP地址到真实地址信息的映射信息，例如：211.200.101.100北京
    然后给你6亿个IP地址，请设计算法快速的打印出所对应的真实地址信息。
    
15. 9月25日，阿里巴巴二面
    指针/数组区别，决策树训练原理，SVM原理，网络协议，堆排序，字符串转换成整数，设计一款拼音输入法等等..
    点评：字符串转换成整数看似简单，实则很多坑，要写好并不容易，具体分析和实现见编程艺术第30章：http://blog.csdn.net/v_july_v/article/details/9024123；决策树见：http://blog.csdn.net/v_july_v/article/details/7577684；SVM原理见：http://blog.csdn.net/v_july_v/article/details/7624837。
    总结：此次面试的这位同学面的还是堆排/快排/atoi等典型问题，实际上：①面试看基础算法编程能力，和准备是否充分；②不论结果如何，跟4年前高考一样，高考和面试都只是人生路上的其中一站。你的真正核心竞争力不是进哪所名校哪所名企，而是存在你骨子里的上进心或热爱钻研技术的态度。
    
16. 9月28日，微软2014校招笔试题最后一道
    
    点评：上题形式上类似编程艺术第35章完美洗牌算法http://blog.csdn.net/v_july_v/article/details/10212493#t8，但因给定的是链表，所以相对来说，简单了不少；微软2014校招其它题目见：http://blog.csdn.net/xiaoerlyl/article/details/12126807。
17. 9月28日，百度2014校招-武汉站-系统分析师
    
    
18. 10月2日，暴风影音2014校招笔试
    1、合并两个已经排序的单链表为一个排序的单链表，相同内容只保留一个
    如：单链表a:1->2->3->4
    单链表b:3->4->5
    输出：1->2->3->4->5
    2、编写程序，在原字符串中把尾部m个字符移动到字符串的头部，要求：长度为n字符串操作时间复杂度为O(n),时间复杂度为O(1)。
    如：原字符串为”Ilovebaofeng”，m=7，输出结果：”baofengIlove”。
    点评：还是类似编程艺术第1章左旋字符串：http://blog.csdn.net/v_JULY_v/article/details/6322882。
    3、暴风影音的片源服务器上保存着两个文件a和b，各存放50亿条URL，每条URL占用64字节，内存限制是4G，让你找出a,b文件共同的URL。要求：算法设计。
    点评：上述第3题等海量数据处理面试题，请参见此文第第一部分第6题：http://blog.csdn.net/v_july_v/article/details/7382693。
    
19. 关于linux内核的几个面试问题：
    1、Linux中主要有哪几种内核锁？
    2、Linux中的用户模式和内核模式是什么含意？
    3、用户进程间通信主要哪几种方式？
    4、有哪几种内存分配函数？
    
20.  微软一面：输入两个数，相加求和，二进制输出。

9月11日， 京东：

谈谈你对面向对象编程的认识

4**9 的笔试题，比较简单：
1.求链表的倒数第二个节点
2.有一个整数数组，求数组中第二大的数

定一个长度为N的整数数组，只允许用乘法，不能用除法，计算任意（N-1）个数的组合中乘积最大的一组，并写出算法的时间复杂度。
  我们可以把所有可能的（N-1）个数的组合找出来，分别计算它们的乘积，并比较大小。由于总共有N个（N-1）个数的组合，总的时间复杂度为O（N2），显然这不是最好的解法。
  OK，以下解答来自编程之美
解法1

解法2
  此外，还可以通过分析，进一步减少解答问题的计算量。假设N个整数的乘积为P，针对P的正负性进行如下分析（其中，AN-1表示N-1个数的组合，PN-1表示N-1个数的组合的乘积）。
   1.P为0

Q为0
说明数组中至少有两个0，那么N-1个数的乘积只能为0，返回0；
Q为正数
返回Q，因为如果以0替换此时A_N-1中的任一个数，所得到的P_N-1为0，必然小于Q；
Q为负数
如果以0替换此时A_N-1中的任一个数，所得到的P_N-1为0，大于Q，乘积最大值为0。

     2.    P为负数

根据“负负得正”的乘法性质，自然想到从N个整数中去掉一个负数，使得P_N-1为一个正数。而要使这个正数最大，这个被去掉的负数的绝对值必须是数组中最小的。我们只需要扫描一遍数组，把绝对值最小的负数给去掉就可以了。

      3.    P为正数

类似地，如果数组中存在正数值，那么应该去掉最小的正数值，否则去掉绝对值最大的负数值。

10月10日人人网面试题
第一面：
1、（1）++i 和 i++，那个效率高？
  （2）++++i，i++++，哪个是合法的？
  （3）实现int型的++i 和 i++操作。
2、一段程序，求输出。（考察静态变量和模版类）

10月15日，网新恒天笔试题
1.不要使用库函数，写出void *memcpy(void *dst, const void *src, size_t count)，其中dst是目标地址，src是源地址。
点评：下面是nwpulei写的代码：

链接：http://blog.csdn.net/nwpulei/article/details/8090136。
2.给定一个字符串，统计一下哪个字符出现次数最大。
3.我们不知道Object类型的变量里面会出现什么内容，请写个函数把Object类型转换为int类型。

上面的递归程序，有什么地方需要改进呢？在递归的过程中，有些数据被重复计算了。比如，如果开始我们调用CalculateStringDistance(strA,1, 2, strB, 1, 2)，下图是部分展开的递归调用。

可以看到，圈中的两个子问题被重复计算了。为了避免这种不必要的重复计算，可以把子问题计算后的解存储起来。如何修改递归程序呢？还是DP！请看此链接：http://www.cnblogs.com/yujunyong/articles/2004724.html。
3、此外，关于这个“编辑距离”问题的应用：搜索引擎关键字查询中拼写错误的提示，可以看下这篇文章：http://www.ruanyifeng.com/blog/2012/10/spelling_corrector.html。「关于什么是“编辑距离”：一个快速、高效的Levenshtein算法实现，这个是计算两个字符串的算法，Levenshtein距离又称为“编辑距离”，是指两个字符串之间，由一个转换成另一个所需的最少编辑操作次数。当然，次数越小越相似。这里有一个BT树的数据结构，挺有意思的：http://blog.notdot.net/2007/4/Damn-Cool-Algorithms-Part-1-BK-Trees」
最后，Lucene中也有这个算法的实现（我想，一般的搜索引擎一般都应该会有此项拼写错误检查功能的实现）：http://www.bjwilly.com/archives/395.html。
4、扩展：面试官还可以继续问下去：那么，请问，如何设计一个比较两篇文章相似性的算法？（这个问题的讨论可以看看这里：http://t.cn/zl82CAH）

10月28日，微软三面题「顺祝，老妈明天生日快乐！」：
找一个点集中与给定点距离最近的点，同时，给定的二维点集都是固定的，查询可能有很多次，时间复杂度O(n)无法接受，请设计数据结构和相应的算法。
类似于@陈利人：附近地点搜索，就是搜索用户附近有哪些地点。随着GPS和带有GPS功能的移动设备的普及，附近地点搜索也变得炙手可热。在庞大的地理数据库中搜索地点，索引是很重要的。但是，我们的需求是搜索附近地点，例如，坐标(39.91, 116.37)附近500米内有什么餐馆，那么让你来设计，该怎么做？
点评：R树「从B树、B+树、B*树谈到R 树」还是KD树「从K近邻算法、距离度量谈到KD树、SIFT+BBF算法」？