【面经】字节跳动/华为 算法实习面试
之前写好了拖了有点久，当时是实习面试，现在已经进入秋招了…希望对大家能有一点小小的借鉴意义。
第一部分、面试流程：
华为（一面）
总体流程：电话面试，先让自我介绍，然后根据简历问项目相关的问题，最后coding。面试风格压力不大，面试官比较和蔼，简历问题问的也比较浅，coding题目不算难。共计30分钟左右。
1、解释CNN原理
2、解释LSTM原理
3、bagging和boosting，stacking区别，分别的原理
4、你的项目经历中语音、嵌入式的居多，为什么会想到要做NLP方向实习
5、coding（见第二部分）
字节跳动（一到三面）
总体流程：共计三轮面试，安排在一天内完成，每轮在30-40分钟时间，是否通过都会在当场结束后10-20min内短信通知，若通过基本上间隔10min就进入下一轮，非常紧凑。之前听说字节跳动手撕代码很难，所以面试前基本在刷题。我算是运气比较好，三轮coding题目都不算太难，面试官也比较耐心和蔼，这里给字节跳动的面试官门点个赞。
一面，视频面：
一面是我觉得最难的一面，并没有问简历上的任何东西，面试官先介绍了今天三轮面试的流程，然后直接开始coding和概率题。
1、coding（见第二部分）
2、概率题：
1）N个相同的球，取其中M个(M<N），如何保证每个球取的概率一致？
我答了有放回取样，已取样的做标记，若再次取到有标记的则放回重新取，直到取得M个。
考官让算一下，这么做的期望复杂度是多大。没算出来。
2）考官提示：如果是头条的用户场景，每天用户总数量是不确定的，但是要抽M人，如何保证概率一致。
一时间真的想不到好的方法，答了一个每一次抽取都等概率抽样，显然不正确。
3）考官再次提示：如果已经有一个函数，使N-1个人中等概率抽取了M-1个人，那么下一个人加入的时候如何保证等概率。
在这个提示下我想到了需要列式使新加入进来的人概率和前一个人上一次中的概率和这一次的概率之和是一致的，以此类推。其实一下子还是没有写出完整表达式，因为时间比较捉急了，我直接用N个人抽N-1个的特殊情况写了递推式，表示取M个的话需要进行变形。考官应该是认为我已经理解了思路，所以结束了这个问题。
总结：保持和考官的交流，有思路及时沟通，一下写不出答案可以先考虑特化情况。
二面，视频面：
二面主要结合简历在问，相对轻松一些：
1）自我介绍
2）介绍一段你觉得最满意的项目经历
3）说一下CNN和LSTM原理
追问：CNN为什么要有POOLING层
追问：LSTM的输入，输出，遗忘门分别是做什么的，整个计算流程怎么样
4）平常用的什么框架
答：TensorFlow Pytorch都有
5）给你一段文字，如何提取文本特征
答：TF-IDF（解释了一下原理）；word2vec；one-hot；（其实GLOVE ELMO这些也可以讲一讲，不过一时间没想起来）
追问：如果有oov怎么解决
答：word2vec前的词表做大一些，减少oov概率；random一个向量或所有oov都当做unk处理（或者统一规定一个oov向量）；考虑用gensim.most_similar（表明只听说过，没实际使用过）
6）coding（见第二部分）
7）意向做哪一块工作（了解到大的方向主要是推荐，NLP，CV），上海or北京
三面，视频面：
1）coding（见第二部分）
2）自我介绍
3）介绍一段你觉得最满意的项目经历
4）NLP竞赛相关，详细介绍整个流程
追问：用过的模型（CNN/LSTM/ATTENTION）
追问：attention尝试了哪几种，效果如何
答：self-attention和multihead-attention，相似度计算部分乘法，tanh都试过
追问：如果现在倒回去看，如何改进
模型融合方式（尝试stacking）；尝试glove等特征提取；尝试用finetune bert（毕竟bert牛逼...）
5）意向城市
二、Coding问题：
华为（一面）：
问题：O(logN）复杂度找到单次部分旋转后的非减数组最小值。
例如：[1,2,3,4,5]->[4,5,1,2,3] 从后面这个数组中找到最小值1。
这算是我第一次面试撕代码，当时比较懵逼，一下子反应出来的是O(N)的方法，即先令最小值为第一个数，然后找到后比前小的就把后面的数选为最小值，结束循环。
想到了用二分法，但是没有想到是把mid和left的相对大小做比较。leetcode上是有原题的，其实题目不难。
字节跳动（一面）：
问题：定义域值域都是正整数的单调递增函数f，给一个值y，找到使|f(x)-y|最小的x。
肯定是二分，但其实有很多细节值得注意。如定义域值域都是正整数，所以可以推出f（x）是不可能小于x的，应该是x^n的形式，所以开始搜索的范围就是ed=y。
二分法的题目要多做一些，找各种条件下的最简模板。
字节跳动（二面）：
问题：
s = '...' n=3
用 * 去换 .
要求： 任意的两个* 不能相邻
求： 有多少种替换的可能
s = '...'
= '*..'
= '.*.'
= '..*'
= '*.*'
用 * 去换 .
要求： 任意的两个* 不能相邻
求： 有多少种替换的可能
s = '...'
= '*..'
= '.*.'
= '..*'
= '*.*'
类斐波那契，简单推导最后一个替换和不替换的情况就可以解了。
字节跳动（三面）：
问题：
# class A {
# public:
# int next();
# bool has_next();
# };
#
# int peek();
#
# 1,2,3,4,5,6,7
#
# 1. next: 1
# 2. next: 2
# 3. peek: 3
# 4. peek: 3
# 5. next: 3
# 6. next: 4
# public:
# int next();
# bool has_next();
# };
#
# int peek();
#
# 1,2,3,4,5,6,7
#
# 1. next: 1
# 2. next: 2
# 3. peek: 3
# 4. peek: 3
# 5. next: 3
# 6. next: 4
实现class内的三个函数，一开始以为要用stack，后来发现用变量存就行了。
#实习##算法工程师##字节跳动##华为##面经#
