IT公司笔经面经

师兄说，你写笔试日记没？写笔试日记是一个好的总结，可以学到东西。

 这一段遭遇的打击表明必须认真对待找工作这件事了。

 言归正传。

笔经

（1）10.10 网易游戏笔试

笔了3个小时，共20页。试卷1是决定及格线，试卷2决定名次。

 试卷1并没有答的很好，说明基础不牢。基本上是语言和数据结构，操作系统和网络大约两道。//看完面试宝典。试卷2里面都是大题。问题出在概率题和排序。//消化数据结构和100题

 概率题：网游中有个抽奖活动，抽中各星座的概率为10/200，20/200，。。。120/200.如何实现？

 排序：求快排的非递归做法求期望的公式？

（2）  人搜笔试。

是最难的几道算法题把大家搞懵了。图论算法，组合数学，概率题目，数据库操作系统网络

   
1  游玩n个城市中m个城市的所有方法 所有路径数。可以重复游玩。最后输出方法数p。可以回退。有的有边，有的没边。输入是邻接表。 大概是蚁巢算法和模拟退火

 2buddy system：空闲内存的叶框的组织模型

 Linux内核中引入了伙伴系统算法(buddy system)。把所有的空闲页框分组为11个块链表，每个块链表分别包含大小为1，2，4，8，16，32，64，128，256，512和1024个连续页框的页框块。最大可以申请1024个连续页框，对应4MB大小的连续内存。每个页框块的第一个页框的物理地址是该块大小的整数倍。

     
假设要申请一个256个页框的块，先从256个页框的链表中查找空闲块，如果没有，就去512个页框的链表中找，找到了则将页框块分为2个256个页框的块，一个分配给应用，另外一个移到256个页框的链表中。如果512个页框的链表中仍没有空闲块，继续向1024个页框的链表查找，如果仍然没有，则返回错误

http://baike.baidu.com/view/4935190.htm

（3） 腾讯笔试 是最容易的。书本基本知识。

（4） 高德笔试题型一般，难度中等。

1  
原题是求n个数中最大的K个数，有一道堆排序没写出来，忘了怎么写。

 2   struct的写法忘了。指针型的统一使用”->“,对象型的使用”.“就行。

 node *p, p->next,p->data。node p , p.next,p.data.

 总之，败在了基础上。

 补充：还有很多笔试，不过大部分想不起来了，不外乎两点：数据结构和算法。另外就是大数据量的处理很多公司会来一道大题。

 （5）启明星辰。做了两套卷子：linux和c,安全工程师。linux和c这张卷子比较平常，但是可能考察代码能力比较严格---写出能用的简洁的正确的代码--这恰恰是我缺乏的。有一道关于linux自旋锁http://blog.21ic.com/user1/2543/archives/2006/13468.html的问题没有回答出来。安全工程师这一块考了挺多网络基本知识的，大部分都忘了，草草答了题目。深拷贝和浅拷贝。

深拷贝和浅拷贝体现在 拷贝构造函数中的差别。

拷贝有两种：深拷贝，浅拷贝当出现类的等号赋值时，会调用拷贝函数在未定义显示拷贝构造函数的情况下，系统会调用默认的拷贝函数——即浅拷贝，它能够完成成员的一一复制。当数据成员中没有指针时，浅拷贝是可行的。但当数据成员中有指针时，如果采用简单的浅拷贝，则两类中的两个指针将指向同一个地址，当对象快结束时，会调用两次析构函数，而导致指针悬挂现象。所以，这时，必须采用深拷贝。深拷贝与浅拷贝的区别就在于深拷贝会在堆内存中另外申请空间来储存数据，从而也就解决了指针悬挂的问题。简而言之，当数据成员中有指针时，必须要用深拷贝。 

（6）去哪儿和美团

这两个网站同时笔试，去哪儿只做了一个小时就出来写美团了。

去哪儿：

a输入算术表达式求解。使用两个栈。一个压栈数字，一个压栈操作符，对比当前字符串元素与操作符栈栈顶元素，执行动作。

b字符串连接给出类似"13""1""134""35"，连接出最小的排列，比如“11313435”最小。

重载运算符"<".对比的标准是：如果第一位相同，则比较第二位;如果a的位数n小于b的位数m，那么a[n+1]=b[1],继续进行对比n+1位。

美团算法题:给定字符串，写出全排列。如"aab"写出“aab” "aba""baa"。

解答：使用变换和递归。比如已知第一种排列aab第一个位置放a。查看让它后边的元素与它交换，放在第一位。如果相同则不交换。递归进行第二个位置的确定。

参考：http://blog.csdn.net/crazyhacking/article/details/8095037

面经：

很多公司可能会问到大数据的问题。需要准备的一些知识：数据挖掘，分词算法

搜狗面试题：1 就是如何实现搜索关键词的提示

 腾讯面试：1微博方面大约问了四道很基本的算法题。有一道：给出字符串s,给出字符串token,根据token的每个字符对s进行分词。没有说出O(n+m)的做法：对s中每个字符进行hash映射，如果映射到token中则分词。2游戏方面，是一位做前台的长发大哥面试的，但我应聘的是后台。问了我c和c++，shell的一些“极端用法”，大部分不会。然后两人都比较喜欢游戏，就扯了一会淡。不过，那位大哥倒是告诉我一个知识点：做高并发响应的用多进程（开n个进程，一个死机不会影响整个机器），而我们高性能计算则是多线程（开n个线程，一个死机可能会影响整个机器）。

 阿里：不说了，公司面试有点扯。装比啊。