字节跳动算法岗实习一二三四面面经
取之于民，还之与民(面试官Q，我A)
一面（1h）（3月6）
Q：自我介绍一下吧
A：吧啦吧啦吧啦.....
Q：写个编程题吧：两个集合A，B，求A，B的交集(假设A长度为n，B长度为m)
A：1.这个最简单的解法遍历B时候，逐个检查是否在A出现过，复杂度是O(n*m)，
2.我们对A预先排序以后能达到O(max(nlogn ， mlogn)),
3.如果A中最大值不大的话，可以开一个数组nums[max(A)]（打表）记录A中出现元素，这样复杂度是O（m），但是空间复杂度取决于A的最大值
4.我们可以用hashmap把A中的元素记录下来，这样复杂度是O（m），空间复杂度大概O(n)
（我感觉，简单的题如果能给出整个优化的过程，会比较好，而且能拖一点点时间....）
Q：那么如果A，B很大，内存装不下呢？
A：我们可以把A，B通过Hash分桶以后，每个桶单独处理，然后在合并起来
Q：如果某个桶元素很多呢？
A：可以做二次哈希
Q：（心里想：既然你会A+B，那么你把这个偏微分方程求解一下吧）
Q：再写个编程题吧：一个字符串，最少切几刀，使得每个子串都是回文的?
A :.........................我们可以拿DFS求，如果当前串是回文的就返回，如果不是，遍历当前串切割点，递归计算左右两个字符串的最小切割数，最后取最小。
Q:你这个太复杂了，怎么优化
A:（这个题对我来说真的难，搞了半天没搞出来，心态有点慌，最后没办法了，面试官手把手教我怎么写....）
Q:你不要紧张啊，没关系，这个确实有点难，我看你用了Dijkstra,那么dijkstra使用的条件是啥？
A（面试官人真的很好，抱拳了）每条路上的权重都是正值
Q：我看你用了word2Vec,俩训练方式哪个快
A：我知道skip-gram更适用于很多低频词汇的场景，但俩速度没比较过
（我后面感觉，不会的时候尽量结合已有知识，给出一个合理的推断出来，尽量不要说不会）
（其实，我知道skip-gram适用于低频词汇，那么为什么不能取代cbow呢?只能是skip-gram比较慢了，后悔当初斩钉截铁的说没比较过了）
Q:GDBT,XGB,LGB之间的区别和联系
A：这个经常会问到。
-----------------------------------------
（代码题没搞出来，我感觉凉了，就退出房间了，HR过了几分钟，给我打电话让我上线.....）
2面（1h）（3月6）
Q：自我介绍一下吧
A：吧啦吧啦吧啦.....
Q：写个编程题吧：n个数，能够组合成多少种排序树？
A：给出了递推方程以后，开始写代码，中间搞错了一个下标，最后改过来了.....
Q:无穷长的数组中，每次只能读取一个数字，最后我们需要等概率的选取m个数，怎么选？
A: 后面查了下是蓄水池抽样。当时没搞出来.....
Q:聊了一会项目和比赛，项目用了one-class svm,然后问和svm的区别，以及svm的损失函数和KTT
Q:项目的细节问的比较多，建议项目上的细节也尽可能搞清楚
Q:问某个比赛的模型搭建细节，从特征工程到模型完整的叙述一遍
Q:你是如何利用GDBT将连续特征离散化的
Q:GDBT的基模型是什么，对应的损失函数是什么，怎么分裂的节点
Q:GDBT和XGB的区别（又问了一次）
Q:LR，FFM，DEEPFM之间的区别和联系
Q:如何通过用户历史点击记录构建用户画像的embedding，在这里你有什么创新，和别的队伍比起来。
Q:DIN模型的核心思想是什么，如何用在你的比赛里面的
----------------------------------------
(HR打电话约了下周四面)
3面（30min）（3月12）
Q：自我介绍一下吧
A：吧啦吧啦吧啦.....
Q：问论文,这块占了点时间，因为我论文用到协同进化，这块比较小众，解释起来有点吃力。 Q：我们来个编程题吧：二叉树，输出每一层最左面的结点值
A：这个用层序遍历，解决起来比较容易理解，也可以用先序遍历，因为，先序遍历时候，一定可以保证每一层最左面的结点，最先访问
其他结点后面访问，那么我们可以开一个map,map(h)=a 表示第h层的第一个结点值是a，先序遍历时候可以把层数传进去，然后每次检查
map中当前层是否存在，如果不存在就保存，存在的话就不管了。
A：说完思路写完后，我说非递归也可以写
Q：那你写写
A：写着写着感觉不对劲，层数没法知道，一个方法是把树结点结构体里面加上层数，但是这样破坏了原始结构，另一个方法是开了个记录层数的栈，和结点栈同时入栈出栈，解决了。
Q: 好了，我这里没问题了
-------------------------------------
4面（15min）（3月15）
Hr打电话说通过了，等待审批，感谢牛客！
OFFER CALL（5min）（3月17）
收到实习OFFER啦，字节效率真的高
