算法工程师面经 百寒拼菇腾作网3娱快书p字 附答案
寒武纪：深度学习工程师
2019.7.16一面：电话面 全程打断buff
1、自我介绍
2、Python和C++的区别（答了很多python的特性）
3、Python为什么会慢？
答：因为不知道数据类型，取数据要判断一下。
(1、python是一个动态的解释型语言；python中的值不是存储在缓存区而是分散的存储在对象中
3、看过那些书（答：python高性能编程）
4、什么是内存泄露？什么时候会内存泄露？
没有删掉。
(动态申请的内存空间没有被正常释放，但也不能继续被使用的情况。没有释放内存)
5、关闭程序的术语？
不知道！
(可能是关闭进程，不确定)
6、指针和引用？什么时候用指针什么时候引用？
(指针可以不初始化，引用必须初始化，且绑定后不能再变；向函数中传递指针和传递指针的引用的区别：
传递指针，会先复制该指针，在函数内部使用的是复制后的指针，这个指针与原来的指针指向相同的地址，如果在函数内部将复制后的指针指向了另外的新的对象，那么不会影响原有的指针；
对于传递指针引用，如果将传递进来的指针指向了新的对象，那么原始的指针也就指向了新的对象，这样就会造成内存泄漏，因为原来指针指向的地方已经不能再引用了，即使没有将传递进来的指针指向新的对象，而是在函数结束的时候释放了指针，那么在函数外部就不能再使用原有的指针了，因为原来的内存已经被释放了)
7、知道那些数据结构？
答：堆 数组 列表 栈
8、什么是堆？
答：平时只用数组模拟堆，不知道真实的结构，认为是父节点-子节点这样状态的数据结构（超高频问题，一般由程序员分配释放， 若程序员不释放，程序结束时可能由OS（操作系统）回收。分配方式类似于链表。向上增长，栈的分割开辟在程序运行时进行，内核顺着链表找到一块足够大的空间交给程序，如果没找到就析构调无用内存再找一次，更具体的请自行总结一下并时常复习，区别包括申请方式、系统响应等很多）
9、堆和栈的区别
栈就是存东西的空间，往最里面存，出来是最外面出来（超高频问题，函数运行时分配，函数结束时释放。由编译器自动分配释放 ，存放为运行函数而分配的局部变量、函数参数、返回数据、返回地址等。向下开辟，速度很快，局部性能好的话会和寄存器交互，存PC指针，函数参数多也会组成栈帧存到栈里面）
10、进程和线程
（超高频问题，我看了深入理解计算机系统后的总结：1、进程就是活着的程序，程序不过是一些文本，运行着的程序就是进程，是系统进行资源调度和分配的基本单位，掌握资源，包括内存等，线程就是轻量级进程，是CPU调度和分派基本单位。2、由于进程占有资源，压栈和出栈慢，所以切换不灵活，线程不占资源，只占必要的资源（递归要压栈所以有一点资源），所以线程容易通信->在进程分来的内存中直接通信，容易并发->切换灵活，同一进程的线程切换速度很快，因此线程开销小3、地址空间，进程独立，同一进程的线程共享资源，对其他进程的线程独立）
自我介绍。随便面面就不套路了，就随意简单介绍一下。
全程面试官语音冷漠，感受不到面试情况的反馈。
C++基础：
1、include的时候怎么避免重复include
ifdef(当时就说了这个词，懂得自然懂)
2、static
static对全局变量，限制全局变量作用范围。链接的时候，变量被分为内部、外部、全局。全局变量就是这个可重定位文件内部的全局变量，外部变量就是外部文件的全部变量，内部变量就是static修饰的变量。作用域就是先全局变量(对应当前的全局变量、然后再内部再外部)内部变量重定位的时候，外部变量无法通过自身外部变量的指示找到这个变量，就实现了保护？还是屏蔽？总之就是限定作用域。
static修饰局部变量，存储位置就从栈变为静态存储区，(生命周期变长)，函数迭代的时候就可能用到上一次的局部变量。
static修饰类内变量，存储位置从类里面转移到外部，这样所有的类实体公用(或共用)一个变量。
static修饰类函数，类函数因为在外面，看不见类的变量，所以只能看到类的static变量，也只能使用它，不能用别的变量。
其他的想不起来了。
(还有初始化为0这个功能。解决重定义的功能:就是把变量限制在本文件中，和上面一个意思，最好都说出来)
3、static类内函数和类内普通有什么区别？
感觉答上一个题的时候答完了，复述一下，提到static变量是共享的要注意就结束。
4、extern用过吗
我说链接的时候，extern就是外部的全局变量，就去找。巴拉巴拉。
还有其他的功能吗？答没想起来。
(还有这个，链接指示功能，extern"C"就是用C语言的方法去搞，类比得出extern"其他语言"，估计面试官想让我答这个，除了背谁能想到，大家都会用，谁不知道还有这个功能，灯下黑。。。和static默认初始化0一样没答出来)
5、malloc和free
malloc的功能是隐式空闲链表(不是通用分配器用的方法，是简单的实现)，找一合适大小空闲空间挖出来返回，先找一下，找不到申请帮助，内核会合并相邻小碎片，重新找一次，找不到就调什么什么brk还是rbk去申请更大的空间(sbrk函数)，然后返回的是void*，需要我们自己强制类型转换成需要的类型。malloc是库函数。
那么new呢？运算符，可以重载，如果没申请出来就中断。malloc返回空。new还是一个就是可以输入类型符，就是new个int，然后算大小他会把int的大小算进去，malloc需要自己算。一个存储区上一个在堆上，这两个的区别是巴拉巴拉。
(new会调构造函数、malloc不构造函数)
6、堆和自由存储区区别？
(我不是刚说了么)堆是C的概念，自由存储区是C++的概念，两者在概念上有根本的不同，但C++沿袭了C，实际使用的是一块空间。
7、malloc后的返回值是一个指针，然后这个指针可以加数吗？
可以加。(指针不就随便加)
能吗？那么这个值+了几个数后在free会怎么样？
懂了，面试官上一个问的应该是这个含义->新空间的首地址，可以加么。不可以加，这样free的时候内存泄露。
8、你有没有检测过内存泄露。
没检测过。我程序最大的问题是重复析构，当时想办法解决了这个问题。巴拉巴拉。为什么会这样，巴拉巴拉。如何解决巴拉巴拉。
(问了问收割大佬，以下是原话：VS有个CRTDBG可以打印内存开辟和内存释放，也可以对内存使用情况快拍，这是VS工具，单独的工具有bound_checker，功能是类似的其实。Linux是Vargrind)
9、内存泄露会怎么样？
和面试官同时回答:占得空间越来越大。
10、重复析构会报错啊？
是的。我的软件中间有一段时间会在主程序在退出的时候会把申请的空间释放掉，所以关程序会报错(程序崩掉，就是弹出一个报错框，0x什么什么，一个大数字)。
11、智能指针？
用python的角度介绍了智能指针，计数法析构内存，python是引用自动析构内存，没有显式指针可用，用的是引用，被引一次就+1，不被引了就-1。为的0的时候，我们就找不到这块变量了，就自由析构了。
一边讲一边想到面试官可能要问循环引用了，就讲python本身解决不了，用的是gc垃圾收集器定位然后析构掉。C++用的是weak_ptr解决这个问题。(点到即止，懂得自然懂，面试官想问就问不问拉倒)
12、智能指针转普通指针注意什么？
说没转过，懒得分析说不会。
(找了另一个工具人大佬问了问，大佬说智能指针的作用就是帮你把这些东西封装成比较安全的使用的类，如果把share的指针转化为普通指针，这个时候share的又自动释放掉了这个东西，如果这时候此指针当普通指针用，会用到已经被释放掉的东西。而weak_ptr转换为普通指针的时候，不会改变计数，引发访问到已被释放空间的时候，就会报错，发生如此之风险)
13、调试的怎么调的？
打cout。(憨的一批)
14、还有呢？
用调试器，然后普通调试器不好，有的调试器对于地址，不显示地址对应的值还是只显示地址的值(臭codeblock)，然后下了个牛逼的版本可以显示的。后面用python，notebook好用的一批，随便调试。
16、用过tensorflow吗？
顺势讲项目，从头到尾，心路历程，中间结果，最后结果，得出结论。我知道，这些东西既可以拖时间，拖完时间面试官往往还会非常满意。
17、损失函数？
logloss啊，多分类。然后面试官又问了一遍题目，就讲了优化的几种，自己的尝试和效果。然后分析自己的项目里损失曲线的特点和原因。
18、忘了。
反问。
寒武纪的深度学习是在做一个基础性平台供算法工程师使用，还是做一个解决方案配套一个任务啊？
介绍项目
一面90分钟
先做两道题：
1、从数组找三个数，三和与value差最小
要求时间O(n2)空间O(1)
排序要求用快排
2、字符串A 、B，B占A最短的子序列（A中最短的子序列包含B）
面试官和我都笑了，因为python切片+in操作符四行结束，面试官也笑了，于是我们约定in这一步自己写函数。
暴力解决一切花里胡哨
1、介绍Kaggle比赛（从EDA开始到最后）
2、ID3\C4.5等基本树 是二叉树还是多叉树 被切过的特征还会再切吗
离散特征(离散数量>2)是多叉分类，连续是二叉分裂，连续可以在切，离散不可以（当时回答的是可以再切，被提示后意识到不可再切，说了自己的matlab实现，先做集合，遍历特征，保存最大的信息增益位置，然后对特征切分，切分后把这个特征从集合中删掉，所以离散特征切完就不在切了，还好反应过来了，连续性特征可以再切，详情可以去看看别人的ID3树和其他树的源代码）
3、介绍BN
4、GBDT和RF哪个树比较深
RF深。说了boost和bagging的思想。boost使用低方差学习器去拟合偏差，所以XBG和LGB有树深的参数设置，RF是拟合方差，对样本切对特征切，构造多样性样本集合，每棵树甚至不剪枝。
5、XGB特征重要性程度是怎么判断的？
答：不清楚，但是用的很多，猜测是按分裂点的次数（在所有树的出现次数），只说了这一点
(gain 增益意味着相应的特征对通过对模型中的每个树采取每个特征的贡献而计算出的模型的相对贡献。与其他特征相比，此度量值的较高值意味着它对于生成预测更为重要。
cover 覆盖度量指的是与此功能相关的观测的相对数量。例如，如果您有100个观察值，4个特征和3棵树，并且假设特征1分别用于决策树1，树2和树3中10个，5个和2个观察值的叶结点;那么该度量将计算此功能的覆盖范围为10+5+2 = 17个观测值。这将针对所有决策树结点进行计算，并将17个结点占总的百分比表示所有功能的覆盖指标。
freq 频率（频率）是表示特定特征在模型树中发生的相对次数的百分比。在上面的例子中，如果feature1发生在2个分裂中，1个分裂和3个分裂在每个树1，树2和树3中;那么特征1的权重将是2 1 3 = 6。特征1的频率被计算为其在所有特征的权重上的百分比权重。)
6、XGB很容易理解它的回归和二分类，如何理解多分类呢？
谈笑中度过，一开始回答的label encode ，用onehot+softmax,但是每棵树如何是拟合softmax前一步呢。这个我确实不知道，面试官提示我说三分类，构造100棵树还是300棵，我就意识到了，回答原以为是100棵。
面试官说构造三百棵树，拟合三分类，再softmax。
(onehot之后，输入标签是一个向量，对向量中每一个预测点集成一群树)
二面55分钟
1、先问你是报的NLP方向不
2、三道题
第一题：第K大的数
讲了三种方法
方法1：堆排序 分析复杂度是O(Nlogk)(没分析错把)
方法2：快排二分 分析复杂度是O(N)
方法3：排序 查表 分析复杂度(NLogN)
要求O（N）所以用的快排二分，面试官说快排能做这道题？但快排是最快的（我知道的）也正好是要求的O（N）复杂度
(百度了一下，快排和hash最快，其余都不快）
手写python代码，但是编译不知道哪里也错了，这个IDE也不提示，面试官也很尴尬，说以前用牛客的可以报编译错了在哪 于是我就说下面的题用C++写（这个问题很严重，面试的时候找不到bug，所以一定要小心python，一定要bug free，不然老实用C++)
第二题：
地板n*3，木板1*3，几种排法
dp[n]=dp[n-1]+dp[n-3]
第三题：
有等概率1-7函数
造等概率1-10，分析调用1-7的次数期望
def rand7() def rand10(): x = 7*(rand7()-1)+rand7()-1 while x>=40: x = 7*(rand7()-1)+rand7()-1 return 1+x//4
期望不好算，是个数等比列求和，然后我就口算的近似值2.5n
百度：
效率很高，交完简历一天就面试了
研究岗
自我介绍 ，聊聊项目
对我们部分感兴趣吗：部门做日志检测 安全领域
互相了解
要开会，下次继续聊
10点：继续聊上次的内容
全程比较轻松愉快
二面结束，但是状态还是二面待安排。。。
和面试官讨论如何用机器学习的方法去处理危险日志检测。从头复习了各大机器学习器学习的知识，然后教每个模型在这个场景下的有点和问题，也算自我反省了。这里能获得的比较突出的经验就是，很多部门还是规则学习为主，对机器学习的分类情况有强烈的可解释性要求。所以树模型和LR等可解释性好的模型很受青睐呀。但最后面试官“感谢”了我，估计是暗示我挂了，桑心
通知笔试五题A了3道半，成绩也还行把，但是部门锁我简历。。。
通知了“两面”，几分钟结束，随便聊聊，说9月份现场继续面，然后就灰了
拼多多
一面：
自我介绍
科研项目介绍
Kaggle 比赛介绍
腾讯比赛介绍
RNN用过吗 用过：项目 Kaggle
LR用过吗 用过：Kaggle的二分类检测
XGB和LGB区别：
只想到三点，特征排序，特征切分和直方图和全排序
说他们共同点较多 小提一点，又小提了GBDT到XGB和LGB，然后扯了扯实际用这两个模型的感受，然后说只记得三点不同了，实际效果xgb不输LGB但是调参不好搞，而且LGB很快
(
1）更快的训练速度和更高的效率：LightGBM使用基于直方图的算法。
2）直方图做差加速：一个子节点的直方图可以通过父节点的直方图减去兄弟节点的直方图得到，从而加速计算。
3）更低的内存占用：使用离散的箱子(bins)保存并替换连续值导致更少的内存占用。
4）更高的准确率(相比于其他任何提升算法)：它通过leaf-wise分裂方法（在当前所有叶子节点中选择分裂收益最大的节点进行分裂，如此递归进行，很明显leaf-wise这种做法容易过拟合，因为容易陷入比较高的深度中，因此需要对最大深度做限制，从而避免过拟合。）产生比level-wise分裂方法（对每一层所有节点做无差别分裂，可能有些节点的增益非常小，对结果影响不大，但是xgboost也进行了分裂，带来了务必要的开销）更复杂的树，这就是实现更高准确率的主要因素。然而，它有时候或导致过拟合，但是我们可以通过设置|max-depth|参数来防止过拟合的发生。
5）大数据处理能力：相比于XGBoost，由于它在训练时间上的缩减，它同样能够具有处理大数据的能力。
6）支持并行学习。
7）局部采样：对梯度大的样本（误差大）保留，对梯度小的样本进行采样，从而使得样本数量降低，提高运算速度
)
代码水题，直接让面试官选C++还是Python，面试官(好像所有面试官回应都是一样)“你选就好”
选的python写的，如果是牛客直播间，目前最好不要用python，牛客直播间的python编辑器不行，编译几乎不作检查，编译未通过经常不知道错在哪行。
棋盘有棋子，只能左上走到右下，右走或下走，问最多经过棋子数
dp[i][j]=max(dp[i-1][j],dp[i][j-1]) if chess[i][j]=='棋子': dp[i][j] +=1 return dp[-1][-1]
二面：估计凉凉，答得不好
自带打断buff的面试官 搞思路搞得很厉害，面试体验差
1、gbdt和xgb
(gbdt、xgb、lgb凡是项目提到了一定要熟练掌握)
2、BN、Dropout
(Dropout可以作为训练深度神经网络的一种trick供选择。在每个训练批次中，通过忽略一半的特征检测器（让一半的隐层节点值为0，当然这个“一半”是超参数，自己设），可以明显地减少过拟合现象。这种方式可以减少特征检测器（隐层节点）间的相互作用，检测器相互作用是指某些检测器依赖其他检测器才能发挥作用。
Dropout说的简单一点就是：我们在前向传播的时候，让某个神经元的激活值以一定的概率p停止工作，这样可以使模型泛化性更强，因为它不会太依赖某些局部的特征。
其实就是个Bagging策略，构造子网组合。)
5、AUC知道吧，回归怎么计算AUC
不知道怎么计算，一查 根本没有..是不是我听错了 他其实想说逻辑回归的AUC怎么计算
(回归没有AUC这么一说)
6、堆和栈哪个开辟的快
脑抽完全说反了，答完很久才反应过来。说的是堆编译的时候分配好了，不用再开辟伸缩什么的快，栈要伸啊缩啊所以慢（见前面的答案，这个答错了我可以凉凉了）
7、重载和重写
(注意重写是对虚函数的重写，我当时就答错了，所谓重载就是同名函数参数表不同，编译时会对函数改名，其实运行的时候他们已经不是同名的了；重写是虚函数重写，子类对父类的非虚函数在写一遍叫重定义或者隐藏，反正不是重写，重写是对虚函数的重写)
8、大数据 买东西 找买东西最多的100个 怎么做
9、MAP底层怎么做的
我说还没看底层代码。（话说我一直不知道有MAP这种东西存在，都是手撸哈希表，准备有时间看一下STL源码分析）
(底层红黑树，一种O(log(n)的查找插入和删除数据结构，实际是2-3树，伪平衡二叉树)
10、有没有O(1) 的？恍然大悟 我擦原来还有哈希表
哈希表冲突怎么办
回答了拉链 重哈希 当前 1
(同样高频问题，拉链：链表，冲突了就在链表后 1个；探测：线性探测，二次探测，就比如当前的值 1；再哈希：多个哈希函数)
我就感觉HR贼好，于是二面的时候疯狂表达了我对HR工作的满意、支持和欣赏，二面说我的夸奖她会反馈给HR滴。所以我感觉HR面是不是已经过了，就差交叉面了。
不过我说的都是实话，我确实很喜欢她们的HR。
自我介绍，两道题
第一道：
1000以内的最大素数
说了Python能够O（1）空间实现素数生成器，筛选法，但是没写，没要求就不写，直接bool判断就好，注意从大到小
但是好像面试官不会python哦？于是改用C++下一题
第二道：
不用除法实现除法，很简单
注意我的写法里，C++里abs(一个负数)可能溢出，但是无所谓面试的时候速度A比较重要，平时要注意这些细节，而且python不会溢出
#include <iostream>
using namespace std;
int jianfa(int num1,int num2)
{
int re = 0;
bool fuhao = false;
if ((num1<0 && num2<0) || (num1>0 && num2>0))
{
fuhao = true;
}
num1 = abs(num1);//小心溢出
num2 = abs(num2);//小心溢出
if(num2==0)
{
cout<<"div zero error"<<endl;
return 0x3f3f3f3f;
}
if(num1<num2)
return 0;
int tmp=1;
while(num1>num2)
{
tmp*=2;
num2*=2;
}
num2/=2;
tmp/=2;
while(num2)
{
if(num1>=num2)
{
num1-=num2;
re =tmp;
}
num2/=2;
tmp/=2;
}
if(fuhao)
return re;
else
return -re;
}
int main() {
int num1,num2;
cin>>num1>>num2;
cout<<jianfa(num1,num2);
return 0;
} 问了很多很多：
个别想不起来了失忆了。。
1、为什么没有实习经验？
第一点老师不让找工作。（这是真话，今天老师对另一个同学说，你找到工作了吗，你找到工作但是毕不了业你说工作是不是白找了，。。。）
第二点，为了能够接触到实际工程，在科研之余，参加了比赛，巴拉巴拉。面试官可以满意。
2、LR用过吗？
必须的
3、LGB比XGB好的点？
直接介绍二者不同
4、L1、L2不同？L1为什么能稀疏？
从数学分布讲了，一个是拉普拉斯分布 一个是高斯分布；讲了图解为什么L1能稀疏，一个圈一个菱形，容易交在轴上。工程上讲了，L1的近似求导，区间内0区间外优化。然后L2是直接求导比较简单。
5、哪些学习器是凸优的呀？
LR sigmoid logloss 凸优 。线性回归，最小二乘凸优。SVM凸优。NN肯定不凸优，因为往往收敛到鞍点。PCA无数学解，但是利用特征值去做反而得到最优解。
(注意sigmoid+平方损失不是凸优化)
6、特征重要性你怎么做，例如特征组合和删除，调参你是怎么调的呀？
答：特征组合用onehot、交叉、EMBEDING。组合的话要看实际分布，讲了自己构造过的一个和标签有线性关系的组合，说自己用的是遍历的方法，用两两数学关系构造新特征，看和标签的线性关系。
特征删除等想到了某个KAGGLE大佬的特征筛选步骤，从他的kernel我也是学到了很多。
调参：
第一步祖传参数。比如树模型的深度、采样频率等，这个主要还是经验
第二部调参，比如尝试新特征，特征采样频率要设为1啊这种细节
7、知道几种激活函数？
我说最简单的SIGMOID TANH RELU我就不提了，讲了讲某个比赛时候用到了leakRELU，然后谷歌的论文里面的swish函数，随口介绍了一下这个论文。
8、鞍点是什么？
我嘴贱说这个干吗，然后我说忘了，但绝对不是局部最优点，看表情面试官可以满意，其实真忘了。
鞍点（Saddle point）在微分方程中，沿着某一方向是稳定的，另一条方向是不稳定的奇点，叫做鞍点。在泛函中，既不是极大值点也不是极小值点的
临界点，叫做鞍点。在矩阵中，一个数在所在行中是最大值，在所在列中是最小值，则被称为鞍点。在物理上要广泛一些，指在一个方向是极大值，另一个方向是极小值的点。
广义而说，一个光滑函数（曲线，曲面，或超曲面）的鞍点邻域的曲线，曲面，或超曲面，都位于这点的切线的不同边。)
先问用没用过RNN
答：项目的RNN效果，分析RNN在项目里不好，和比赛中RNN前期效果（前期效果最好）
用过GRU吗，为什么LSTM能够记忆长时记忆。
答：GRU用过一次，在哪里用的。用的记忆门，保证长时记忆传输。
9、Attention有哪些？
答：之前说到了自己用过attention，只用过，不知道原理。
(作为一个调参侠，各种网络随便试，但是attention的本质我还是不甚理解，attention is all you need？)
10、Dropout为什么预防过拟合？
从bagging的角度答的，NN是偏差小方差大的学习器，适合用bagging，构造子网络在预测的时候组合，相当于构造了学习的多样性，实现了bagging。
11、协同过滤：
说了解 但是没写过代码
(协同过滤，感觉一个学生要是搞科研为主还是很难接触到，感兴趣的可以了解下，特别是面电商的商品推荐工程师呀还是容易问到的)
12、CTR估计，都用什么？
我说LR和FM ，代码写过，FM主要是NFM，其他的FM都知道理论但是没写过代码
13、蘑菇街是干嘛的你造不？
答：卖衣服滴。于是他介绍蘑菇街主要是电商和直播。（听到直播我差点笑了，快憋不住了，就莫名很开心，然后他看我绷不住了赶紧说直播是目前蘑菇街发展最快的模块）
二面：
顺利，没有撸代码，因为时间不够面了半小时，二面说一面的评语是代码能力特别好，所以不写代码了
我的项目里有一个完整的软件实现，我负责的主要部分超过了1万行代码，可能是这一点让面试官觉得我不用谢代码了吧。
其实大部分正常手撸代码都可以（除了字符串是我的弱点），真出到不会的题是真的没办法
介绍了项目讲了项目细节
项目里编码领域内特征组合都是异或，所以用RELU BN提特征，BN真的是巨大提升
讲BN原理，公式，实现
(可以去看看BN源代码，不长)
为什么用BN压缩异或后映射的正数部分而不是什么什么（没听清）？
我提到了BN层也算做了数据扩充，而且BN层把只有0,1的编码流做了抖动转化，让梯度能变起来，优化的更好（机器学习可行无非就两点，第二点就是优化问题）
为什么用CNN？然后面试官介绍推荐领域内的另一种东西（Embedding），这个Embedding映射了隐向量，你觉得是CNN交叉好呢 还是隐向量好呢
面试官是个大佬！
给定括号流，找到字串中合法匹配的连续对数
s = '(())(()()()'输出是3。下面我的dp好像最开头多加1个0？但是无所谓了
#s = input()
s = '(())(()()()'
#s = '(())(()'
re = []
dp = [0]
for i in s:
if not re:
re.append(i)
dp.append(0)
else:
if i=='(':
re.append(i)
dp.append(0)
else:
if re[-1]=='(':
re.pop()
dp.append(dp.pop()+1)
else:
re.append(')')
dp.append(0)
print(re)
print(dp)
m = 0
cur = 0
for i in dp:
if i!=0:
cur+=i
m = max(cur,m)
else:
cur = 0
print(m) 输出：
['(']
[0, 0, 2, 0, 1, 1, 1]
3 网易互娱 游戏研发
一面
1、自我介绍
没什么拿得出手的东西呀，我主要是算法工程师，而且实际科研项目要么专业性强（编程算法都不沾），要么是算法的东西
说了自己写的科研软件，代码量1W以上写了一堆报告 其他的简单一提
自我介绍的时候提到了自己喜欢玩游戏（以前玩盗版，现在玩正版，steam50级以上，然后游戏快100了）
2、平时喜欢玩什么游戏啊？
最近一段时间科研，没玩游戏。以前喜欢玩塞尔达、黑魂、怪物猎人等
3、网易的游戏玩过吗？
阴阳师和炉石
4、聊聊炉石？
以前特别喜欢玩炉石，主要是喜欢开包（面试官笑），为炉石花了很多钱，因为我喜欢一个游戏就很愿意支持他。炉石的优点在于它有竞技性，而且也是打牌类的游戏，所以本身有趣味性，而且每局有随机性，这样每一句的体验不一样。另外一点就是攒金币开包，金币多了开包后卡池更新，可以有新的构筑，新的体验。这样每过一段时间都会新体验，留住用户，我本身也是喜欢紧张刺激的开包环节
5、三道题，比较简单，要写测试用例
手撕成功，写代码还是比较快的
第一题二分
python写的编译报错，牛客网查不到错在哪，我就赶紧c++重写了一个
讨论了二分的四个边界条件
return st,en二种对应返回搜索边界，data[mid]<value和<=value，两种对应二分上下界
def lower_bound(data,value): st = 0 en = len(data)-1 mid = st+((en-st)>>1) while(st<=en): if data[mid]<value: st = mid +1 else: en = mid -1 mid = st+((en-st)>>1) return st def lower_bound_en(data,value): st = 0 en = len(data)-1 mid = st+((en-st)>>1) while(st<=en): if data[mid]<value: st = mid +1 else: en = mid -1 mid = st+((en-st)>>1) return en def upper_bound(data,value): st = 0 en = len(data)-1 mid = st+((en-st)>>1) while(st<=en): if data[mid]<=value: st = mid +1 else: en = mid -1 mid = st+((en-st)>>1) return st def upper_bound_en(data,value): st = 0 en = len(data)-1 mid = st+((en-st)>>1) while(st<=en): if data[mid]<=value: st = mid +1 else: en = mid -1 mid = st+((en-st)>>1) return en
第二题是二叉树的深度
python手撕，又报错，然后无IDE查bug还好查到了，print大发好，对python，如果print(“XXX”)没输出东西就说明没运行这一行。
定义树class的时候写的是.next，晕了，应该是.left和.right
第三题是数组旋转
左旋转，自信一波分析写完是右旋转，一脸懵逼，怎么看都是左旋转跑完就是右旋转
然后再那试了试改i,j，然后第二次就输出对了，晕，运气比较好
由于循环用的常数限制，要求改成了数组的范围，注意python len(data)是行 len(data[0])是列
正常构造一个和data一样大new数组是先列后行 [[0 for _ in range(len(data[0])] for _ in range(len(data)]
然后循环是先行后列（这样局部性更好，运行速度快，更容易缓存命中，当然面试官也没问我也没提）
写法应该是对的，但我不敢改成行列不相等的情况，万一错了呢.PS:想了想应该不对，因为new数组我照着data开辟的，应该行列反过来开辟才对，先行后列构造的话正好对应旋转后的情况，幸好没深究，不过这种bug很容易改，print()大法print一下就出来了
问问题：好希望他问我机器学习的东东，这样我就能装逼了，然而
6、静态内存和动态内存?
讲了static和堆栈是静态,编译的时候决定了大小，动态内存可以自由开辟->堆，也不知道对不对。。
（回来问了问另一个收割大佬，应该是这样）
7、堆是？
说了向上开辟，速度慢、运行时改，然后开辟的过程，链表存着下一个位置和这一块有没有使用，如果没找到就析构合并内存再找，再找不到返回null（可以参考前面的答案）
8、堆栈是？
说了向下开辟、速度快、编译时分配、主要是存PC指针，然后函数入口参数多组成栈帧存进去等着恢复
9、malloc和new区别 free和delete？
1、一个是函数（面试官没问，但我自觉呀，诚实回答忘了是哪个头文件里的了，事后查了查是stdlib我擦我天天写没想到是这个）一个是关键字
2、malloc要算大小，返回void*(然后随口提到void*可以转XX *),强转后按转完后的类型用，要自己算大小；new的时候传类型，就比如100个int，然后直接开100个就好了，他自动将int长度算进去
3、malloc再堆上，new在自由存储区（然后回答忘了自由存储区再哪了） 讲着讲着忘了free和delete的事了
(自由存储区和堆似乎是概念上的区别？我丢，深入理解计算机基础是按C讲的，我哪知道C++的自由存储区和C的堆有啥区别呀，按理来说假如new是依赖malloc实现的，那么他们不该开辟于同一块区域么。C++默认在堆上开辟new需要的空间，所以new来自自由存储区和堆都行。
网搜的答案：
自由存储区是C++中通过new与delete动态分配和释放对象的抽象概念，而堆（heap）是C语言和操作系统的术语，是操作系统维护的一块动态分配内存。
new所申请的内存区域在C++中称为自由存储区。藉由堆实现的自由存储，可以说new所申请的内存区域在堆上。
堆与自由存储区还是有区别的，它们并非等价。
)
10、智能指针了解不？
我从python的内存管理角度讲了计数法析构内存，和智能指针原理一致。但我自觉诚实的说出我没用过智能指针
11、python怎么解决循环引用的？
是不是想问我智能指针的循环引用解法？我忘了呀，我就直说python本身解不了循环引用的问题（这实话实说，确实解不了，python又不是神，循环引用要靠自己析构，对python来说，循环引用的东西就算程序关了都还在），但python有个库函数可以发现循环引用位置，然后调用垃圾收集器析构掉就好（其实就是定位内存泄露，然后gc把它干掉）
12、计网了解不？计算机网络TCP和UDP的区别？
答自学。回答了很多，挺详细了
(UDP主要用于那些对高速传输和实时性有较高要求的通信或广播通信，
TCP用于在传输层有必要实现可靠性传输的情况
1、TCP面向连接（如打电话要先拨号建立连接）;UDP是无连接的，即发送数据之前不需要建立连接
2、TCP提供可靠的服务。也就是说，通过TCP连接传送的数据，无差错，不丢失，不重复，且按序到达;UDP尽最大努力交付，即不保证可靠交付
3、TCP面向字节流，实际上是TCP把数据看成一连串无结构的字节流;UDP是面向报文的；UDP没有拥塞控制，因此网络出现拥塞不会使源主机的发送速率降低（对实时应用很有用，如IP电话，实时视频会议等）
4、每一条TCP连接只能是点到点的;UDP支持一对一，一对多，多对一和多对多的交互通信
5、TCP首部开销20字节;UDP的首部开销小，只有8个字节
这里建议不是特别熟的回答首部设置不一样，别说的太详细。
6、TCP的逻辑通信信道是全双工的可靠信道，UDP则是不可靠信道
)
13、长传输和短传输？
不知道
(是http的长连接和短连接吗？HTTP1.1规定了默认保持长连接（HTTP），数据传输完成了保持TCP连接不断开（不发RST包、不四次握手），等待在同域名下继续用这个通道传输数据；相反的就是短连接。)
14、操作系统呢？
回答自己看的深入理解计算机系统，看的很详细，收获了特别多
15、进程和线程？
程序不过一段文本，运行起来才是进程，一顿讲，资源/调度单位啊、共享内存啊、并发啊XXXXXX
（见之前的答案）
16、你还有什么问我？
问了两个问题
一问：您能不能了解到其他面试人的信息，然后对着我教研室座位后面的字节大佬猛夸（因为他特别想去互娛做游戏），一开始面试官还以为这个人挂了呢我想捞一手，一听和我同时面了互娱就轻松了说既然这么强一定能过面试，然后我就突然想到好像可以暗示一波，就说我和他报的都是广州，我很想和他当同事（强烈暗示）
二问：我说我是算法工程师，机器学习特别厉害，平时工作内容是啥啊，机器学习这部分我都用上么
教研室巅峰大佬去了收口头offer，我去了收“简历你拿回去吧”。。太难了。
重构了简历，突出了软件经历，游戏经历，并附带了玩过的游戏，游戏保有量和steam58级，以前写过的一个2048游戏，并带上了2048开发报告，带上了不涉密的写过的软件demo、2048游戏、switch、surface。
嗯，基本都没用上。
一道题，30分钟。完成strlcpy。写出来了，但是面试官没问。
size_t strlcpy(char *dest,const char* src,size_t size)
{
assert(dest!=nullptr && src!=nullptr and size>=0);
char *tmp_dest = dest;
//重叠从后向前找
if(dest>=src && dest<=src+size)
{
*(dest+size)='\0';
--size;
while(size>=0)
{
*(dest+size)=*(src+size);
--size;
}
}else
{
size_t len = size;
while(len>0 && *src!='\0')
{
*dest++ = *src++;
--len;
}
*dest = '\0';
}
char *tail = tmp_dest;
//更新新序列里长度，这一步可以放在上面的if else里优化，就不需要再从头找了
while(*tail!='\0')++tail;
return tail-tmp_dest;
} 自我介绍，略过了机器学习的部分，介绍完聊了一些算法现状和拿到的一些算法offer，为什么选择网易互娱等的心路历程。也没有忘记这次来的目的，继续吹一波身边的好友，说他很强，他字节offer40W，他一定来互娱。然后面试官要了信息，结果一查发现是别人面得，尽力了，不过他开发游戏比我强多了，应该可以拿到offer，我就不行了。主要是运气不好，一二面都是不同的面试官，不然我绝对把他抬进去。
1、玩了多久的游戏了？
十五年了。正版保有量100，盗版的大几百(面试官表示理解)，任天堂花的钱比较多，一个游戏好几百，玩过的网易游戏最喜欢的是炉石传说，花了几K。
2、炉石传说最喜欢哪个部分？
开包。买了每一个版本的大包和冒险
3、喜欢的卡组，最会的卡组？
喜欢玩奇奇怪怪的卡组，最喜欢的是奴隶战，那时候天天打。其次就是瓦莉娜，术士玩的比较多，算是最强的了，喜欢恶魔术，动物园手牌术都玩。
4、现在不行了，术士都不敢变身了，新卡不是给对当前场面最有利的卡么,那张卡叫啥来着？
牺牲契约。
介绍一下项目，问了问机器学习的比赛？我说您想听吗，这个和游戏研发关系不大。然后讲了一会比赛。
5、一个队列，想知道最大值，怎么做？
保存最大值和索引，出队就从新找，这一步是O(n)，然后入队更新值和索引。
6、如何优化？
想不到。
(这里给出滑动窗口最大值的最优解法，我通常都是用5的方法做滑动窗口最大值，实际上可以用双端队列，翻了翻我自己的剑指offer全题解，我竟然是用5的方法写过，果然不愧是我啊，一错到底。。。没有用到最优的解法，这种一直都可以A的写法，竟然不是最优。
deque解法：
队列为空插入新数据。队列存的是索引，索引比大小的意思是索引对应的值比大小。
非空，判断队首index和当前窗口的关系，若是滑过了，弹出。
循环判断新数据和队尾数据大小，队尾元素小于新数据，就把队尾移除直到第一个比新数据大的，新数据插入。
每次更新窗口的时候，队首元素一定最大。
暴力，复杂度O(N)。KNN学习器用的是kd树，但是我忘了怎么写的了。然后说用kd树，但是忘记了实现过程，连实现过程都想不起来了是最骚的。
(kd树是平衡二叉树，用的思想是二分查找，对所有数排序，如果在中间左边，就在左边找，否则在右边找，主要用kd把平面划分成很多矩形区域。然后搜索的时候，如果最近距离小于边界线距离，那么分界线另一半完全不需要搜索了，因为复杂度最优每次降一半，是O(log(n))复杂度。但是容易退化到O(n)。
构建方法：
根结点->代表k维度空间内所有实例点的矩形区域
对k维递归切分，生成子节点。平面区域选择一个坐标轴和此坐标轴上的切分点，确定超平面，切分点垂直于选定坐标轴，划分区域为左右子区域。实例被分到两个区域，知道没有实例终止，实例保存在结点上。
这一篇讲的很好：
https://www.cnblogs.com/earendil/p/8135074.html
)
8、二维平面一些点，每个点有一个数字，找每个字对应的凸包。
不会，讲了讲聚类的一些算法，主要是小波聚类找到边界点，在想办法最外边连起来。
难点还在于不同数字可能相互混叠。要求是密度最大的算做一个数字，比如很多1，部分2。他们围成的凸包应该是1对应的凸包。
真不会，也没搜到。
9、忘了。
10、反问环节
其实没啥问题，该问的我之前托人打听过了。就聊了一些有的没有，最后问面试官现在还玩游戏吗？得知玩了30年任天堂，当场我就拜起来了，tql。聊了一下switch，面试官也带着。然后讲了讲以前怎么玩的任天堂游戏，我是模拟器玩家。。。聊了一下工作地点选择，选广州工作是因为互娱在广州，原本倾向于上海因为上海落户容易。面试官说你要选上海吗？我们这里有广州上海和杭州，然后介绍了一下，我说想去广州，因为总部在广州。互娱非常想要哪些喜欢玩游戏的，兴趣最重要。然后聊了组内的竞争和双选，选择和努力哪个重要，独立游戏。python互娱用的很多，但是面试不会问，面试官说一面没问吗，应该问问虚拟机的，我说我不会虚拟机，只会python基础的东西，面试官说没事，可以学。聊了聊rpg。但是问面试官的内容很少。。。
整体面试确实非常之愉快，毕竟大家都是游戏爱好者。。。
最后面试官说能和游戏爱好者聊天是非常满足的事情，大家都相见甚欢，然后让我把简历带回去。。。凉凉。。。
360 搜索（Ranking）-机器学习工程师
负责360搜索的部门，面试体验很好。
一面：上午10点40 1小时
忘了面试的一部分，因为连续4面，其中技术面360两个，网易互联网1个，hr面1面，非常之累。
1、介绍自己
2、介绍自己实现的科研软件
用什么语言：C++
什么写的界面：QT
3、LGB和XGB区别
一开始听错了以为是LSTM，我还在想LSTM和XGB的区别，这怎么说，先介绍介绍XGB吧，然后说完XGB反应过来，面试官不是让我说LGB吧。。那就好说了，一顿讲。
(答案前面有)
4、介绍CNN、卷积层如何实现非线性
使用激活层，不然在卷积都是线性变换。我从猫的视觉锥细胞开始一顿讲，应该讲的挺详细了，CNN的时不变性真的很适合用于信号处理。讲了时不变和局部权值共享，说CNN是DNN的特例。
(
卷积：对图像（不同的数据窗口数据）和滤波矩阵（一组固定的权重）做内积操作。
卷积的重要的物理意义是：一个函数（如：单位响应）在另一个函数（如：输入信号）上的加权叠加。
卷积神经网络CNN是多层感知机(MLP)的变种。20世纪60年代，Hubel等在研究猫脑皮层时发现其独特的网络结构可以有效地降低反馈神经网络的复杂性，继而提出了CNN。
CNN：局部连接和共享权值的方式，减少了的权值的数量使得网络易于优化，另一方面降低了过拟合的风险。该优点在网络的输入是***图像时表现的更为明显，使图像可以直接作为网络的输入，避免了传统识别算法中复杂的特征提取和数据重建过程。在二维图像处理上有众多优势。
CNN具有一些传统技术所没有的优点：良好的容错能力、并行处理能力和自学习能力，可处理环境信息复杂，背景知识不清楚，推理规则不明确情况下的问题，允许样品有较大的缺损、畸变，运行速度快，自适应性能好，具有较高的分辨率。它是通过结构重组和减少权值将特征抽取功能融合进多层感知器，省略识别前复杂的图像特征抽取过程。
CNN的泛化能力要显著优于其它方法，卷积神经网络已被应用于模式分类，物体检测和物体识别等方面。利用卷积神经网络建立模式分类器，将卷积神经网络作为通用的模式分类器，直接用于灰度图像。
)
5、卷积层 pooling层怎么放？激活层放哪里比较好，有什么区别？
没听明白，不该是中间夹一个激活层吗。面试官的pooling口音真的是一言难尽呀？我一直以为说的是最后的全连接FC层，我心想这不是被全局池化代替了么？不会所以一顿乱说？因为我自己也是改网络的时候，经常会尝试层的位置交换，我都是哪个效果好用哪个。讲的时候想起了何恺明大神的论文里的预激活，然后对着预激活、卷积层在Resnet的作用一顿夸。有会的大佬么。请私聊教教我。。。
两道题
进制转换
输入为一行，M(32位整数)、N(2 ≤ N ≤ 16)，以空格隔开。
为每个测试实例输出转换后的数，每个输出占一行。如果N大于9，则对应的数字规则参考16进制（比如，10用A表示，等等）
//map<int,char>table;
//table[0]='0';
//table[10]='A';
#include<stdio.h>
#include<iostream>
#include<string>
#include<vector>
using namespace std;
void reverse(vector<int>&a)
{
int l = a.size();
for(int i=0;i<l/2;++i)
{
int tmp = a[i];
a[i] = a[l-i-1];
a[l-i-1] = tmp;
}
}
string get(int M,int K)
{
bool ju = false;
if(M<0)
{
ju = true;
}
//注意负数转正数溢出
M=abs(M);
vector<int>data;
while(M)
{
data.push_back(M%K);
M/=K;
}
reverse(data);
string res = "";
if(ju)
res ='-';
for(int i=0;i<data.size();i++)
{
if(data[i]<=9)
res ='0'+data[i];
else
res ='A'-10+data[i];
}
return res;
}
int main()
{
int M=7,K=2;
cin>>M>>K;
string s = get(M,K);
cout<<s<<endl;
} 2、A->B,B->C,A->C,C->A中有一对链子A->C，C->A问序列里有多少对链子 使用哪种数据结构？
要求：序列很长，只看直接相连，A->B->C->A 不算ABC互联。
讲了比较简单的d[i][j]=(bool)的结构，O(N^2)的时间和空间复杂度
又讲了两次扫描，O(N^2)的时间复杂度，O(1)空间复杂度
最后说了数组＋链表，极端情况下时间复杂度也较高，但我心里想的是对链表排序也不慢吧，二分查找，时间空间都OK呀，但我傻就傻在我心里想了，嘴上没说链表排序。
(看了教研室收割大佬的面经，看到了类似的题目思路，其实对于微博抖音A关注B然后B关注A了吗都是一类题，建一个邻接表和逆邻接表，是表不是矩阵，改进用跳表，大数据用哈希算法进行数据分片，具体的不方便说，毕竟是别人的思路。现在他也在总结面经，等他整理好假如有这部分内容可以在他那看。。。)
体验好，一道题，抽的前两道题都做过，一个是奇偶排序，一个是前序中序重建树
都是剑指OFFer原题，面试官见我思路顺畅，问我是不是做过，做过默写就没意思了。
第一道奇偶排序要求稳定排序，思路1就是归并排序，前偶后奇为大于。思路2双指针，顺序遍历，奇从头放偶从尾放、二分找分界点、偶数部分倒序
第二道 找根节点，二分，没了
第三道没做过，但是也简单，问面试官能不能用python，能的话两分钟结束这道题，说不行就老实写了
这一面主要是深挖项目，深挖！
反问环节，面试官疯狂指导我，真好，这里总结了记住的一部分：
聊了搜索推荐的一些问题，我问的第一个是360对编程能力的要求。面试官的回答是所有的算法工程师都要具备很强的编程能力。
第二个是推荐中排行榜的问题，我说上了排行榜，阅读量就是疯狂增加，一增加就会更留在排行榜上，这种情况怎么办。面试官回答这是正反馈问题，说了很多干货，有兴趣做推荐的可以看看相关内容。
我又问了冷启动的问题，我就说对于新出现的页面，第一次出现，没有任何曝光下，如何给他做推荐呢？这里面试官反问了我，我就回答了自己的思考，先小批次试点曝光，再推广。
面试官开始讲推荐和搜索排序的区别，搜索排序面临的问题更复杂。所谓排序就是获取大数据的网页界面，然后对用户的查询给出一个最可能的结果(LGB可用)，用到一些分层、召回(最优可能查询结果捞出来)、排序(对捞出来的东西排序)，这里排序要做到去相关性，查询要保证输出结果多样性、表达多样性，还牵扯到了词与词之间的紧密度、运营和相似度命中。
另外排序有很多难点，首先数据量更大，抓取信息很多，但是索引不是越多越好，因为存在重复的（抄袭的网页）、质量不高的网页。另外对于learning to rank，我们不需要像回归那样得到准确的回归值，只要得到他的偏序就好。比如A<B，我们算价值是A：80，B：79和A：80 B：77，偏序都一样，只要排序正确即可。而要检验我们排序的好不好，就是根据反馈，检验模型的优劣，比如我们把A在B前面，但是用户不点A点B，用户改Quary词或者翻页，都可以用于检验模型效果。这三时候可能会用概率图解决这些问题。排序技术难度大，底层需要的技术也比较高级。另外，用户的询问和我们的结果可能存在一定的gap，比如用户搜某车的标价，我们给的搜索结果是某车的成交价，这就存在了gap。
最后我问了这么一个问题，就是我在做学习强国的时候，查询一个答案， 结果第一个是付费的，第二是是免费的，有限的时间里查到的第一个结果让我付费观看，我就很生气。这个怎么看待？面试官的回答也是很棒呀，所谓的搜索排序最终就是给用户满意的结果，结果可能是多样的，有的排版好内容丰富，有的排版差内容差，我们做的就是把最好的结果展示给用户。对于搜索排序，可能产业化的结果分两个，第一种是满足需求的免费内容，特别用户预期的结果。第二种可能是竞价排序的结果，可能付费观看，大部分用户没有付费的欲望觉得不好，少部分付费用户可能也会特别喜欢，但无论如何，前者肯定也会在搜索结果前列。
网易互联网：深度学习工程师
啊，面到最后没时间了，面试官让我问问题，我就随便问了两个，然后不得不回360电话了，就说我有点事把视频关了，本来面得挺好的，哭
其他的忘了，就记得两道题
第一道 n的二进制表示中有1的个数
int re = 0;
while(n)
{
++re;
n = n&(n-1);
}
print(re) 然后分析复杂度，最后提示下分析出来了log(1+n)
然后分析平均复杂度，我以为从1 到int_max的所有复杂度求平均。所以怎么都分析不对。
最后才知道是每个的复杂度，晕，面试官告诉我是log前面的系数是0.5。因为0,1等概率出现
第二道：
1、建个链表
2、打印链表
3、反转链表
反转链表写的不好，左右边界各判断了一次，正常情况下只判断一次就好，但面试官说也OK，多做一次时间影响不大，结果正确就好。
4、排序链表
做的是真难受，臭牛客，哼哼。写错个变量都指不出来，改bug改到头秃。
排序链表写的是链表快排，最后发现复杂度不是nlog(n)，因为我L部分的尾部没有指向mid(base)，导致我最后写了个找L部分的尾部，把这一步优化了就没问题了，但是面试官说也行吧排序的结果不会错。
最后问问题的时候，我一边问一边调试，最后终于把链表快排调对了。然后和面试官说我调出来了，就匆匆结束了这次面试，很难过。因为马上360就是二面，我总不能为一面放弃二面把，这里我情商不够处理的不好，哎，难受。面试官人都挺好的，都是我的问题。
放弃了面试。BIGO C++开发（机器学习平台开发/推荐平台开发）
这次的面试，心态过于放松。
问了软件难点，确实很难。自己如何用数学知识最终解决的这个问题，解决这个问题的全部背景和流程。
聊到了自己对实际工作中C++开发这部分和算法这部分的工作内容和关系的认识，其实笔试的时候我大概就知道这部分工作大致是干那的了，但来都来了，面！
二、先来的简单的，构造顺序和析构顺序。
先父后子，先子后父。然后说这也太简单了。。
三、虚函数，构造函数可以虚函数吗？
不可以会构造错误。然后面试官质疑后回答了正确答案，构造函数构造后才有虚函数，所以构造函数不可以虚函数。
(构造函数不是虚函数是规定，构造函数之前，没有实例化，没有内存空间，就没有虚函数表，构造函数就不能是虚函数。另外如果构造函数可以是虚函数，那么子类构造时，不可能用父类的指针去调用构造函数，因为构造函数是对象创建时自动创建的。)
四、析构函数呢？为什么
析构错误，只析构基类。面试官质疑，说错，然后她说很多人答案都是这个，但这个不对。
(显然面试官说错了，通过基类的指针来销毁对象。这时候假设析构函数不是虚函数，就不能正确识别对象类型从而不能正确调用析构函数。用基类指针去析构子类，如果析构函数不是虚函数，那么只析构了基类而没有析构子类，正常析构应该是先析构子类，再析构基类，少析构了一部分）
五、类里，不用虚函数，函数隐藏怎么做的？不同参数列表的同名函数怎么实现？
答了同名隐藏，函数签名修改。
(同名隐藏是子类重定义了父类的函数，会把父类的隐藏，函数签名修改是函数重载等，在编译阶段把同名不同参的同名函数改成不同的名字)
面试官解释了析构函数为什么要是虚函数，因为虚函数只析构子类不析构基类，因为指向的是子类所以只调用了子类的析构函数。。我表示疑问，但不质疑，说自己下去看看(内心怀疑人生，真的假的，感觉学的假C++)。
这两个问题间扯了一些自己对接口重用的理解。
六、malloc过程？
讲了讲链表找空间块，然后怎么标记的找没找到，没找到析构一些合并，再找，找到返回。
面试官说还会析构无用变量，malloc这么智能？我说析构是操作系统内核做的，怎么怎么的。面试官说malloc应该没那么智能。我没做表示，并想回去再看看深入理解计算机系统。。心想应该有析构这一步吧。。不确定
(C标准库提供了malloc程序包的显示分配器，调用malloc函数从堆中分类块，返回一个指针，指向大小至少为申请size字节的内存块，由于对齐可能实际大一点，32位模型返回块地址是8的倍数，64位是16的倍数。如果失败，则返回NULL，并设置errno
至于隐式分配器就是垃圾收集器)
七、上述说的找合适大小怎么找到？
不知道怎么回答，说了从头找，上一次找，最优情况，并说实际比较复杂，但最优的情况(找合适大小)存在于理论很难实现。
(深入理解计算机系统里，说的这三种，也就是我仅会的三种，这三种的名字叫首次适配、下一次适配和最佳适配
首次适配：从头搜索空闲链表，选择第一个合适的空闲块。
优点是大的块放后面，缺点链表起始位置碎片多。
下一次适配：从上一次查询结束搜索空间链表，选择第一个合适的空闲块。
优点是运行速度块，缺点是内存利用率比首次适配低很多。
最佳适配：搜索整个链表选个最合适的，彻底搜索。
实际中用的方法接近最佳适配但不需要彻底堆搜索。)
八、智能指针用过吗？
没用过，为什么了解呢，因为和python内存管理一致才知道的。
这时候面试官补充说析构函数+虚函数为了能析构子类。。我就说嘛。。。
九、map和unordermap底层，怎么用
十、什么时候用什么map，什么时候用unordermap？
内心想什么时候用就什么时候用。说了自己的理解。
(map底层红黑树，因此是有序的(中序遍历)，依靠大小关系建树，增删改都是log(n)，缺点是占用的空间大，需要保存父节点、子节点还有颜色。unordermap底层哈希表，依靠哈希函数建表，查找可以达到O(1)，但是建表比较慢，占用空间更大
实际怎么选看场景。要求速度用哈希，要求有序用红黑树。静态数据用哈希表更好一点，动态的红黑树更有伸缩性。内存要求高，就用红黑树，时间要求高，用哈希表。)
十一、操作系统锁机制？线程安全？
开始胡言乱语。。哈哈不会，聊了聊信号量，临界区，也不知道自己在说啥，哈哈。
(锁机制就是对临界区的保护，临界区同一时刻只能被有限的线程进入临界区代码。信号量常用于多进程或线程对同一资源访问竞争的问题，是一个值，只能PV两种操作，P是信号量大于0减，为0挂起进程；V是其他进程挂起则恢复，没有挂起自增1，加相当于门上挂着一把钥匙，进来一个人开门带着钥匙进屋，出来再把钥匙挂门上。信号量常用于二元信号量，同一时刻只能进来一个。
多个线程同时操作临界资源，不出现二义性叫做线程安全，如果我们对临界操作进行了非原子操作，这是可能不安全。解决线程不安全的方法包括同步和互斥，同步就是线程占用这个临界资源，其他线程看它占着就不用这个临界资源了，是访问的合理性，互斥就是不管你进不进来，我都要尝试进一下，但是同一时刻只能有一个进入，这就是互斥
线程的互斥主要用互斥锁，也就是0/1计数器，进来一个线程互斥量就减1，解锁就是加1，为0则不可以再进入资源。
互斥量和信号量的区别在于互斥量用于线程互斥，信号量用于线程同步。互斥量对资源限制访问，无序；信号量可用于线程也可用于进程，实现资源有序范文。互斥量0/1，信号量可以0/1，也可以是自然数。互斥量对同一线程加锁和解锁，信号量A释放给B)
十二、继承的虚函数表结构
口述的稀烂，但是面试官反馈还可以
(类A有两个虚函数，那么类A虚函数表就有两个虚函数指针，表中放两个虚函数指针，类B继承于A，定义了自己的虚函数，那么B的虚函数表，除了保存B自己新定义的虚函数，另外都是继承于A的虚函数，如果B重写了A中的虚函数，那么B表里相应存的A被重写的函数指针改成B自己新写的就可以了)
十三、给了网站，两道题，简单的链表反转
不会写C++的struct链表形式，但是应该没写错吧，不知道
链表反转简单。。随手写完，说自己不是背的，但写的肯定是对的，然后让讲思路，真没好讲的。。
另一道题 两个等长元素不重复，包含元素都一样的数组，找到顺序一致的子序列最长（问题是说找到删除元素最少的方案，一个意思）长度1e6时间2s。应该是O(n)或者nlog(n)
第一反应动态规划，但是我蹲在地上好难受，腿算了，没思路。干脆就聊怎么暴力做，聊着聊着想到了剪枝方案，剪枝方案说完想到了打表换时间。分析平均复杂度nlog(n)
方案打B表，偏历A表，原因利用偏历A表的偏序关系，贪心找长度。看面试官反馈还可以。
结束了感觉又不太对劲，说不上来，难道做错了。。。好像是不行，贪心找长度不行，这一步要二分优化找就行了。那复杂度估计就是nlog(n)log(n)
如果LCS转LIS不会写，面试就按LCS问题，就是最长公共子序列的最优解默写一下，杀手锏。
十四、你来广州吗？ 来
啊，正准备夸广州好，结果反应过来问面试官是不是可以选地方，北京或者广州。面试官说选地方，你会选哪。我会选广州因为拿了一堆北京的offer（嘴贱啊，2个等于一堆，3个等于海量成了），啊，你都拿了那些offer?我回什么都没拿。。口误。额，好吧，拿的都是算法的offer，C++开发没拿。然后开始夸C++开发好。。。想做C++开发。
等一波感谢信。刚挂了电话就来了，我心想感谢来的太快就像龙卷风，结果是快手，说您好，这里是快招校手平台，和您约的XX日下午YY点，您能来吗？我说不要紧张，约的时间不是ZZ点吗不是YY点。她回哦是的，不好意思说错了，XX日下午ZZ点，您有时间吗，我回有空。。。嗯，谢谢您。太可爱了。
二面
等发视频连接，结果是臭电话面。bigo不是挺有钱的，怎么不花钱在牛客上面？不就几十块。。。
挖软件难点。讲了很久。
为什么要来基础平台开发呢？
表明自己喜欢基础研究，不太喜欢赚钱的的广告推荐啊游戏研发啊这些工作（其实我所有的工作都喜欢。。。闻道有先后，术业有专攻，所有的职业都应得到尊重）
给一个场景，短视频推荐，如何避免重复推荐
说了算法工程师的做法，召回去相关。说了C++开发的做法，算哈希。
去相关计算相似度，相似高就屏蔽，算哈希打表，推荐过不再推荐。
怎么比较相似度？哈希怎么算
每张图用特征表征，根据特征算哈希。
生成词图比较，用词来代表图片。
那你这样容易把同类的去掉啊？用户就喜欢相同的同类别的你给过滤了。还有别的方法吗？你这是视频不是文本。
想到了特征脸。于是说图片低秩、视频更低秩，可以用几张特定的图作为特征表征整个视频。有些用户可能就是把别人的视频裁了裁，这样里面的特征帧图片内容应该很相似，这样就过滤掉了。相似的视频映射到同一个哈希上就行了。
那现在特征有了，如何过滤掉同一段时间看过的视频？
建个map、vector这一段时间看过视频的哈希值，判断在不在vector里可以用二分，如果在出现同样的就过滤掉。或者堆结构也可以。
你二分要有序啊，哪来的大小比较？
用哈希值去作比较。
那你用这些东西怎么删除一个哈希值呢？
vector可以把要删除的和最后一个交换pop掉。又讲了讲其他的删除方法。
面试官生气了，说这是个面试，你不要以为很简单，我不想知道你掌握的东西，我只在乎你爱不爱学新的东西，注意细节，要是有的重度用户看视频很多啊？你不要这么随意啊。
原来面试官是个宝宝，赶紧安慰他一波(心想面试官是不是被前面的面试者怼了)，我是不会怼面试官的，大家好聚好散嘛，基本的尊重还是要的。嘿嘿。
表明自己很荣幸有这个机会和面试官交流，自己从来没有不尊重对面。
(这里理念就不同了，我要是面试官，我只在乎面试者掌握的东西，爱不爱学是其次，很多人都爱学，但是怎么就没学呢，还不是不自律，道不同不相为谋啊，而且这个爱不爱学这段话说的莫名其妙，全程没提到啊，固定是记忆错乱把我当成上几个面试者了，因为我这是上午最后一场，心里已经把bigo拒了，估计是互拒)
假设我是一个不会优化算法的人，给我讲讲模拟退火？
优化的目的是为了满足机器学习可行的第二个条件，就比如我要是登山，优化算法的目的就是找到最高峰的位置，优化算法就是如何往上走的方法。传统的梯度下降就是盯着脚下的路走，每一步都沿着向山顶的方向，当走到一个山顶时，四面都是下披路，就站在山顶不动了。而模拟退火就是一个喝醉的人去登山，他每一步都知道往哪走上是向上的方向，但是他喝醉了，可能会往上走也可能乱走。随着时间的流失，他喝醉的程度减轻了，就是醒酒了，乱走的可能性降低，最后完全醒酒了，就直接朝着向上的方向走了。
再讲讲为什么能够跳出局部最优解，为什么能走到最优解呢？
(先说不一定走到最优解，面试官也知道自己口误了，补充说的确是局部最优解)
之所以梯度下降法不能跳出局部最优解，是因为梯度下降法只盯着向上的方向走，假如登山者站在了凳子上，那么他往哪个方向跳下凳子后，落脚点都是一个朝着凳子位置下落的方向，而梯度下降法只会朝着高处走，所以不会有跳下凳子这一步，所以他就封印在了凳子上。就算凳子摆在了山谷，他只要跳下去就能朝着更远处的山顶走，他也不会跳下去。模拟退火来自于物理学的概念，表明自己学过热力学，然后讲了讲熵和分子运动，就算是走到凳子上，模拟退火在这里有一定概率跳下去凳子，因为他有概率朝着向下的方向走，只要他跳出了这个局部最优解，他就能朝着远处的山峰走去。另一方向，模拟退火不一定能走到最优解的原因是，假如局部最优解覆盖的范围较广，由于模拟退火走不了太远，可能跳着跳着就跳回来了，就好比珠穆朗玛峰远处的乔戈里峰，他们差的太远了，很难从局部最优解跳出走到全局最优解。然后比赛中准备用这个方法所以知道代码实现，表示这个代码特别好写。
到了最喜欢的反问环节？这里我想的既然面试官是个宝宝，我就拉下脸哄哄他道个歉大家好聚好散吧。可信面试官惜字如金啊，互给个台阶这么难么。。。
问：BIGO这里有两个平台开发，是独立的还是相关比较高？
独立的，基础学习平台开发是更广的，算法工程师要用的比较多，推荐平台主要面向工程软件。
C++开发工程师作为基础架构的实现者，平时怎么和应用架构的同事交流工作呢？
看个人。
许多机器学习的任务都要求并行，这样对基础平台的并发要求高吧，如果是校招学生，应该怎样掌握相关技能呢？
会什么不重要，关键爱看学啥。
时间差不多了，咱们就这样吧，你不想答我也不问了。然后和面试官互相谢谢就结束了。
快手 C++开发（机器学习平台开发）
机器学习平台开发，C++平台
一面
介绍项目
一道题：二叉搜索树转新的单链表
题目给了一些定义，给了一个函数，返回值是链表，入口是树，这样好难递归啊，不知道怎么返回头节点，所以写的怪怪的的，但感觉是对的，结果不对。
方法就是找左边，左边不空，创建左边的next接现在，现在等于左边。
找右边，右边不空，链表的结尾接右边的新listnode
然后过了0，尴尬。哈哈
我就说中序遍历一遍就行，因为二叉搜索树中序遍历有序，他说对，然后说再给我一个机会让我写，在外面写listnode，是定义一个新的类成员么。。不清楚，不想写了还是python好。大概解法是外面定义一个listnode，然后再写一个新的可以递归的中序遍历(返回值是树的节点不是链表的)，然后一个个接上吧，讲了讲思路等死了。
一面面试官说虽然你没写出来但是我知道你能写出来。。等下接着二面。。我。。。
二面
你都会什么排序，讲讲
快排讲讲。。快排有啥好讲的。。讲了快排
堆排讲讲。。给你一个数组转堆。。
原地调整吗？ BB了半天。最后又说了从头建堆的方法，然后一步步push_back，怎么找父节点(index-1)/2，怎么找子节点index*2+1，index*2+2
(很多人以为数组原地建堆是nlog(n)的复杂度？这是误区啊，把数据调成堆结构是O(n)复杂度，这里提一下。最差nlog(n)
#建堆，可以直接优先队列，不太熟悉python的优先队列库 def heap_step(data,index): #index的左右结点不空 l = index*2+1 r = index*2+2 cur = index if l<len(data) and data[cur]>data[l]: cur=l if r<len(data) and data[cur]>data[r]: cur=r if index!=cur: data[index],data[cur]=data[cur],data[index] heap_step(data,cur) return None def mak_heap(data0): data = data0[:] index_max=len(data)//2 for index in range(index_max,-1,-1): heap_step(data,index) return data def heap_updata_K(data,value): #模仿固定容量的优先队列的插入操作 if value<=data[0]: return else: #data.append(data[0]) data[0] = value #data.pop() k = len(data)-1 heap_step(data,0) # #data = [1,2,3,4,5,6] #mak_heap(data) # #数据 data_all = [[1,2,3,4,5,6,7,8,9,10,11,12],[2,2,3,0,1,6,0,1,6,0,1,6],[0,1,6,0,1,6,0,1,6,8,7,6]] #两个列表找最大和topK #由于是最大的topK，排序记得reverse def get_he(data1,data2): x = sorted(data1,reverse = True) y = sorted(data2,reverse = True) pri_quequ = mak_heap([i+x[0] for i in y]) for y_index in range(0,len(y)): if y[y_index]+x[0]<=pri_quequ[0]: break #剪枝，很重要，复杂度立马降下来了 else: for x_index in range(1,len(x)): heap_updata_K(pri_quequ,value=y[y_index]+x[x_index]) return sorted(pri_quequ) #矩阵找最大行和topK，重复两行的调用就可以了 def get_all_he(data): data1 = data[0][:] for i in range(1,len(data)): data1 = get_he(data1,data[i][:]) return sorted(data1,reverse=True) def get_all_min_he(data): for i in range(len(data)): for j in range(len(data[0])): data[i][j]=-data[i][j] tmp = get_all_he(data) res = [-i for i in tmp] #还原回来，虽然没必要 for i in range(len(data)): for j in range(len(data[0])): data[i][j]=-data[i][j] # return res print(get_all_he(data_all)) print(get_all_min_he(data_all))
[26, 26, 26, 25, 25, 25, 25, 25, 25, 24, 24, 24] [1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2]暴力检查
tmp = [] for i in range(len(data_all[0])): for j in range(len(data_all[1])): for k in range(len(data_all[2])): tmp.append(data_all[0][i]+data_all[1][j]+data_all[2][k]) tmp.sort() print(tmp[:len(data_all[0])]) print(tmp[-len(data_all[0]):][::-1])暴力输出
[1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2] [26, 26, 26, 25, 25, 25, 25, 25, 25, 24, 24, 24]
拓扑排序，会吗？
不会啊，我看到拓扑排序就跳过，所以一直没来得及学，然后笔试遇见就放弃呗，反正就见了两次，我都放弃了。
没学过？太好了，写一个，不用考虑复杂度。输出一个合法的
我就写了一个，遍历两边点，第一层如果res序列没有，i***去，维护下标。
第二层，如果res没有j,插入j,维护下标continue
判断，i的下标小于j，continue。否则，把i插在j前面，更新这一段的下标（一开始写了j插在i后面，肯定错的）i插在j前面这样插应该可行，假设之前都有序，这样新插的i在后面不满足偏序，把i插在前面，所有的数据依然有序，因为没环。证明可以用数学归纳法，就是复杂度高一点。
小红书算法工程师
投的早，笔试A的也不多，当时还比较菜。通知的现场面，就在学校外边的会议中心。
一面：
题一：三数之和最接近
题二：leecode659
分割有序数组为连续子序列。可以分割返回true。连续子序列长度要>2。比如1 2 3 3 4 4 5 5 true。范围1-10000。
没有思路，说了递归和dfs可写但时间复杂度过高，分析是阶乘复杂度(没好意思说是指数)，面试官让优化到多项式复杂度，面试官提示说的递归和dfs能不能写开，然后是不是要排第一个数，在提示了下了排序+map的答案。
面试官提示数据在1-10000。改换C++写了O(n)的最优情形，贪心。
(这题没提示真没思路)
class Solution: def get_start_help(self,start): if start>=10001: return -1 if self.dic_nums[start]>0: return start while(start<10001 and self.dic_nums[start]<=0): start+=1 if start<10001: return start return -1 def isPossible(self, nums: List[int]) -> bool: import collections #dic_nums = collections(int) self.dic_nums = [0]*10001 dic_tail = [0]*10001 for i in nums: self.dic_nums[i]+=1 cur = 0 cur = self.get_start_help(cur) while(cur!=-1): if dic_tail[cur-1]>0: dic_tail[cur-1]-=1 dic_tail[cur]+=1 self.dic_nums[cur]-=1 cur = self.get_start_help(cur) else: if self.dic_nums[cur+1]>0 and self.dic_nums[cur+2]>0: self.dic_nums[cur]-=1 self.dic_nums[cur+1]-=1 self.dic_nums[cur+2]-=1 dic_tail[cur+2]+=1 cur = self.get_start_help(cur) else: #print(dic_tail[:10]) #print(cur) #print(self.dic_nums[:10]) return False return True
二面：
自我介绍
RF DT LGBM在特征选择的区别
介绍了很多，从ID3讲到C4.5讲到CART讲到XGB讲到LGB，boost的从头讲到尾，RF详细说了，还讲了讲lgb的特征采样参数的坑，如何按叶分类。面试官补充问为什么学习率和树深度的关系？我感觉是树越深越小，但不确定，于是肯定的说(不能露怯)越深学习率可以越小。问LGB学习率可以比较小，LGB树深但是每层很瘦，巴拉巴拉讲了不少，顺便讲了一些自己觉得是玄学的网上给出的解释，因为讲的特别细还讲的很快，面试官极为满意。不过我不是百分百确定自己对于学习率那一段说的对不对。
一道题，很久后才理解题意(以为理解了实际上没理解)。一个二维数据，返回一个区间，在这个区间内，一定能找到任意行的某一列的数都在区间内。
思路，中间所有行，统计一对最小和最大，所有最小取max得到min0，最大取min得到max0，在边界范围[start,end]一定有start<=max,end>=min
然后暴搜两头。O(n^2)
复盘：把所有行都按这种方法做不就知道start和end的范围了，没必要中间这样做两边暴搜。因为一直以为第一行和最后一行要对上，不知道自己在想什么想锤自己。哎。
三面：
介绍项目和比赛
一道题：有一串珠子和m个颜色，找到包含m个颜色最短的一串。
滑窗。左右窗。如果没包含，右边界右滑，否则，左边界右滑。更新长度。
面试官给了标准答案，问我做过没，和我写的有什么区别。
我说没做过，leecode只刷了不到50道中等以上的题。区别：我是+颜色，他是-颜色。然后我是在循环里判断该左滑还是右滑标准答案是先一直右滑到能包括所有颜色，再左滑到不包括。算长度。
复杂度呢？O(N)。一定是O(N),因为每一步都相当于某个边界自增1，两个边界从0增长到N总共也就2N。
视频二分类，不平衡，算精准率，召回率，准确率。
改了改分类结果，再算一边。
问我怎么看。
我说召回率太重要了，因为这种我们可以虚警但是不能漏警(猜猜检测的啥)，所以精确率不高可以接受。
如何提高精准率呢？
调分类阈值+大，但是召回率降低就回退。
正样本权重变高训练，用focalloss
FocalLoss？
如果不改动现有模型呢？
我说一般我会用二分类trick，但是这种不知道在二分类行不行，应该不行吧，不如人工查。
面试官反馈说人工肯定要查的，(我已经意识到自己的上一句话不妥了，但是现在是对方的回合)，面试官说了人工查的重要性和必要性，然后说这一步提高精准率就是为了减少人力，然人从大量分类错的样本解放出来，可以用二分类，对分错的样本和负样本再二分类。我表示同意，说这个Trick不错。面试说，对啊，不就是个Trick么。
面试官介绍了公司的内容和各个部门的方向，问我个人意向。
HR面开始瞎聊。问小红书为啥下架，当时我拉着所有人报，结果第二天下架了，报小红书的时候有多开心，听到下架整个人就多傻。教研室就投的小红书很少。说到美团啊大家都下架过要挺住啊。
ponyAi
一面：
问项目，机器学习知识点。
一道题：
一个数组找两两异或的最大值。
这道题出了三年了。。。今年又出了可惜我没看别人的面经。
#include<iostream>
#include<cstring>
using namespace std;
typedef long long LL;
struct Node
{
char val = 0;
LL node_count = 0;
Node *next[2]={nullptr,nullptr};
};
class WordTree
{
public:
Node *root=nullptr;
unsigned n_max = 1<<31;
void append(unsigned &cur)
{
this->root = _append(this->root,cur,n_max);
}
bool quary2(unsigned &cur,unsigned &m,int len){
return _quary2(this->root,cur,m,len,n_max);
}
private:
Node* _append(Node *root,unsigned &cur,unsigned n)
{
if(root ==nullptr)root = new Node();
root->node_count++;
if(n==0)
{
root->val = 1;//因为不需要符号表，符号表=值，这里做题赋值仅为了与空进行区分。
return root;
}
int next = cur&n;//每次取一位。
if(next!=0)next=1;
//cout<<cur<<" "<<n<<" "<<next<<endl;
root->next[next] = _append(root->next[next],cur,n>>1);
return root;
}
int _size(Node *node)
{
if(node==nullptr)return 0;
return node->node_count;
}
//判断当前的数据的前len位与字典里面能不能异或出来m这个结果
bool _quary2(Node *root,unsigned &cur,unsigned &m,unsigned len,unsigned n)
{
if(root==nullptr)return false;
if(len==0)return true;
unsigned cur_c = cur & n, cur_m = m & n;
//if(cur_m==0)return true;
//else cur_m==1;
if(cur_c!=0)cur_c=1;
if(cur_m!=0)cur_m=1;
unsigned next;
if(cur_c == cur_m)next =0;
else next = 1;
//unsigned next = cur_c ^ cur_m;
return _quary2(root->next[next],cur,m,len-1,n>>1);
}
};
int main()
{
unsigned n,m;
cin>>n>>m;
unsigned *data = new unsigned[n];
WordTree a = WordTree();
LL res = 0;
for(unsigned i=0;i<n;i++)
{
cin>>data[i];
//cout<<endl;
a.append(data[i]);
}
//找到数组中两个元素最大的异或值
//一位一位搜即可
m = 1<<31;//左移31次在右数第32位。
unsigned res2=0;
for(int len=1;len<=32;len++)
{
res2 += m ;
bool ju = false;
for(unsigned i=0;i<n;i++)
{
if(a.quary2(data[i],res2,len))
{
ju = true;
break;
}
}
if(ju==false)res2 -= m;
m = m/2;
//m = (m>>1);
}
cout<<res2<<endl;
delete []data;
//类也要析构。。。这里省略
}
一道题：
正数数组找到长度为k的三段，使三段和最大。
data = list(map(int,input().split())) k = int(input()) def get_max_sum_3(data,K): if not data or K<=0 or len(data)<K*3: return None #找前缀 dp_first = [0]*len(data) cur = sum(data[:K]) max_first = cur dp_first[K-1]=max_first for index in range(K,len(data)): cur+=data[index]-data[index-K] max_first = max(cur,max_first) dp_first[index]=max_first #同理找后缀 dp_second = [0]*len(data) cur = sum(data[-K:]) max_last = cur dp_second[len(data)-K]=max_last for index in range(len(data)-K-1,-1,-1): cur+=data[index]-data[index+K] max_last = max(cur,max_last) dp_second[index]=max_first #由于不重叠，需要从[K,len(data)-K) res = -0x3f3f3f3f cur = sum(data[K-1:K+K-1]) #容易错的两行 for index in range(K,len(data)-K-K+1): cur+=data[index+K-1]-data[index-1] res = max(res,dp_first[index-1]+cur+dp_second[index+K]) return res print(get_max_sum_3(data,k))
二面：
问项目，问机器学习知识点。由于有误会面试官一直想直接淘汰我，最后才知道简历他看错行了，以后我在造假，他把A项目的内容看成B项目上了。然后一直问A内容的知识点和适用范围，试图找漏洞，因为A项目的内容不能用于解决B问题，也是比较尴尬，但是问的知识都回答出来了。知道出了乌龙后就直接做题了。
一道题：给出AB两个数组，然后AB每次出一个数字，比较，A大于等于B，A加分，否则B加分。AB长度一样，都是奇数个，先已经知道了A的排兵布阵，问B是不是有必胜的安排策略。
一开始我直接就想到了递归或者一步一步DFS或者BFS，但是复杂度很高，思路是很简单的，就是贪心的拿分。
然后突然就顿悟了答案，就是知道了A的排兵布阵，那A的出列顺序就无所谓了，直接对A排序，把A最小的(n+1)/2个数和B最大的(n+1)/2个数一一比较即可，全小于则B胜。然后一直在说证明这样可行，用了递推和反证。最后面试官说方法对了就结束了面试。
字节跳动：散招
散招。
一面60分钟
1、自我介绍，讲讲比赛
才讲到baseline被打断
2、分类和回归的差异是什么？
如果非要说本质区别，应该是输出变量是否是连续型变量。但我觉得本质区别是分类的结果没有大小之分但回归有，训练的时候分类使得各类别间隔最大但回归不可以，因此分类的训练结果往往会优于回归很多，这也是为什么坐标映射用分类做比较好的原因。
3、被逮到了 分类使得各类别间隔最大但回归不可以？问原因
我说看论文看到的，具体的忘了(没认真看不知道原因)
4、一定要给个解释，因为很多分类用回归做的，讲讲为什么分类使的间隔最大。
自己的理解。实际中分类往往是回归+切分阈值做分类。以GBDT为例，假设我们设树的数量是100的三分类任务，我们实际上做了300颗树，然后每一百颗树回归出一个输出维度的结果，(我们三分类是ABC，那么一般会先onehot成1 0 0,0 1 0,0 0 1。然后前100颗树拟合的是回归的1 0 0 中的1，这样。然后给出一个新样本，我们300颗树回归出三个结果 x y z，再套用softmax公式得出最终的结果。注意到softmax求导是这样的，如果输出特征维度j对应上和没对应上是两种情况，i=j怎么样，i!=j怎么样。因为输出值虽然是类别但是我们编码成了向量，因此有了第几个这个概念，i和j就有两种形式吗，但最终的结果就是如果当前是1，就会把当前维度的预测朝着1进行，其他维度朝着0进行，也就是不仅对本维度增强，也会对其他维度抑制，因此间隔变大。
(不满意，让接着说)
对于激活函数，以sigmoid为例，我们预测结果从0.5到0.9是容易预测的，0.9到0.99是不容易预测的。(打断，让解释原因再接着说)，sigmoid可以认为包含了中间的线性区和两端的饱和区，对线性区求导接近1但是饱和区就是很小很小的小数，因此两端梯度几乎不更新，0.9-0.99这一段梯度很小，但是0.5-0.9梯度很大，因此sigmoid预测的结果就是容易收敛到两端。over。对于我们的多分类任务，虽然是回归在做，但是我们onehot后就成了0 1 的向量，此时我们很容易得到趋近两端饱和区的结果而不是落在中间，但是回归的话数字是连续的分布在激活函数的各个部位，有的落在饱和区有的落在线性区，落在线性区就很容易抖动收敛的不好，而且回归有大小之分，就可能出现梯度的矛盾(前一段上升后一段又降了)，特别是回归的离群点，不好好处理的话容易对整体收敛进行较大的干扰(因为回归可以很大很大的值做干扰，比如回归范围1-1000W，但是绝大多数数据几种在10-20这样，很难对大数预测的准确)。总之，在优化这一步回归是很难的，但是用softmax做分类则可以。(个人观点)
5、二分类讲讲，和softmax区分开。
简单一提，顺势引入LR。
6、为什么交叉熵不用L2。
首先肯定了L2可用，但是不好用。用L2一样是可以求导的而且能够训练出结果。认为交叉熵有更多的好处，首先sigmoid函数是推导出来的，不能变的，在sigmoid函数的前提下，使用L2损失并不是一个凸优化的过程，而logloss则是凸优化的过程，当优化过程不是凸优化的时候，我们没法保证收敛到的局部最优解是全局最优的，所以用logloss我们能够保证至少虽然求得是局部最优解，但他就是全局最优解，是可用的。
另外则是分布上，本质上学习器就是在拟合分布，使用logloss我们有更好的解释性，那就是我们就是在拟合最理想的分布，假设学习器理论上最好的分布式p(x)，其实就是我们的label，我们自己的分布式q(x)，则两个分布的差异可以用p(x)log(p(x))-p(x)log(q(x))来衡量，当特征做好了，q(x)固定了，我们对x求导，则只剩下右边交叉熵的部分，即logloss，我们就可以说，学习器在拟合最理想的分布。
最后简单一提最大熵模型。
7、xgb介绍
完整大流程开讲，(打断，改讲一棵树的流程)按层分类，建一棵茂盛的树，遍历所有特征，当增益够大的时候，对此特征分裂成左右子树，因为基模型一般是CART回归树所以是二分裂，到达树深的限制后就成了一棵茂盛的矮壮的树。
8、达到树深才不切分吗？
不是，要父结点-左孩子-有孩子-L1正则-L2正则的增益>阈值才分类。
一道题：
K个有序链表合并。
写的是返回了一个vector<ListNode*>，被问到为何不返回新链表emmm。。。回答说自己秀逗了，直接改链表指向返回一个ListNode*头结点就行了，当前代码不进行大改动的话可以把输出的vector<>遍历一遍，连接成链表后输出。
我一开始的想法是两两合并，分析复杂度不会，说的归并的复杂度但一想不对，因为已经有序了所以是不会出现log项的。假设平均长度是m，我想到的计算方法：
第一段链表合并了k-1次，第二段链表合并了k-1次，第三段是k-2次，第四段k-4，以此类推，直到最后一层只合并一次，所以复杂度是(k(k+1)/2-1)m次。
那多段一起合并呢，合并后长度是mk，我想到的是绝大多数合并后的数据都被比了k次，所以复杂度是mk^2。这样一算两两合并很慢，要优化。
灵机一动想到了用堆优化，因为多段合并后第一次比较完我们就已经知道k个数的偏序关系了，这一步弹出新数据，再二分插入新数据复杂度是log(k)。因此总复杂度是mklog(k)。然后开写。
二分用的优先队列，API忘了，用的抽象的代表，其实应该好好记住的，三个参数，类型，怎么存，怎么比。说了return > 顶部才是最小值。
写的有点问题，第一个是返回值应该返回新链表就可以了，我把链表的各个放在vector里了。问我怎么改成链表返回，我说改动最小的写法就是把vector遍历一次连起来就行了。
#include <iostream>
using namespace std;
vector<Node*> merge_k(vector<Node*>data)
{
int k = data.size();
vector<Node*>res;
int cur_index = 0;
//这一行写的不对！优先队列不是这样用的，我当时忘了随便写的。
prior_queue<pair<int,Node*>>pq;
//
for(int i=0;i<k;i++)
{
pq.push({data[i]->val,data[i]});
}
pair<int,Node*>cur;
while(true)
{
cur = pq.top();
pq.pop();
Node *cur_Node = cur.second;
if(cur_Node == nullptr)break;
res.push_back(cur_Node);
if(cur_Node->next==nullptr)
{
pq.push({0x3f3f3f3f,nullptr});
}else
{
pq.push({cur_Node->next->val,cur_Node->next});
}
}
return res;
}
int main() {
cout << "Hello World!" << endl;
} 二面：60分钟
1、手写ID3
问我要多长时间，本来我想说20分钟的，他看我没说了给了半小时。
有一个小点写错了，ID3是多叉树我写成二叉了。笑死了。我写成把数据切分成某特征某维和某特征其他维两种情况了，稍微改一改改成多叉就可以了，具体是遍历这个特征的所有取值，然后根据取值切分数据集成多份，递归向下就可以。。 。
2、给出一个完整的方案 电商推荐 包括样本 label选取、用哪些特征
你都学过什么？
LR回归的损失函数？
损失函数怎么导啊？
口述了求导过程，先对sigmoid偏导*sigmoid对x偏导
GBDT和RF？
GBDT如何分类？
GBDT如何算梯度？
过拟合如何解决？
FM知道吗？梯度怎么算？
注意力知道吗？
两道编程题
1、map<string,val> 按val从小到大打印stirng,val
res_en.push_back(en);写成了res_st.push_back(en); 这就导致了打印输出的时候越界了。因为en是空的。 因为当场写代码不让调试只能肉眼debug所以没看到，面试官看了一圈说感觉写的没什么问题，可能是哪里边界错的就放我过了。 这里只存了起始位置和终点位置，把数据切出来打印就好了。
#include <iostream>
#include <vector>
using namespace std;
const int L = 129;
bool ju(int* q,int *d,int len = 128)
{
for(int i=0;i<len;++i)
{
if(q[i]>0 && q[i]>d[i])return false;
}
return true;
}
int main() {
string s1,s2;
cin>>s1>>s2;
int q[L]={0};
for(auto c:s1)q[c]++;
int cur_q[L]={0};
//int max_len = s2.size()+1;
//int res_st= -1,res_en = -1;
vector<int>res_st;
vector<int>res_en;
//
int st = 0,en = 0;
bool ju_tmp = false;
cout<<"1"<<endl;
while(en<s2.size())
{
ju_tmp = false;
while(ju(q,cur_q)==false && en<s2.size())
{
cur_q[s2[en]]++;
en++;
ju_tmp = true;
}
while(ju(q,cur_q)==true && st<en)
{
cur_q[s2[st]]--;
st++;
}
if(ju_tmp)
{
res_st.push_back(st-1);
//下一行写成res_st了、
res_en.push_back(en);
}
}
cout<<res_st[0]<<" "<<res_en[0]<<endl;
//cout<<res_st[1]<<" "<<res_en[1]<<endl;
return 0;
}
概率题：圆上三点锐角三角形概率
最前沿paper复现并取得收益->其他部门负责复现。
工作是通常意义算法工程师 参数的设置和接口的调用、选用等应用于自己的业务并负责业务的上线。
代码的工作完全可见->利于成长,可以参与其他团队的设计，。
太强了
作业帮公司氛围 51人发布
