网易面试杂谈

http://blog.csdn.net/silangquan/article/details/18013967

从一次面试说起

         昨天下午接到的国内一家比较大的游戏公司面试通知，晚上打印好新的简历，今天早上7点半起床从B城赶到C城，海上雾很大。提前十分钟到达面试的地点。等了会，技术总监直接出来面试。下面是一些基本没答上来的题目。

语言相关

什么是displacement new？

placement new是重载operator new的一个标准、全局的版本，它不能被自定义的版本代替（不像普通的operator new和operator delete能够被替换成用户自定义的版本）。 它的原型如下： void *operator new( size_t, void *p ) throw() { return p; } 首先我们区分下几个容易混淆的关键词：new、operator new、placement new new和delete操作符我们应该都用过，它们是对堆中的内存进行申请和释放，而这两个都是不能被重载的。要实现不同的内存分配行为，需要重载operator new，而不是new和delete。 看如下代码： class MyClass {…}; MyClass * p=new MyClass; 这里的new实际上是执行如下3个过程： 1调用operator new分配内存； 2调用构造函数生成类对象； 3返回相应指针。 operator new就像operator+一样，是可以重载的，但是不能在全局对原型为void operator new(size_t size)这个原型进行重载，一般只能在类中进行重载。如果类中没有重载operator new，那么调用的就是全局的::operator new来完成堆的分配。同理，operator new[]、operator delete、operator delete[]也是可以重载的，一般你重载了其中一个，那么最好把其余三个都重载一遍。 placement new是operator new的一个重载版本，只是我们很少用到它。如果你想在已经分配的内存中创建一个对象，使用new是不行的。也就是说placement new允许你在一个已经分配好的内存中（栈或堆中）构造一个新的对象。原型中void*p实际上就是指向一个已经分配好的内存缓冲区的的首地址。 我们知道使用new操作符分配内存需要在堆中查找足够大的剩余空间，这个操作速度是很慢的，而且有可能出现无法分配内存的异常（空间不够）。placement new就可以解决这个问题。我们构造对象都是在一个预先准备好了的内存缓冲区中进行，不需要查找内存，内存分配的时间是常数；而且不会出现在程序运行中途出现内存不足的异常。所以，placement new非常适合那些对时间要求比较高，长时间运行不希望被打断的应用程序。 使用方法如下： 1. 缓冲区提前分配 可以使用堆的空间，也可以使用栈的空间，所以分配方式有如下两种： class MyClass {…};  char *buf=new char[N*sizeof(MyClass)+ sizeof(int) ] ; 或者char buf[N*sizeof(MyClass)+ sizeof(int) ]; 2. 对象的构造 MyClass * pClass=new(buf) MyClass; 3. 对象的销毁 一旦这个对象使用完毕，你必须显式的调用类的析构函数进行销毁对象。但此时内存空间不会被释放，以便其他的对象的构造。 pClass->~MyClass(); 4. 内存的释放 如果缓冲区在堆中，那么调用delete[] buf;进行内存的释放；如果在栈中，那么在其作用域内有效，跳出作用域，内存自动释放。 注意： 1) 在C++标准中，对于placement operator new []有如下的说明： placement operator new[] needs implementation-defined amount of additional storage to save a size of array. 所以我们必须申请比原始对象大小多出sizeof(int)个字节来存放对象的个数，或者说数组的大小。 2) 使用方法第二步中的new才是placement new，其实是没有申请内存的，只是调用了构造函数，返回一个指向已经分配好的内存的一个指针，所以对象销毁的时候不需要调用delete释放空间，但必须调用析构函数销毁对象。

new 或者malloc最多能申请多大的内存？

32位程序不可能申请大于4G的内存,linux在X86系统下，理论上用户态可以申请3G内存（有1G的地址空间留给内核），内核态可以申请4G内存，windows你需要查一查其系统规范。

linux下用top命令显示有内存空间，但malloc一个64mbuffer的时候失败了，什么原因，为啥会出现这种情况？试着malloc一个1m的buffer可能成功么？

内存碎片，无法找出连续的地址空间。空闲内存以小而不连续方式出现在不同的位置。由于分配方法决定内存碎片是否是一个问题，因此内存分配器在保证空闲资源可用性方面扮演着重要的角色。

内存碎片存在的方式有两种：a.内部碎片 b.外部碎片 。 内部碎片的产生：因为所有的内存分配必须起始于可被 4、8 或 16 整除（视处理器体系结构而定）的地址或者因为MMU的分页机制的限制，决定内存分配算法仅能把预定大小的内存块分配给客户。假设当某个客户请求一个 43 字节的内存块时，因为没有适合大小的内存，所以它可能会获得 44字节、48字节等稍大一点的字节，因此由所需大小四舍五入而产生的多余空间就叫内部碎片。 外部碎片的产生： 频繁的分配与回收物理页面会导致大量的、连续且小的页面块夹杂在已分配的页面中间，就会产生外部碎片。假设有一块一共有100个单位的连续空闲内存空间，范围是0~99。如果你从中申请一块内存，如10个单位，那么申请出来的内存块就为0~9区间。这时候你继续申请一块内存，比如说5个单位大，第二块得到的内存块就应该为10~14区间。如果你把第一块内存块释放，然后再申请一块大于10个单位的内存块，比如说20个单位。因为刚被释放的内存块不能满足新的请求，所以只能从15开始分配出20个单位的内存块。现在整个内存空间的状态是0~9空闲，10~14被占用，15~24被占用，25~99空闲。其中0~9就是一个内存碎片了。如果10~14一直被占用，而以后申请的空间都大于10个单位，那么0~9就永远用不上了，变成外部碎片。

可能会成功。

使用全局对象有什么缺点，内存是如何分配与回收的，

全局类变量会在进入main()函数之前被构造好，且是在退出main()函数后才被析构。

注意：在使用了标准C++的头文件时，如果全局对象的析构函数中使用了cout，则会看不到想要输出的字符串信息，自己误以为析构函数未被调用。 解释：首先析构函数的确被系统调用了，这一点可以在析构函数中加断点，调试证实。未产生输出的原因是cout其实是一个ostream对象，所以它也会析构，且在这里它比你定义的全局对象先析构，应该在退出main函数前析构，所以用cout输出的语句已经不具备意义了

说一下进程和线程的堆栈内存管理。

线程自己基本上不拥有系统资源,只拥有一点在运行中必不可少的资源(如程序计数器,一组寄存器和栈),但是它可与同属一个进程的其他的线程共享进程所拥有的全部资源. 

堆：是大家共有的空间，分全局堆和局部堆。全局堆就是所有没有分配的空间，局部堆就是用户分配的空间。堆在操作系统对进程初始化的时候分配，运行过程中也可以向系统要额外的堆，但是记得用完了要还给操作系统，要不然就是内存泄漏。 栈：是个线程独有的，保存其运行状态和局部自动变量的。栈在线程开始的时候初始化，每个线程的栈互相独立，因此，栈是thread safe的。

使用malloc申请对象指针内存，然后编译，是否会通过，在什么时候会出错？对其使用free的话会出现什么错误？

看一段测试代码:

[cpp] view plaincopy

在CODE上查看代码片

派生到我的代码片

1. #include<iostream>
2. #include<stdlib.h>
3. using namespace std;  
5. class Object  
6. {  
7. public:  
8.     Object(int i):id(i)  
9.     {  
10.         cout<<"Constructor"<<endl;  
11.     }  
12.     ~Object()  
13.     {  
14.         cout<<"Destructor"<<endl;  
15.     }  
16. void sayHi()  
17.     {  
18.         cout<<"Hi,I am No."<<id<<endl;  
19.     }  
21. private:  
22. int id;  
23. };  
25. int main()  
26. {  
27.     Object *p;  
28.     p = new Object(10);  
29.     p->sayHi();  
30. delete p;  
31. //free(p);
32. return 1;  
33. }  

编译运行，结果是：

将delete p换成free(p)：

没有执行析构函数，如果在object的析构函数种有释放内存的操作将不会被调用，造成内存泄漏。

再看一段代码

[cpp] view plaincopy

在CODE上查看代码片

派生到我的代码片

1. #include<iostream>
2. #include<stdlib.h>
3. using namespace std;  
5. class Object  
6. {  
7. public:  
8.     Object(int i):id(i)  
9.     {  
10.         buffer = new double[10];  
11.         cout<<"Constructor"<<endl;  
12.     }  
13.     ~Object()  
14.     {  
15. delete[] buffer;  
16.         cout<<"Destructor"<<endl;  
17.     }  
18. void sayHi()  
19.     {  
20.         cout<<"Hi,I am No."<<id<<endl;  
21.     }  
23. private:  
24. int id;  
25. double *buffer;  
26. };  
28. int main()  
29. {  
30.     Object *p;  
31.     p = (Object*)malloc(sizeof(Object));  
32.     p->sayHi();  
33. delete p;  
34. return 1;  
35. }  

运行结果：

首先是编译没有问题，运行也正常，程序无崩溃。

首先是用malloc分配内存，然后用类型转换转换城(Object *)类型，成员变量为0；

delete的时候，会调用对应的析构函数，当尝试delete在构造函数中的buffer的时候，这个时候buffer是NULL，而delete NULL什么都不会发生。

static 对象何时析构？

静态成员变量的构造和初始化是在程序进入点《main函数》之前 析构在main()函数退出之前 至于顺序，我想和各个文件的编译顺序有关。

说一下函数调用堆栈，保存现场保存了哪些变量?

在c语言程序的入口其实不是main函数，在main函数之前c标准库的代码首先被执行，这段代码设置程序运行环境包括函数调用栈。对于每一次调用（包括调用main函数）的大致流程如下：

1、push ebp 将esp入栈 2、movl esp, ebp 将esp赋值到ebp 3、sub esp, XXX 在栈上分配XXX字节的临时空间 4、push XXX 保存名为XXX的寄存器

对于没有使用局部变量的函数第三步是可选的，第四步也是可选的用于保证调用前后XXX寄存器的值不变。 函数返回的流程大致如下： 1、pop XXX 恢复寄存器XXX的值 2、mov esp, ebp 回收之前分配的临时空间 3、pop ebp 恢复ebp之前的值（重新指向上一个函数的堆栈） 4、ret 栈中弹出返回地址，返回调用者

扩展

malloc/free和new/delete的本质区别

malloc/free是C/C++语言的标准库函数，new/delete是C++的运算符。 对于用户自定义的对象而言，用maloc/free无法满足动态管理对象的要求。对象在创建的同时要自动执行构造函数，对象在消亡之前要自动执行析构函数。由于malloc/free是库函数而不是运算符，不在编译器控制权限之内，不能够把执行构造函数和析构函数的任务强加于malloc/free。因此C++需要一个能完成动态内存分配和初始化工作的运算符new，以及一个能完成清理与释放内存工作的运算符delete。

c++代码编译城可执行文件的过程

1.编译预处理：宏定义指令、条件编译指令、头文件包含指令；

2.编译、优化阶段： 编译程序所要作得工作就是通过词法分析和语法分析，在确认所有的指令都符合语法规则之后，将其翻译成等价的中间代码表示或汇编代码。

3.汇编过程：把汇编语言代码翻译成目标机器指令的过程。

4.链接程序：静态链接和动态链接。

编译阶段将源程序（*.c)转换成为目标代码（，一般是obj文件，至于具体过程就是上面说的那些阶段），连接阶段是把源程序转换成的目标代码（obj文件）与你程序里面调用的库函数对应的代码连接起来形成对应的可执行文件（exe文件）就可以了

数据结构相关

限长优先级队列的实现

         通常优先级队列用在操作系统中的多任务调度，任务优先级越高，任务优先执行（类似于出队列），后来的任务如果优先级比以前的高，则需要调整该任务到合适的位置，以便于优先执行，整个过程总是使得队列中的任务的第一任务的优先级最高。 　　优先级队列有两种：最大优先级队列和最小优先级队列，这两种类别分别可以用最大堆和最小堆实现。。一个最大优先级队列支持的操作如下操作： INSERT(S,x)：把元素x插入到集合S. MAXIMUM(S)：返回S中具有最大关键字的元素. EXTRACT_MAX(S)：去掉并返回S中的具有最大关键字的元素. INCREASE_KEY(S,x,k)：将元素x的关键字的值增加到k，这里k值不能小于x的原关键字的值。

    堆的实现就是一棵平衡二叉树，性质为：让二叉树中的每一个节点的key（也就是优先级）值比该节点的子节点的key值大。

     让这棵二叉树总是保持为完全二叉树（且不破坏大根堆特性），这样树高就会是lgn，那么入队和出队操作的时间复杂度就是O(lgn)。这就比较理想了。

     另外，考虑到这个树要保证的性质只有大根堆特性，那么可以让这棵二叉树总是保持为完全二叉树（且不破坏性质A），这样树高就会是lgn，那么入队和出队操作的时间复杂度就是O(lgn)。这就比较理想了。 　　对于一棵完全二叉树，我们可以用数组（而不是链表）方式来实现。因为对于数组实现的完全二叉树，index为i的节点，它的父节点的index是i/2，左子节点的index是i*2，右子节点的index是i*2+1。乘2和除2都是可以通过位移来实现的，效率上很好。而且通过保存元素个数，可以O(1)时间只找到处于树的最未的那个元素。用数组来实现还有一个好处，就是不需要在数据结构中再实现对父、子节点的指针存储，这样也省下了不少空间。这些特点都非常适合（也很好地改善了）优先级队列的实现。

Hash表和map的区别

其实就是比较哈希表和红黑树。

构造函数。hash_map需要hash函数，等于函数；map只需要比较函数(小于函数). 存储结构。hash_map采用hash表存储，map一般采用红黑树(RB Tree)实现。因此其memory数据结构是不一样的。

适用情况： 总 体来说，hash_map 查找速度会比map快，而且查找速度基本和数据量大小无关，属于常数级别;而map的查找速度是log(n)级别。并不一定常数就比log(n) 小，hash还有hash函数的耗时，明白了吧，如果你考虑效率，特别是在元素达到一定数量级时，考虑考虑hash_map。但若你对内存使用特别严格，希望程序尽可能少消耗内存，那么一定要小心，hash_map可能会让你陷入尴尬，特别是当你的hash_map对象特别多时，你就更无法控制了，而且 hash_map的构造速度较慢。 权衡三个因素: 查找速度, 数据量, 内存使用。

Android相关

Android系统层次

Android root原理，是否可以还原？

Android的内核就是Linux，所以Android获取root其实和Linux获取root权限是一回事儿。 你想在Linux下获取root权限的时候就是执行sudo或者su，接下来系统会提示你输入root用户的密码，密码正确就获得root权限了。Android本身就不想让你获得Root权限，大部分手机出厂的时候根本就没有su这个程序。所以你想获得Android的root权限，第一步就是要把编译好的su文件拷贝到Android手机的/system/bin或者/system/xbin/目录下。我们先假设你可以把su放在xbin下，接下来你可以在Android手机的adb shell或者串口下输入su了。 Linux下su以后输入密码就可以root了，但Android里的su和Linux里的su是不一样的，Android里的su不是靠验证密码的，而是看你原来的权限是什么。意思就是如果你是root，那你可以通过su切换到别的用户，比如说shell,wifi,audio什么的。但如果你是root之外的其他用户，就不能切换回root了，会提示你permission denied。

其实Android系统的破解的根本原理就是替换掉系统中的su程序，因为系统中的默认su程序需要验证实际用户权限（只有root和 shell用户才有权运行系统默认的su程序，其他用户运行都会返回错误）。而破解后的su将不检查实际用户权限，这样普通的用户也将可以运行su程序， 也可以通过su程序将自己的权限提升。手机Root后，最重要的是，给手机安装了su程序和superuser apk。 su一般被安装在/system/xbin 或者 /system/bin 下面。 可以理解成root 破解就是在你系统中植入“木马su”，说它是“木马”一点儿都不为过，假如恶意程序在系统中运行也可以通过su来提升自己的权限的这样的结果将会是灾难性 的。所以一般情况下root过手机都会有一个SuperUser应用程序来让用户管理允许谁获得root权限，也算是给系统加了一层保险吧！

还原的话讲原来的su替换即可。

android中system和root用户有什么区别？

         Root是Linux等类UNIX系统中的超级管理员用户帐户，该帐户拥有整个系统至高无上的权利，所有对象他都有可以操作的权利，所以很多黑客在入侵系统的时候，都要把权限提升到Root权限，也就是将自己的非法帐户添加到Root用户组。类比于Administrator是Windows NT内核系统中的超级管理员用户帐户，也拥有最高的权限。但不同的是，在WINDOWS下Administrator的资源和别的用户资源是共享的，简单的说，别的用户可以访问Administrator的文件。而Linux中，别的用户是不能访问Root用户的家目录(/root)下文件的。因此，Linux比Windows更安全。 　　由于Root权限对于系统具有最高的统治权，便可方便的对于系统的部件进行删除或更改。

         system也是Linux的一个用户名，常见的情形为在未破解的Android手机上，当你链接真机在PC上执行adb shell时，adb 是以system的用户规则进行操作的。system与普通的App区别在于为了整个Android系统的运行在"/"目录下有一些"system"生成的目录及文件。

从操作系统的角度描述Android运行一个app。

        每一个Android应用程序进程都有一个Dalvik虚拟机实例。这样做的好处是Android应用程序进程之间不会相互影响，也就是说，一个Android应用程序进程的意外中止，不会影响到其它的Android应用程序进程的正常运行。         每一个Android应用程序进程都是由一种称为Zygote的进程fork出来的。Zygote进程是由init进程启动起来的，也就是在系统启动的时候启动的。Zygote进程在启动的时候，会创建一个虚拟机实例，并且在这个虚拟机实例将所有的Java核心库都加载起来。每当Zygote进程需要创建一个Android应用程序进程的时候，它就通过复制自身来实现，也就是通过fork系统调用来实现。这些被fork出来的Android应用程序进程，一方面是复制了Zygote进程中的虚拟机实例，另一方面是与Zygote进程共享了同一套Java核心库。这样不仅Android应用程序进程的创建过程很快，而且由于所有的Android应用程序进程都共享同一套Java核心库而节省了内存空间。

Android系统如何保护app种的sql数据不被篡改？

        未曾Root过的手机，每个App只能访问自己的data文件夹下的数据库，没有访问其他app/data文件夹的权限,所以无法随意修改其他应用的sqlite数据。

        Root过的手机都可以进入到/data/data/<package_name>/databases目录下面，在这里就可以查看到数据库中存储的所有数据。如果是一般的数据还好，但是当涉及到一些账号密码，或者聊天内容的时候，我们的程序就会面临严重的安全漏洞隐患。

其他

看你搞过网站的东西，会Node.js么？

“有听过，但没弄过。”

会网络编程么？

“不会。”

那今天就面到这里，后面有需要的话我们会联系你。

“嗯。”

最后

现在回想起来，基本只答出来了一半不到，幸亏之前有看了一些C++的书，不然可能就是15分钟就88了。

基础不好是根本原因，缺乏面试的经验也是一方面。

借同学的一句话，“幸亏你面的不是XX游戏开发，不然你幼小的心理将会受到毁灭性的打击。”

现在的感觉就是10分钟单中的冥界亚龙，数据是0杀1死0助攻，装备是草鞋三树枝,兜里有400块。买一个圆盾，一个回城，继续飞中。

嗯，节奏很差。

现在能做的只能是补好每一个兵，稳扎稳打，然后抓住每一个机会，把局势掌握在自己手里。