字节跳动实习算法岗面经

今天下午终于等到了心心念的字节跳动算法实习生的面试，我报的是算法实习生-数据挖掘、搜索、推荐三个访方面。
等待面试
心里十分慌张，把自我介绍翻来覆去的念。不过很快就收到了一面的短信。
一面
一面是一个特别和蔼的面试官，我们用Q来代表面试官。A表示我。
A：面试官，你好
Q：你好，先坐一下自我介绍吧
A：好的,balabala。（这个地方大家千万不要紧张，放平心态，在下面先准备好自我介绍，上去直接说）
Q：好的，说说你最近做了什么项目吧？
A:(划重点！！！项目一定要挑自己熟悉的说，简历上放一些和岗位相关的项目)。我说了自己最近写的一个深度神经网络的框架和一个刚刚做不久的小车AI的项目。
Q：仔细说说你这个小车的项目。
A：balabala(进行了适当的美化)
Q：你说你写了个深度神经网络的框架，那你给我简单说一下Batch Normalization是什么意思
A：(这个概念好久没用了)，简单介绍了Batch Normalization的特性，感觉说的不是很清楚，因为有点忘了。
Q：看你的简历项目里有数据降维和可视化的项目，简单说一下LDA的思想
A：LDA是一种有监督的降维算法，其基本思想是让同一类样本降维之后尽可能的聚在一起，不同类的样本尽可能地分散。然后又简单说了一下公式
Q：那这个T-SNE算法呢
A：这个算法的主要思想是balabala。中间提到了相对熵（KL散度）
Q：那你写一下相对熵的公式吧

A: $P_{ij}log\frac{q_{ij}}{p_{ij}}$
Q：好的，那咱们来做一道编程题吧
A：(传说中的编程题终于出现了)好的
Q：有两个字符串，你只可以进行删除操作，问你最少进行多少次操作可以使两个字符串相等。例:sea,eat需要两次删除操作
A：这个简单，思路就是用动态规划求两个字符串的最大公共字串的长度。然后使用每一个字符串的长度减去公共子字符串的长度。
Q：那咱们再加一点，如果我想要知道每个字符串需要删除的字符是那些呢，
A：那我们就需要求出最大公共字串具体是由什么字符构成的，思路也是动态规划。(很快就写完了)
Q:嗯，好的，那你有什么想要问我的么
A：balabala。问了俩问题。
一面结束
感想的话就是面试官会根据你的项目一点点来问你，问你一个问题的时候，这个时候尽可能不要挤牙膏：问一句，回答一句，要根据这个问题发散的回答，把节奏掌握再自己手里。
二面
二面的面试官是一个比较严肃的。
Q：先做个自我介绍把
A：balabalba.....
Q：好的，那先来做一道编程题把
A：(我???咋不按套路出牌)
Q：给你一个二叉查找树，还有一个数K。如果能找到，就返回节点，如果找不到，就返回空
A：(这个题就很简单，一遍过)
Q：你是用递归的形式实现的，那么和非递归，递归怎么样?
A：emmmmmm，占用内存更多。
Q：具体是什么意思？能详细说说么
A：emmmmm，这个就是每次递归都需要保存一些数据、节点什么的。具体我不是很清楚
Q：那递归有什么缺点
A:当递归层数很多的时候，容易造成内存溢出
Q：介绍一下你的深度神经网络模型
A：balablabla
Q：你刚刚说了鞍点，你知道鞍点的定义么，鞍点有什么特点？
A：emmmmmmm，不太清楚，只是知道这个概念。
Q：好的，下面我们来一个开放式的问题:现在有一组数，其中有m对数是两两有序的，请你设计一种算法来对这一组数排序。
A：（冥思苦想之后)这个不太会，没啥思路
Q：（循循善诱）想想图中的有向图，和排课表的问题
A：（没看图啊。都忘干净了）这个我还是不会。
Q：好吧。那我们换一个，有M个有序链表（从大到小）。现在我们要取出前K大的元素。
A：（哇，这个我见过，内心美滋滋）我们应该把M个链表的头节点做成一个大小为M的最大堆，每次取出堆中最大的节点，然后将这个节点的后序节点放进来，重新对堆进行排序。
Q：好的，那这个算法的时间复杂度和空间复杂度是多少呢

A：时间复杂度，每次需要 $O(log^{m})$ ，需要k次，那么总的时间复杂度为 $O(klog^{m})$ 。空间复杂度为 $O(m)$
Q：那建立这个堆的时候时间复杂度是多少？

A： $O(mlog^{m})$ ，那总的时间复杂度应该为 $O((k+m)log^{m})$ 。
Q：好的，这次面试就到这了
二面总结
二面都是数据结构相关的题，但是都比较基础，果然编程和数据结构是躲不过的两座大山。以及如果面试遇到不会的题，不要着急，直接和面试官说，一般都会再给一次机会的。本来以为回答的一半，可能凉了，没想到收到了三面的短信。
三面
三面的面试官也是一个比较亲切的模样
Q：先做个五分钟左右的自我介绍把
A：balabala(其中说到了自己熟悉C++)
Q：好的，那我们先来问一点C语言的。C语言中结构体struct{int i; bool b}一共占几个字节
A：如果int类型占4个字节的话，那么这个结构体一共需要8个字节。
Q：ok,那(问了C语言的问题，表示从来没见过)
A：不会
Q：好的，那offset(b)在结构体中偏移几个字节
A：4个字节
Q：那么你会计算结构体中每个变量相对于结构体偏移几个字节么。
A：这个不太会
Q：好的。那么union了解么
A：了解，和struct类似，但是是共享内存。
Q：OK，那问一道概率方面的题把,几何分布知道什么意思么
A：听名字有点忘了，但是概念还记得
Q：那伯努利分布知道么
A：嗯，了解
Q：现在我有抛一枚硬币，正面朝上的概率是p,反面是1-p。那么第k次抛的时候出现第一次正面的概率是多少?

A: $P(1-p)^{k-1}$

Q：好的，那么我们设 $f(z=k)=p(1-p)^{k-1}$ ，那你计算一下 $E(z)$ （求个均值）

A：(想了一会) $E(z)=p+2p(1-p)+3p(1-p)^{2}+...+mp(1-p)^{m-1}$
Q：能不能计算一下 $E(z)$ 的数学表达式

A：好的，思考了一会，可以使用 $E(z)-(1-p)E(z)=A$ 。其中A是一个等比数列。然后就可以求出E(z)。
Q：ok,来做一道编程题把
A：好的
Q：我们输入两个值n和k，n表示我们有从1到n个整数，然后将这些整数都字符串化之后按字典排序，找出其中第K大的。例如:n=15,k=5.那么1-15字符串化之后排序如下:1,10,11,12,13,14,15,2,3,4,5,6,7,8,9。其中第5大的就为13。
A：好的，我想想(其实完全没思路，但是明显这种题有时间复杂度为O(1)的解)，说了几种想法，都被否了
Q：那你说一种时间复杂度为O(k)的算法也可以
A：（思索一会）O(k)的话就相当于我们将前k大个元素都求了出来。（然后开始写代码）
5分钟过去了，写好了
Q：你看看代码是不是还有点问题
A：（emmmmmmmmm）说出问题，修改
Q：你再看看那，是不是还不太对
A(emmmmmmmmm????)找问题，想，说出问题，修改
Q：嗯，ok
Q：你还有什么想要问我的么
A：啊，没有了，刚刚一面问过了（想问问我这样能不能发了offer）
Q：好的，那面试就到此结束了，
A：好的，谢谢面试官
三面总结:
突然考到了语法基础和数学基础，不得不感叹问的真的广，然后面试官给你的代码一时半会没有思路也不要着急，和面试官说你的想法，慢慢改正，放平心态，一般都可以做出来
- - - - - - - - -
经过了漫长的10分钟后，接到了等通知的消息。
- - - - - - - - -
我是3.30号面试的，今天4.8号收到了offer call。也祝大家可以早日收到心仪的offer

- - - - - - - - -
关于最后一面的算法，有几个同学私信问我，复杂度为O(k)的算法代码Demo如下了，但是面试时候我手写的代码完成度没有这么高，但是思路差不多；因此面试的时候手撕代码主要是思路没问题就OK:

#include <iostream>
using namespace std;
int main(){
    int n,k;
    cin>>n>>k;
    if(k == 1) cout<<1<<endl;
    else{
        k--;
        int base = 10;
        int res;
        while(k > 0){
            res = base;
            while(res<n && k>0){
                res*=10;
                k--;
            }
            res=res/10;
            while(res<n && k>0){
                res++;
                k--;
            }
            base++;
        }
        cout<<res<<endl;
    }

    return 0;
}

#字节跳动##实习##面经##春招##算法工程师#