「面试」字节跳动 - ByteCamp 算法赛道

前言

五月份的时候报名了头条的 ByteCamp,结果当时两场笔试都咕咕咕了,于是就自然而然的凉凉了。结果最近又要补录几个人,y哥就帮我内推了一下,过了快一周收到了面试通知。

面试

由于收到面试通知的时候我在家,所以是在牛客网上进行的视频面试。下午四点钟顺利开始面试。

面试官:先想这样一个问题,如何求一棵树里最远的两个点之间的距离

我:这个问题也就是求树的直径,先从任意一个点 x 开始 BFS,找到离 x 最远的点 y,然后再从 y 开始 BFS 找到离 y 最远的点 z,y 与 z 之间的距离就是树中的最远距离

面试官:emm,你是这样做的啊,我的思路是递归然后回溯的时候来求答案,你明白我这个做法么?

我:哦,那这就是两遍 DP 吧,维护一下以一个点为根的子树中的最长链和次长链,以及该子树外的最长链,就可以直接算答案了

面试官:emm,嗯,那这两种做法哪个更好呢?我这个复杂度是不是更好一点?

我:复杂度一样啊,都是 O(n)

面试官:我说的是空间上,你是不是需要多开一些数组?

我:(mdzz),BFS 的话的确是需要一个队列,但是总空间开销不一定比 DFS 多啊,况且 DFS 还有栈空间的开销,而且 BFS 不存在递归太多爆栈的问题

面试官:这么说也是,好吧。那我们下一道题,给你一个字符串,找出第一个仅出现一次的字符。

我:(深思熟虑半分钟),难道真的有比暴力更好的做法么,就是扫一遍拿数组或者 map 记一下每个字符出现的次数,然后从头再扫一遍找到第一个出现一次的就是答案。

面试官:那你再想想有什么更好的做法没

我:(???……),或者可以倒着扫一遍,扫的时候还是要维护每个字符的出现次数。然后我们维护一个栈,如果当前字符第一次出现就将其加入栈中;否则,若当前字符与栈顶字符相同,就将栈顶弹出,若新的栈顶出现次数也不为 1 就继续弹,直到栈顶元素当前只出现过一次。这样扫完栈顶就是答案。

面试官:嗯,这个思路不错

我:(??????????这哪里比暴力好了),好吧。

面试官:那再来最后一个问题,给你一个数字字符串,怎样将其转换成对应的数字?

我:a = a * 10 + c - ‘0’

面试官:emm?

我:就是从高位到低位,一位一位的取出来加到数字上

面试官:你这个 - ‘0’ 是什么意思?

我:就是把字符 ASCII 码转换成对应的数字啊,’0’ 就等于 48 呗

面试官:啊好吧,有道理,那就这样吧。

后记

感觉真的是一场很奇葩的面试,怀疑面试官是个实习生,或者平时工作根本不搞算法。

然后三天后就顺利拿到入营 offer 了,骗吃骗喝骗车票成功✅