IT公司笔经面经【转】

（1）10.10 网易游戏

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

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

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

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

（2）人民搜索

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

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

2. buddy 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个页框的链表查找，如果仍然没有，则返回错误

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

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

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

总之，败在了基础上。

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

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

（6）去哪儿和美团

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

去哪儿：

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

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

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

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

【面经】

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

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

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

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