9.14 第三次面试 电话面试

还是复试，算上上一次，就是第二次复试了
渲染管线
内存池
pbr brdf
玩过什么游戏
欧拉角
游戏用到的网络协议
内存管理
线程间的无锁通信

GG了，好多都不会。估计自己学着写一个渲染器会好一点

9.5 第二次面试

acm经历、美赛经历
说一下new，delete可能出现的问题
有没有避免new、delete的方法
share_ptr和unique_ptr的使用
10000张扑克牌，随机洗牌
说一说渲染
怎么学习的计算机图形知识
有没有做过系统的客户端、并发的呢
生产者和消费者模型
信号量
读过的英文文献、技术文章

反问：
周六还上班么
工作室：timi

感受：
感觉自己菜鸡了，洗牌那个之前有看到过、但是全忘了。智慧指针就从来没用过。

9.6 第二次后台&综合 笔试 --- 笔试邀请已拒绝。

8.31 第一次面试

介绍自己游戏客户端相关的项目 5min
问了下实习的项目 具体问到了simd

c++：
c++的类型转换有哪几种
c++的lamda表达式，捕获方式有哪些
智能指针和垃圾回收
c++的移动语义和完美转发

4个题：

1. 
2. 已知向量|A|=|B|=|C|=1,A+B+C=0。求A*B+B*C+C*A,*是点乘。
3. 
4. 10个问题&5分钟，问出考官心里的词

8.23 后台&综合 笔试场

牛客五个编程题

1. 给n个数的链表，输出去除第k个数后的链表。

不需要真正实现链表。

2. 给N=5000长度的字符串，问在去重后的N所有子序列里，字典序第k小的，k<=5。

取出每个字符和它的下一个（两个、三个、四个）字符组成的 共 5*N个子序列， 这些子序列的长度不超过5，sort这些子序列后取不重复的第k小的串。

3. 给一个正数n，n最大1e12，取俩非负数a、b满足：a+b=n ，求最大的s(a)+s(b) ， s(x)表示的是x的每一位的数字之和。有100个case。

a取 0，9，99，999，9999 ，... 里最靠近n的那个数，b取n-a，最后算一下sa和sb。

4. 给N=5000个宽度为1的木板的高度a[I]，高度范围1e9正整数，问用一把宽度为1的刷子最少刷几次能把木板都刷完。这里的刷子可以横着刷 也可以竖着刷，横着刷的时候不能越过板子，木板底部对齐。

这个题我的解法是错的，时间复杂度太大，还是写上这个错误的O（N^3）解法：

DP[I][J] 表示前i个木板被刷完、而且第i个木板的1~j米是横着刷完的 刷的最小次数。

初始化：DP[0][X]=X, DP[X][Y]=N

递推: 1. DP[I][J] = min( DP[I-1][K]+1+J-K )， 这里的J取0~a[I] ，这个意思是前一个底部横着刷有k个，现在的底部想刷j个的话，就需要额外的j-k次刷墙，另外需要一次竖着刷。
2. DP[I][ A[I] ] = min( DP[I-1][ K ] + A[I] -K )，这个式子是说横着刷a[I]高度的时候，就不需要额外竖着刷一下了。 注意a[I]如果大于N，就不需要第2个递推了。

这个算法是O（N^3） （IJK范围都是占5000），交上去T掉。

剪枝：K取 J-20~J 范围， 卡过去了。

5. N=400长度的字符串，1e5个询问，每次问[L,R]的子序列的最小拆分次数，拆分是把一个子序列拆成连续的子子序列，每个子子序列必须是回文字符串。

N^3预处理一个二维布尔数组m[I][J]，表示[I,J]子序列是不是回文串。用马拉车算法更快。
把m[I][J]==true看作是路径长度为1的路径，m[I][J]==false看作长度是400的路径。每条路径的起点是i，终点是j+1。
floyd算法算出每一对i，j的距离，这个距离就是它要询问的东西。

踩踩github，点个关注北