|
面试分为项目经历介绍以及基础知识。基础知识考察分为三部分：最多的为考察C/C 、STL相关；第二部分是图形学基础渲染算法，考察频率也较高；第三部分简略考察计算机基础知识、图形的数学、数据结构与算法。 第一部分：C/C 语法，STLSTL
指针
第二部分：计算机基础计算机基础
数据结构与算法
第三部分：图形学基础算法
基本出自这个网站：Learn OpenGL 其他：
[问题列表待更新] [以下为粗略解答，后续校订、润色] STL
new和malloc内部的实现方式有什么区别？
C 内存划分类型？
vector 数组差别在于空间灵活性 vector 的 size 和 capacity 的区别 size是当前vector容器真实占用的大小，也就是容器当前拥有多少个容器。 capacity是指在发生realloc前能允许的最大元素数，即预分配的内存空间。 vector 扩充 capacity？ 配置新空间/数据移动/释放旧空间。
list，非连续存储结构，具有双链表结构，因此支持前向/后向遍历。支持高效的随机插入/删除操作，但随机访问效率低下。
clear删除储存在vector中的所有元素. 调用clear之后, vector的尺寸(size)将变成zero. 但它的容量(capacity)却并不发生变化, vector本身并不释放任何内存。 如果vector的元素是一些object, 则它将为当前储存的每个元素调用它们各自的析构函数(destructor). 然而, 如果vector储存的是指向对象的指针, 此函数并不会调用到对应的析构函数 如果你想同时做到清空vector的元素和释放vector的容量, 你可以使用swap技巧(此技巧并非在所有环境中都管用 e.g. not with Intel Compiler 10.0.69 and LINUX 2.6.9-89 x64) vector的clear操作的内部过程
该函数将一个新的元素加到vector的最后面，位置为当前最后一个元素的下一个元素，新的元素的值是val的拷贝。 该方法可以快速有效率地在数组size范围内增长元素，除非当增长的元素个数大小超出了vector的capacity的时候才会发生重分配。
假定有 n 个元素,倍增因子为 m。那么完成这 n 个元素往一个 vector 中的push_back操作，需要重新分配内存的次数大约为 logm(n)，第 i 次重新分配将会导致复制 m^i (也就是当前的vector.size() 大小)个旧空间中元素，因此 n 次 push_back操作所花费的总时间约为 n*m/(m - 1):  时间复杂度计算 很明显这是一个等比数列.那么 n 个元素，n 次操作，每一次操作需要花费时间为 m / (m - 1)，这是一个常量. 所以，我们采用均摊分析的方法可知，vector 中 push_back 操作的时间复杂度为常量时间.
随机访问，数据增删，内存使用效率
双链表
map内部实现了一个红黑树，该结构具有自动排序的功能，因此map内部的所有元素都是有序的，红黑树的每一个节点都代表着map的一个元素，因此，对于map进行的查找，删除，添加等一系列的操作都相当于是对红黑树进行这样的操作，故红黑树的效率决定了map的效率。 有序性，这是map结构最大的优点，其元素的有序性在很多应用中都会简化很多的操作。红黑树，内部实现一个红黑书使得map的很多操作在lgnlgn的时间复杂度下就可以实现，因此效率非常的高 unordered_map内部实现了一个哈希表，因此其元素的排列顺序是杂乱的，无序的。因为内部实现了哈希表，因此其查找速度非常的快，但哈希表的建立比较耗费时间。
开放定址法（再散列法）
链地址法（拉链法）
a是str，s是seed。这个哈希函数的好坏首先取决于
不是所有的奇数都满足第二条，但是131是满足的。
迭代器是一种面向对象的广义指针，用于指向容器中或流中的对象。可以看做是一种指向数据的指针。 向容器中添加或者删除元素的操作可能会使指向容器元素的迭代器失效，失效的迭代器将不指向任何元素。 一般有两种情况无法通过迭代器 操作遍历整个stl容器; 无法通过迭代器存取迭代器所指向的内存。 eg. vector 使用erase不当，使用erase删除某一个结点之后，vector迭代器虽然还是指向当前位置，而且也引起了元素前挪，但是由于删除结点的迭代器就已经失效，指向删除点后面的元素的迭代器也全部失效，所以不能对当前迭代器进行任何操作；需要对迭代器重新赋值或者接收erase它的返回值；
STL 语义上不提供任何强度的线程安全保证。使用 STL 做多线程编程是基于你对实现的了解的。因此你这个问题不可能有一个简单的回答，假如你读的时候（锁定的情况下）获取了引用，而随后的写触发了重新分配，那照样会有问题。读还有一致性的问题，而在 vector 上你大体上只能（通过锁）获得按照索引原子读取一个值这样的能力，索引、多次读之间都可能不一致。 指针
虚函数主要是用来实现多态和多重继承的 动态单分派子类型多态，运行时决定，基于一个类型，以子类型-超类关系实现多态。 定义一个函数为虚函数，不代表函数为不被实现的函数。 定义他为虚函数是为了允许用基类的指针来调用子类的这个函数。 定义一个函数为纯虚函数，才代表函数没有被实现。 定义纯虚函数是为了实现一个接口，起到一个规范的作用，规范继承这个类的程序员必须实现这个函数。
都会有一个虚函数表vtable，表的第一个位置放的是跟运行时有关的东西（RTTI），然后就是根据你类中虚函数的声明次序来存放。然后，在每一个类对象中，都会含有一个指向虚函数表的指针vtpr，在程序运行时，会根据类的动态类型的，通过vtpr从而找到相应的vtable，从而执行某个虚函数正确的版本。
简单总结一下就是类只有成员变量占用内存（静态成员不占类内部内存，函数不占内存）。如果有虚函数，每个类对象都会有一个虚函数指针Vptr（占用一个指针大小的内存），vptr指向一个虚函数表，表里面记录了各项标记virtual的函数，子类如果覆盖父类虚函数，对应虚表位置的虚函数会被子类的替换。如果是虚继承，还会有虚基类表记录当前对象相对虚基类的偏移，以及一个虚基类指针指向这个虚基类表。 虚表在编译完成时大小与布局就被决定了，加载时其内存位置也就被确定了。
《Effective C 》条款9：永远不要在构造函数或析构函数中调用虚函数。
模板是泛型编程的基础，泛型编程即以一种独立于任何特定类型的方式编写代码。 模板是创建泛型类或函数的蓝图或公式。库容器，比如迭代器和算法，都是泛型编程的例子，它们都使用了模板的概念。 每个容器都有一个单一的定义，比如 向量，我们可以定义许多不同类型的向量，比如 vector <int> 或 vector <string>。
shared_ptr在原始指针周围包装引用计数机制。所以对于shared_ptr的每个实例，引用计数增加1。如果两个share_ptr对象引用他们，他们永远不会被删除，因为他们永远不会结束一个引用计数为零。 weak_ptr指向一个shared_ptr，但不增加它的引用计数。这意味着即使有一个weak_ptr引用，仍然可以删除underying对象。 这种方式的工作原理是，weak_ptr可以用来创建一个shared_ptr，每当有人想要使用基础对象。然而，如果对象已经被删除，则返回shared_ptr的空实例。由于底层对象上的引用计数不会随weak_ptr引用而增加，因此循环引用不会导致底层对象未被删除。
如何修改shared_ptr智能指针，让他支持多线程？
Effiective C 3rd edition. Item 7: Declare destructors virtual inpolymorphicbase classes. 就是要避免base class的无效释放以造成memory leak。 什么时候用呢，可以说只要涉及到继承的多样性，基本上基类就逃不过虚析构函数了。
静态动态(编译时多态):主要通过函数和运算符重载来实现; 动态动态(运行时多态):主要通过继承和虚函数来实现.
当首次为每个类型调用函数模板时，编译器会创建一个实例化。每个实例化是专用于该类型的模板化函数版本。每次将该函数用于该类型时，此实例化都将调用。如果有几个相同的实例化，即使在不同的模块中，也只有该实例化的一个副本将在可执行文件中结束。 函数模板实例化
在分离式编译的环境下，编译器编译某一个.cpp文件时并不知道另一个.cpp文件的存在，也不会去查找（当遇到未决符号时它会寄希望于连接器）。这种模式在没有模板的情况下运行良好，但遇到模板时就傻眼了，因为模板仅在需要的时候才会实例化出来，所以，当编译器只看到模板的声明时，它不能实例化该模板，只能创建一个具有外部连接的符号并期待连接器能够将符号的地址决议出来。然而当实现该模板的.cpp文件中没有用到模板的实例时，编译器懒得去实例化，所以，整个工程的.obj中就找不到一行模板实例的二进制代码，于是连接器也黔驴技穷了。 C 中的模板类声明头文件和实现文件分离后，如何能实现正常编译？Export Template，即外名模板，它的作用在于使得模板代码可依照C/C 语言习惯，将模板声明和实现分开分别放到.h和.cpp文件中，并且可以减少冗长的模板编译时间（否则同一模板实例需要在不同编译单元中分别实例化）。
Overload(重载)：在C 程序中，可以将语义、功能相似的几个函数用同一个名字表示，但参数或返回值不同（包括类型、顺序不同），即函数重载。 （1）相同的范围（在同一个类中）； （2）函数名字相同； （3）参数不同； （4）virtual关键字可有可无。 Override(覆盖)：是指派生类函数覆盖基类函数，特征是： （1）不同的范围（分别位于派生类与基类）； （2）函数名字相同； （3）参数相同； （4）基类函数必须有virtual关键字。 Overwrite(重写)：是指派生类的函数屏蔽了与其同名的基类函数，规则如下： （1）如果派生类的函数与基类的函数同名，但是参数不同。此时，不论有无virtual关键字，基类的函数将被隐藏（注意别与重载混淆）。 （2）如果派生类的函数与基类的函数同名，并且参数也相同，但是基类函数没有virtual关键字。此时，基类的函数被隐藏（注意别与覆盖混淆）。
如果派生类在虚函数声明时使用了override描述符，那么该函数必须覆盖其基类中的同名函数，否则代码将无法通过编译。 如果派生类里面是像覆盖虚函数 就加上关键字override 这样编译器可以辅助检查是不是正确覆盖，如果没加这个关键字 也没什么严重的error 只是少了编译器检查的安全性 计算机基础
小结TCP与UDP的区别：
线程是进程的一个实体,是CPU调度和分派的基本单位,它是比进程更小的能独立运行的基本单位.线程自己基本上不拥有系统资源,只拥有一点在运行中必不可少的资源(如程序计数器,一组寄存器和栈),但是它可与同属一个进程的其他的线程共享进程所拥有的全部资源.
红黑树（英语：Red–black tree）是一种自平衡二叉查找树，是在计算机科学中用到的一种数据结构，典型的用途是实现关联数组。它是在1972年由鲁道夫·贝尔发明的，他称之为'对称二叉B树'，它现代的名字是在Leo J. Guibas和Robert Sedgewick于1978年写的一篇论文中获得的。它是复杂的，但它的操作有着良好的最坏情况运行时间，并且在实践中是高效的：它可以在Ologn时间内做查找，插入和删除，这里的n是树中元素的数目。
设计模式（Design Pattern）是一套被反复使用、多数人知晓的、经过分类的、代码设计经验的总结。使用设计模式的目的：为了代码可重用性、让代码更容易被他人理解、保证代码可靠性。设计模式使代码编写真正工程化；设计模式是软件工程的基石脉络，如同大厦的结构一样。 游戏编程模式 程序设计
堆排序 快速排序，不断调用分治函数，直到它输出的position = K-1
蒙特卡洛，随机模拟。产生2个范围[-r,r]之间的随机数dx,dy，理论上(x dx,y dy)在{{x-r,y-r},{x r,y r}}矩形（左下角，右上角）范围内。添加判断(x dx,y dy)距离圆心的距离小于r即可。 CDF
Loading... /**
动态规划 图形学
圆上任选三点组成三角形，这个三角形是锐角、钝角和直角三角形的概率分别是多少？
判断点是否在三角形内
两个三角形香蕉 首先判相交，从两个三角形上分别枚举一条线段判断是否相交， 如果不相交，枚举一个三角形的顶点判断是否在另一个三角形内， 如果也互不包含，那么剩下就是相离这种情况了， 上述涉及到的所有判定都只需要利用叉积判断方向。 N个？ 来源：葡式蛋挞 - 计算机图形学 |
|
|
这个序列的循环周期，如果周期很短的话，周期之后的字符就会乘以和前面的某个对应字符相同的系数，这样很容易产生碰撞。这个hash函数足够好的条件是：
