6， 将有序数组转化成最小深度的二叉查找树：折半查找的思路，每次都把序列中间的点作为父结点，而左序列中间节点作为左孩子，右序列中间节点作为右孩子

7， 在无向无环图中，找到最长的路径：最长路径的起点和终点的度为1，所以可从度为1的结点开始，依次找到他到其它度为1结点的最长路径，之后从最长路径集中找到最长的路径。对每个度为1的节点做广度优先搜索，得到最长路径

2011-9-19 雅虎一面题及答案

1， 一直以来最具成就感的项目，实习时的工作内容

2， 进程与线程的区别，线程的缺点，进程间的通信，管道的通信监听

进程和线程都是由操作系统所体会的程序运行的基本单元，系统利用该基本单元实现系统对应用的并发性。进程和线程的区别在于： 简而言之,一个程序至少有一个进程,一个进程至少有一个线程. 线程的划分尺度小于进程，使得多线程程序的并发性高。 另外，进程在执行过程中拥有独立的内存单元，而多个线程共享内存，从而极大地提高了程序的运行效率。 线程在执行过程中与进程还是有区别的。每个独立的线程有一个程序运行的入口、顺序执行序列和程序的出口。但是线程不能够独立执行，必须依存在应用程序中，由应用程序提供多个线程执行控制。

从逻辑角度来看，多线程的意义在于一个应用程序中，有多个执行部分可以同时执行。但操作系统并没有将多个线程看做多个独立的应用，来实现进程的调度和管理以及资源分配。这就是进程和线程的重要区别。

线程的缺点：

每个线程与主程序共用地址空间，受限于2GB地址空间；

线程之间的同步和加锁控制比较麻烦；

一个线程的崩溃可能影响到整个程序的稳定性；

到达一定的线程数程度后，即使再增加CPU也无法提高性能

线程能够提高的总性能有限，而且线程多了之后，线程本身的调度也是一个麻烦事儿，需要消耗较多的CPU

进程间的通信：基于信息量，基于共享内存，基于管道，基于消息队列

3， 堆和栈的区别

一个由C/C++编译的程序占用的内存分为以下几个部分
1、栈区（stack）— 由编译器自动分配释放 ，存放函数的参数值，局部变量的值等。其
操作方式类似于数据结构中的栈。
2、堆区（heap） — 一般由程序员分配释放， 若程序员不释放，程序结束时可能由OS回
收 。注意它与数据结构中的堆是两回事，分配方式倒是类似于链表，呵呵。
3、全局区（静态区）（static）—，全局变量和静态变量的存储是放在一块的，初始化的
全局变量和静态变量在一块区域， 未初始化的全局变量和未初始化的静态变量在相邻的另
一块区域。 - 程序结束后由系统释放。
4、文字常量区 —常量字符串就是放在这里的。 程序结束后由系统释放
5、程序代码区—存放函数体的二进制代码。
二、堆和栈的理论知识
2.1申请方式
stack: 由系统自动分配。 例如，声明在函数中一个局部变量 int b; 系统自动在栈中为b开辟空 间
heap: 需要程序员自己申请，并指明大小，在c中malloc函数
2.2 申请后系统的响应
栈：只要栈的剩余空间大于所申请空间，系统将为程序提供内存，否则将报异常提示栈溢
出。
堆：从系统有一个记录空闲内存地址的链表中查找合适的块进行分配，

2.3申请大小的限制
栈：在Windows下,栈是向低地址扩展的数据结构，是一块连续的内存的区域。这句话的意
思是栈顶的地址和栈的最大容量是系统预先规定好的，在WINDOWS下，栈的大小是2M（也有
的说是1M，总之是一个编译时就确定的常数），如果申请的空间超过栈的剩余空间时，将
提示overflow。因此，能从栈获得的空间较小。
堆：堆是向高地址扩展的数据结构，是不连续的内存区域。这是由于系统是用链表来存储
的空闲内存地址的，自然是不连续的，而链表的遍历方向是由低地址向高地址。堆的大小
受限于计算机系统中有效的虚拟内存。由此可见，堆获得的空间比较灵活，也比较大。
2.4申请效率的比较：
栈由系统自动分配，速度较快。但程序员是无法控制的。
堆是由new分配的内存，一般速度比较慢，而且容易产生内存碎片,不过用起来最方便.
2.5堆和栈中的存储内容
栈： 在函数调用时，第一个进栈的是主函数中后的下一条指令（函数调用语句的下一条可
执行语句）的地址，然后是函数的各个参数，在大多数的C编译器中，参数是由右往左入栈
的，然后是函数中的局部变量。注意静态变量是不入栈的。
当本次函数调用结束后，局部变量先出栈，然后是参数，最后栈顶指针指向最开始存的地
址，也就是主函数中的下一条指令，程序由该点继续运行。
堆：一般是在堆的头部用一个字节存放堆的大小。堆中的具体内容由程序员安排。
2.6存取效率的比较
堆是在运行时刻赋值的； 栈是在编译时就确定的；
但是，在以后的存取中，在栈上的数组比指针所指向的字符串(例如堆)快。

4， 内存转移memmove函数的思路及实现

存在二种情况，一是源地址与目标地址不重叠，二是重叠或者相等

Void *memmove(void *dest, void* source, size_t count)

{

Assert(NULL!=source && NULL!=dest)

Void *ret=dest;

If(dest<=source ||dest>=(source+count))

{

While(count–)

*dest++=*source++;

}

Else

{

Dest+=count-1;

Source+=count-1;

While(count–)

*dest–=*source–;

}

Return ret;

}

5， 内存泄漏的原因及预防方法：不断申请资源没有释放，养成良好的编程习惯，系统无法做到回收

6， 对数据库类型的要求及sql语句的优化

7， Tcp与Udp的区别，三次握手过程：tcp面向接连的确认服务，udp面向无连接的无确认服务。主机a,b,主机a向b发送一个syn(seq=x),b发送syn(seq=y,ack=x+1),a再发送syn(seq=x+1,ack=y+1)

8， 笔试第6题和第7题的思路

2011-9-19 雅虎二面题及答案

1， 实习经验所学到的东西，所用的平台

2， 合并排序的思想（从小序列到大序列的合并，从大序列到小序列的分解合并）

3， Java笔试题里分治算法的合并排序：把序列平均分成二部分，先把第一部分合并排序，再把第二部分合并排序，之后将两部分结果借助另一个数组实现两个有序表的选择排序。

4， 笔试题第6题和第7题的思路

5， 本科毕业论文的内容，研究生研究的内容，数据挖掘常用期刊，会议及数据源

KDD(knowledge discovery in databases),IEEE-ICDM(IEEE International Conference on Data Mining),springer, Elsevier, wiley. uci

6， 海量数据下样本的选择（选择具有代表普通用户的样本）

华为云计算研发工程师面试总结（2011-9-2~~2011-9-21）

华为一面技术面2011-9-20下午4：00：

1， 自我介绍

2， C++中虚函数的使用

3， C++中析构函数的作用（对象消亡时回收对象的资源），有没有虚函数，能不能传参数（无返回值无参数，可自行定义）

4， 项目相关，项目过程，项目中最关键的工作，你是如何处理的。

华为二面机试2011-9-20下午6：00：

从字符串中找到该字符串第一个字符在本字符串中最后出现的位置，在函数体里填代码，规定时间20分钟。

例如s=”abcabc” indexstr(s)=4

华为三面性格测评：每道题有三个小题，每个小题只有“最符合”和“最不符合”两项，一道只有一个“最符合”和一个“最不符合”，必须放弃一道题。试卷共52页，共104题，答题时间为30分钟。

华为综合面试2011-9-21上午8：30

1， 自我介绍

2， 简单介绍一下项目，项目过程，项目的输出物，项目的平台

3， 客户特征分析有哪些，而后加问了一句“客户特征在数据库里都是哪些”，其实他想表达的是客户属性

4， 怎样表现项目输出物（我用树结构向他说明了一下）

5， 既然谈到了树的话，那么树怎么遍历（中序，前序，后序），当场用三种方法遍历一棵树

6， 使用oracle数据库的话，oracle数据库里的实例是个什么概念，当场写一段sql建一张表

数据库实例是用于和操作系统进行联系的标识，也就是说数据库和操作系统之间的交互使用的是数据库实例

腾讯笔试2011-9-24 10：00—12：00

1， 功能不太复杂，效率高的函数

2， LRU缺面处理（最久未使用页面算法）

3， 页式内存管理

4， Tcp/ip time_out的处理

5， Linux下umask对文件权限的修改

6， 8进制语法的意思是用0-7代表共8种权限。文件和目录的访问权限位一共有9位，每3位分别代表属主，所属用户组，其他用户对它的权限。
在8进制语法中权限与数字的对应关系是
r对应数字4
w对应数字2
x对应数字1
-对应数字0

例子：-rwxr-xr-x用8进制法表示就是755，rwx=4+2+1=7,r-x=4+0+1=5

8种可能得权限为
八进制数字 权限
0 —
1 –x
2 -w-
3 -wx
4 r–
5 r-x
6 rw-
7 rwx

这样就可以根据需要来组合权限，只需要记住对应的数字就可以了

umask是利用8进制位的方式来定义用户创建文件或目录时的默认权限。可以用umask或umask -S命令来查看当前的umask值。
umask表示的是禁止权限，也就是说原来的权限减去umask值才得到所要定义的默认权限。

对于文件来说，umask 的设置是在假定文件拥有八进制666权限上进行(文件默认没有执行权限x)，文件的权限就是是666减去umask的掩码数值；
对于目录来说，umask 的设置是在假定文件拥有八进制777权限上进行，目录八进制权限777减去umask的掩码数值；

7， 单环链表的追尾 p->link=first

8， 循环队列的空值数–|rear-front+M|%M

9， Sizeof(共同体),sizeof

10， 有序表的二叉查找树

11， 系统的负载比较

12， 缺页中断的处理过程（）

13， 标量运行和向量运行程序的时间比较

14， O(1)

15， Linux三级目录索引

16， 归并排序

17， 有权有向图的最短路径及输出 floyd算法

百度笔试—机器学习 2011-9-24 3：00—5：00

1， 任务调度，并发执行任务，任务可能依赖于其它任务

2， 堆与栈的区别，如何分配1kb的缓冲区，此缓冲区在极端情况下需要100mb。

3， Const 修饰词应用，如何用指针取消常量：const int a=10; int * p = (int*)&a;

4， 取数轴上最长的线段重合

5， 求有权有向图中，两点间的最短路径

6， 岭回归的损失函数和罚函数，拉索回归的罚函数与岭回归罚函数的区别

搜狐视频数据挖掘算法工程师笔试2011-9-25 10：00—11：30

1， 类的继承

2， 资源互斥下的死锁

3， 一维数组，元素为指针，指针指向一个参数为Int，返回值为int的函数

4， 进程间的通信方式

5， Const标志符常量一定要？

6， String的普通构造函数，拷贝构造函数，赋值函数，析构函数

7， Strcpy函数

8， N个不同数的全排列，打印所有全排列

9， Sizeof(char name[]=”hello”)

10， 继承的转换（子类可以转换成基类，基类不能转换成子类，多继承下同一子类的基类间不能相互转换）

腾讯一面2011-9-25 14：10~14：25

1， 自我介绍(性格方面的

2， 关于二次购买的预测项目

3， 关于职业规划

4， 对游戏的看法

5， 对于技术和产品的看法

6， 关于从商务平台转换到游戏平台

7， 阿里巴巴有没有留Offer

备注：本次面试官并不是数据挖掘方面的，他看我的简历很适合他的同事部门，所以帮他的同事面的。问完上述问题后，留了一份电子简历给他的同事，如果他的同事觉得可以的话，第二天会电话面试我。其实这也是运气，我的同学们一直在纠结技术，而我如此幸运的过了一面，等待二面通知。

腾讯游戏安全中心二面2011-9-26 上午11：20-12：00

由于昨天面试官的推荐，今天游戏安全中心的员工打来电话面试。与其说是聊一下，倒不如说是往死面，把我蹂躏得不行了，我快招架不住。估计这面是希望了，运气这东西真的很重要。主要问了这么些问题

1， web社区发现的应用趋势

2， web社区里团的边界定义

3， web社区里距离的定义

4， web社区里算法里数据的存储形式

5， web社区发现的经典算法及其当前的应用，是否已经成功应用于商业（facebook的api数据来源）

6， 数据挖掘的可视化软件

7， static 静态变量和静态函数的作用（静态变量放在静态存储区，被多次使用时不被清除，若放在栈中函数被执行后会被清除，静态函数只有在被定义的模块中使用，不能被其它模块使用）

8， 进程与线程的区别，系统给进程分配的最大内存是多少？

9， 分类算法介绍判定树，属性的选择，目标属性为二值属性时属性的选择（判定树选择属性）

腾讯游戏安全中心三面2011-9-27 9：00~9：30

1， 自我介绍

2， Web社区问题的定义及应用

3， Web社区关系的定义及如何抽取

4， Web社区算法（我自己的算法）的流程，算法的优点和不足

5， Web社区经典算法的介绍

6， 当前自己算法存在的问题及后期如何改进

7， 后期的职业规划

8， 阿里巴巴实习的工作内容

9， 数据特征分析里一个简单的项目介绍（无名良品数据的抽取，优质客户的定义）

10， 为什么不回阿里

整个面试过程比较顺利，气氛比较愉快，面试官对我的回答一直频频点头，在出门时刻却什么都没说，包括对岗位的理解和后续复试通知之类的内容。这让我很没底。

搜狐视频数据挖掘算法工程师2011-9-27 10：30~11：00

1， 自我介绍

2， Web社区发现的介绍及其商业价值

3， 属性的选取方法

4， 在阿里是如何描述客户的

5， 使用哪些软件，平时使用哪些语言

6， 是否愿意实习

7， 为什么没有继续实习

8， 机器学习如何应用到数据分析和挖掘中

9， 统计学自已有哪些不足

10， 有其它需要了解的内容（团队的历史，团队的规模，当前团队的地位，岗位具体的工作内容等）

整个面试过程比较轻松，尤其是在面过腾讯的总经理面之后更是如此。搜狐比较顺利，对方对我比较满意，希望能够有进一步的交流合作机会

腾讯数据挖掘hr面2011-9-28 9：00——9：30

今天结束了腾讯的最后一轮面试，这个Hr看着很文静，实则非常地犀利，方方面面都问到了，而且还问得很巧妙。除了一些无关紧要的问题她会笑一下外，其它的主要问题不管你的回答怎样，她都不会表现出来。最后也没有给我任何积极的暗示。主要的问题如下：

1， 自我介绍

2， 在学校的成绩排名，有没有当过班干部，有没有项目，有没有拿过奖学金

3， 简历上的项目介绍

4， 家庭情况介绍

5， 对工作的预期和看法，未来三年的规划

6， 对qq企业文化的了解和qq产品的了解

7， 对于数据挖掘工作的辛苦，自己的看法

8， 为什么不留在阿里

9， 对数据挖掘在行业其它公司的理解和看法

10， 什么时候毕业，能不能在毕业前去实习

网易数据挖掘研究员笔试2011-10-10 19：00~21：00

1， 字符串匹配的算法复杂度（主串N,字串M）N+M

2， 排序算法的稳定性(快速排序为非稳定)

3， 平衡二叉树的插入

4， 20个亿整数的两个集合a与b,求a与b的交集，内存为4Gb

5， 在N个无序数中找K个最小值

6， 页面文件的逻辑地址位（8个1024字放内32帧内存里）

7， 计算机网络各层应用连接

8， 哪一种模式不关心算法

Abstract Factory：提供一个创建一系列相关或相互依赖对象的接口，而无需指定它们具体的类。（使用得非常频繁。）

Adapter：将一个类的接口转换成客户希望的另外一个接口。A d a p t e r模式使得原本由于接口不兼容而不能一起工作的那些类可以一起工作。

Bridge：将抽象部分与它的实现部分分离，使它们都可以独立地变化。

Builder：将一个复杂对象的构建与它的表示分离，使得同样的构建过程可以创建不同的表示。

Chain of Responsibility：为解除请求的发送者和接收者之间耦合，而使多个对象都有机会处理这个请求。将这些对象连成一条链，并沿着这条链传递该请求，直到有一个对象处理它。

Command：将一个请求封装为一个对象，从而使你可用不同的请求对客户进行参数化；对请求排队或记录请求日志，以及支持可取消的操作。

Composite：将对象组合成树形结构以表示“部分-整体”的层次结构。它使得客户对单个对象和复合对象的使用具有一致性。

Decorator：动态地给一个对象添加一些额外的职责。就扩展功能而言， 它比生成子类方式更为灵活。

Facade：为子系统中的一组接口提供一个一致的界面， F a c a d e模式定义了一个高层接口，这个接口使得这一子系统更加容易使用。

Factory Method：定义一个用于创建对象的接口，让子类决定将哪一个类实例化。Factory Method使一个类的实例化延迟到其子类。

Flyweight：运用共享技术有效地支持大量细粒度的对象。

Interpreter：给定一个语言, 定义它的文法的一种表示，并定义一个解释器, 该解释器使用该表示来解释语言中的句子。

Iterator：提供一种方法顺序访问一个聚合对象中各个元素, 而又不需暴露该对象的内部表示。

Mediator：用一个中介对象来封装一系列的对象交互。中介者使各对象不需要显式地相互引用，从而使其耦合松散，而且可以独立地改变它们之间的交互。

Memento：在不破坏封装性的前提下，捕获一个对象的内部状态，并在该对象之外保存这个状态。这样以后就可将该对象恢复到保存的状态。

Observer：定义对象间的一种一对多的依赖关系,以便当一个对象的状态发生改变时,所有依赖于它的对象都得到通知并自动刷新。

Prototype：用原型实例指定创建对象的种类，并且通过拷贝这个原型来创建新的对象。

Proxy：为其他对象提供一个代理以控制对这个对象的访问。

Singleton：保证一个类仅有一个实例，并提供一个访问它的全局访问点。

State：允许一个对象在其内部状态改变时改变它的行为。对象看起来似乎修改了它所属的类。

Strategy：定义一系列的算法,把它们一个个封装起来, 并且使它们可相互替换。本模式使得算法的变化可独立于使用它的客户。

Template Method：定义一个操作中的算法的骨架，而将一些步骤延迟到子类中。Template Method使得子类可以不改变一个算法的结构即可重定义该算法的某些特定步骤。

Visitor：表示一个作用于某对象结构中的各元素的操作。它使你可以在不改变各元素的类的前提下定义作用于这些元素的新操作

9， 数据库系统的两种语言（一种用于定义数据库模式；另一种用于表达数据的查询和更新）

10， 数据库的连接运算

11， 建立索引的原则

12， 事务的定义与特点，事务隔离的级别

未授权读取（允许脏读取，但不允许更新丢失），授权读取（允许不可重复读取，但不允许脏读取），可重复读取（禁止不可重复读取和脏读取，但是有时可能出现幻影数据）和序列化（事务序列化执行，不能并发执行）

13， 专业题一数据挖掘的步骤

14， Pca的概念和处理过程（主成分分析）

15， K中心点聚类算法简介

首先为每个簇随意选择一下代表对象，将剩余的对象根据其与代表对象的距离分配给最近的一个簇。然后反复地用非代表对象来替代代表对象，以改进聚类的质量。判定一个非代表对象O是否是当前一个代表对象的O1的好的替代，对于每一个非代表对象p，下面的四种情况考虑。

1， p当前属于代表Oj,如果Oj被O代替，p离Oi最近，那么p被重新分配给Oi

2， p当前属于代表Oj,如果Oj被O代替，p离O最近，那么p被重新分配给O

3， p当前属于代表Oi,如果Oj被O代替，p离Oi最近，那么p不变

4， p当前属于代表Oi,如果Oj被O代替，p离Oi最近，那么p被重新分配给O

16， 中文分词技术简介，常用数据结构和算法

17， 分类器的主流评测指标：准确率，速率，鲁棒性，可规模性和可解释性

18， 如何建立一个智能问答系统，思路

19， 如何建立一个智能商品推荐系统，思路

支付宝笔试2011-10-10 16：20~17：30

1， 求最短路径

2， Ping命令

3， Request的命令

4， 网页回应代号

5， 设计模式

6， 智力题

7， 流水线问题

8， 文法问题

网易电话面试2011-10-14 19：00~19：30

1， 阿里巴巴实习的工作内容

2， 阿里数据挖掘建模的效果

3， 阿里留存率的模型介绍，效果如何，目的如何

4， Web社区发现的介绍，当前的研究现状，是否有实际应用

5， 分类算法，有没有用过，实现过

6， C++语言的熟练程度，stl是否用过

7， 现在手里的offer，阿里的offer，如果公司有意愿的话，如何选择

8， 对加班的看法，对跳槽的看法

9， 对杭州城市的看法，有没有男朋友在杭州，家是哪里的（工作稳定性）

10， 当前部门工作，部门的历史，（从信息安全那里数据挖掘分过来的，成立半年）

支付宝电面2011-10-12 19:50~8:10

1， 自我介绍

2， 数据处理，最大的数据量，有没有sql数据处理经验

3， 有没有用高级语言写过算法

4， 比较熟悉的数据挖掘算法

5， Sql问题，full join, having

6， 为什么试卷上主观题和附加题没有写

7， 未来一到两年的规划

8， 学习能力很强的表现（自学sas软件）

9， 阿里有没有留offer

10， 关于对公司想要了解的方面（团队的工作内容，未来规划，团队的历史）

11， 未来两周内给见面反馈

由于刚吃完饭回来，而且下午没有接到电话以为晚上不会有电话的，所以没有心理准备，开始的时候比较紧张，慢慢倒是好了不少。