十七的实习

Posted by WildCow on February 25, 2019

写在前面


何其有幸





置顶的感谢


感谢学长 @雨人 给的一个内推和指导,并在简历上给了我特别大的帮助!
感谢小星 @Vacant小星 给的两个内推和鼓励 QAQ
感谢哥哥 @txl 帮忙找人联系的两个内推
感谢两个老师帮忙联系的内推
感谢 @ACM贴吧群 经常讨论题目,从中学到很多
非常感谢诸位的帮助 QAQ




阿里(3.15 算法一面)


阿里异常的迷
简历刚投过去
第二天就发邮件让我补充简历
补充完以后就催我做测评
测评感觉谜之鬼畜……
充斥着阅读理解、计算、图表阅读……
还给你限时
太头大了 QAQ
自评也很窒息
莫名的觉得尬。。。。。
然后第三天下午
在和甜学姐一起准备甜学姐的旷视一面
然后突然阿里的电话就打过来了QAQ
毫无通知,毫无准备,第一次面试就这样 lei 了
面试官:先介绍一下你自己吧
我:balabalabala
面试官:对我们这边的岗位哪些有兴趣
我:不清楚 QAQ,我对贵公司岗位没有什么了解,能介绍一下吗
面试官:太多了一个小时都讲不完,建议以后自己去了解
面试官:讲讲 α β剪枝
我:balabala
面试官:你觉得你和那些不参加算法的人相比,你的优势和弱势在哪?
我:实践能力更强,理论能力,概念的记忆更弱
面试官:说说你 ACM 用的算法
我:刚开始以为是讲个大概,然后面试官让我详细的说算法,于是说了说最短路的 SPFA 和 Dijkstra,还说了说复杂度以及对图的要求,没有纸笔空讲真的好窒息
面试官:你图论好像很熟悉,一些图相关的框架你知道么
我:不知道
面试官:介绍一下你的简历里说的数据库说的块状链表
我:balabala
面试官:你会不会XXX(这里我甚至没听懂是啥)
我:不会
面试官:数据库你懂的哪些
我:我知道 oracle 和 sql(说到 oracle 的时候内心一阵剧痛)
面试官:说说
我:balabala(说的跟 shift 一样,连增删查改都没说清,因为确实不懂)
(这个时候内心已经崩了,明明面的是算法岗为什么问我数据库)
面试官:你有什么问题问我吗?
我:评价一下?
面试官:觉得你有一点埋头读书,应该多了解一下理论的实际运用
我:好QAQ


感觉前面的都还好,就是从数据库 mysql 那里就开始崩了
第一次面试还是太紧张
很多都没发挥好
本来想着找一个小厂献祭一下的
没想到拿起来就把阿里献祭了
回去分析了半天为什么面算法数据库会被抓着问
后来发现是因为我简历写了我实现了一个数据库的算法
估计面试官就以为我了解数据库
但我写的是底层啊QAQ
自己的很多东西还是没有表述清楚
后面加油吧QAQ



百度(3.18 算法一面)


一开始按照惯例自我介绍
然后和面试官说了说 ACM 经历和收获啥的
然后面试官给了我一个共享的屏幕,让我写写题
第一个问题是二叉树的最大深度
面试官说给我 30 ~ 40 分钟
我内心突然有了一种被侮辱智商的感觉(不含贬义)
然后哐哐哐写完
写完后面试官让我说说
我 balabala
面试官:递归你平常用的多么
我:天天用
(然后他就再也没有问我递归的问题)
下一个问题是全序列第 k 大
直接按照快排思想写就好了
写完以后面试官的屏幕崩了打不开。。。
场面很尴尬。。。
于是他就让我说说
我 balabala
他问我复杂度
我:$n + n / 2 + n / 4 + … + 1$ 是 $O(n)$ 的
面试官:你知道堆吗
我:知道
面试官:那你用堆做做
我:就维护一个大小为 $k$ 的小根堆,遍历的时候跟顶端比较一下更新就好了
面试官:复杂度?
我:$O(nlogk)$
(这里面试官纠正我说是 $O(nklogk)$,那个时候内心隐隐约约觉得不太对,就没有深想,现在觉得是面试官错了= =!)
面试官:给你两个没排序好的大文件,你要把他合并成一个有序的大文件
(我刚开始卡了一会,面试官说我有什么想法可以说,他会给我一些提示之类的)
(不过后来我也是全程自己分析出来了,听我叙述过程中会嗯几声肯定我的思考方向)
我:首先要想办法把两个文件有序,然后就能直接合并了 balabala
(最后给出了每次取一部分然后合并有序的方法)
面试官:你会 Python 么
我:不会,但能看懂 Python 代码
面试官:糟糕本来想让你用 Python 写一下的
面试官:给你若干个数字,有一些数字带有删除标记,带有删除标记后的数字一定要被删除,最后你要把他们去重后输出
我:两个平衡树?一个维护删除的,一个维护未删除已经输出的
面试官:复杂度多少?
我:$O(nlog)$
面试官:你为啥用平衡树?
我:你给我数字贼他妈大怎么办(这是原话QAQ,刚说出口我就后悔了)
面试官:那假如没那么大呢
我:那就两个数组?
面试官:有没有 O(1) 空间的
(在面试官的百般提示下,我想出了若干个 $O(n)$ 的,没有想出空间 $O(1)$ 的)
面试官:有什么想问的么?
我:评价一下
面试官:基础还行
然后就等通知了。。。。。





一清科技(3.18 算法一面)


一清科技真的是噩梦
感觉发挥得最不好的一次
很内疚对不起小星┭┮﹏┭┮
最开始的时候问我想做啥
我就知道一清科技是做自动驾驶的
我就说了这个
然后他就开始直接问辅助驾驶相关的东西惹!
大意就是辅助驾驶需要一些什么黑科技,要用到什么
我啥都不知道啊QAAAAAAAAAAAAAAAAAQ
然后就崩了
不知道说了啥
然后他问我人工智能看了些啥
我说我现在看了简单的神经网络,还有分类器一类的
他问我有没有自己写过
我告诉他我只看了证明
然后他问我大一的 α β 剪枝学了多久
我说两周
然后他感慨了一声学的蛮快的
内心刚觉得有戏
他就突然问我如果现在改进会用什么方法
我内心就又崩了
我都说了我只会分类算法了我要怎么改进啊QAQ
然后我也不知道和他说了什么。。。
他说辅助驾驶是他们的核心,我这样肯定不太行的
我说我可以先去其它部门慢慢学
最后他问我成绩怎么样
。。。。。。
心态又又又又又又就炸了
前 50%
他问我为什么
就。。。搞竞赛荒废学业了呗,然后政治课啥的再拖一拖分数。。。。
他说你竞赛和那些应该有很大关系的吖,竞赛搞得不错专业课肯定没问题啊
我跟他说关系其实不是很大,竞赛学的和专业课的不是一个东西
他好像不信
本来想说的是其实是我不太会应对考试,他可以试着问我专业课问题
想了想觉得像在狡辩。。。就没说
然后我就彻底凉了
这次面试好迷啊
感觉面试官应该更注重我的科研能力
然后刚开始的时候好害怕。。。脑子转不动。。。
这个面试没过我倒是认了
但是一个算法题不问QAQ
一个专业课的内容都不问QAQ
我没写过那些人工智能的
但是那些公式的推导我都是能直接推的。。。
包括理论
面试官也没问
这些我都会的啊QAQ
委屈巴巴
星爷对不起 QAQ





深信服(3.21 算法一面,3.22 算法二面)


一面

深信服的简历是真的难投
找了学长内推
就毫无消息了
然后我直接投简历。。。
简历被筛了。。。。。。。
最后小星主动问我要不要帮我内推
小星大好人!
终于内推上了!!!
面试体验极好!
面试官:自我介绍一下
我:balabala
然后就直接算法题了!!!!!!
面试官:给你一个序列找出正好 $k$ 个连续的数字让他和为 $t$
我:你先取前 $k$ 个然后双指针挪一下?
面试官:如果最少的连续数字让他和为 $t$ 呢?
我:双指针尺取,你维护一下你双指针指的区域的和,小于 $t$ 你挪右指针,大于 $t$ 你挪左指针
(刚开始的时候没听清以为不是连续的,把我吓蒙了,最后面试官发现我听错题了就又说了一遍题目把拽回来了,面试官人真好啊QAQ)
面试官:如果有负数呢?
我:加一个较大的值把他们变成正数好像可行?
面试官:我觉得不行
我:我的直觉告诉我要前缀和,这样你能 $O(n^2)$ 枚举区间,我想办法优化一下
(然后提出了一些错误做法,被面试官否认掉了QAQ)
(当我觉得前缀和的方法是错的时候)
面试官:你前缀和后考虑一下有没有 $O(nlogn)$ 的
(啊啊啊啊啊啊啊我是撒子)
我:我会了我会了我会了你排序一下二分就好了QAQ
面试官:如果 $n$ 比较小你会不会 $O(n)$ 的
(这里是真的不懂然后口胡了一个错误的,最后面试官说他想让我讲的是哈希)
面试官:给你一个序列和一个集合 $s$,求包含集合内的所有元素的最短区间
我:一样的啊,你开两个数组去记录,再开一个变量记录当前双指针的区间内的数字和集合内的差
面试官:详细说一下
我:balabala
(这里面试官真的超级有耐心!没用纸笔我在那里慢慢的和他说)
面试官:求矩阵的的最长上升路径
我:这不显然是地皮嘛?你 $dp[i][j]$ 表示矩阵 $i$,$j$ 位置的最长上升路径然后爆搜转移?感觉 $O(n^2)$ 或者 $O(n^3)$ 可行?
面试官:是以 $i$,$j$ 结尾还是?
我:那肯定得是结尾啊,要不然你怎么转移
面试官:那如果要求最长上升等差数列呢?
我:那你四个方向差分一下,不久转化成了求矩阵最长相等数的序列,和刚刚的方法一样一样的
面试官:你其实带公差转移就可以?
我:好像是的
面试官:给你一个手机号的黑名单,再给你一个数字段,问你这个数字段有没有可能属于黑名单内的手机号
我:这不就相当于给你 $n$ 个串串然后询问一个串串是否是他们的子串,你预处理所有前缀跑个 AC 自动机就好了,或者直接后缀自动机?我方向不是搞串串的,具体实现我不太清楚,我只知道有这个东西然后这个东西能解决这个问题
面试管:恩
面试官:$n$ 个数字,你要选两个让他们的异或和最大
我:这不就是线性基什么的么 balabala
面试官:讲讲
我:balabala
面试官:不对,你线性基没法保证取两个
(内心一凉)
我:那你建个 01 字典树然后贪心?$1$ 往 $0$ 走, $0$ 往 $1$ 走
然后一面就结束了,让我等通知



后来周五二面发短信让我定时间,我想的是周六头条面试干脆定周日吧
结果周五四点多的时候回我短信说周日不行要下周一
我就想着早死晚死都得死直接当天面完得了

二面

面试官:介绍一下你自己
我:balabala
面试官:你 $ACM$ 方向是什么
我:图论和数据结构
面试官:那我问你一个图论题吧,给你一个图,边权两个属性,求 $B$ 属性递增的前提下, $A$ 属性的和最小的路径
我:你转移的时候两个状态一起转移好像可以?
面试官:不行,你想想看这个情况 balabala
我:那我好像只会先根据 $B$ 建立一个 $DAG$ 然后跑最短路了
面试官好像不太满意
面试官:20 个物品,每个物品有自己的价值,两个人分赃,要求丢弃的物品尽可能少的前提下让两个人分到的赃物相等
(啊啊啊啊啊啊啊啊啊这个 $ACM$ 群里讨论过这个问题这个我会这个我会)
我:你 $dp[i][j]$ 表示前 $i$ 个物品两个人获得的价值差为 $j$ 时的最少丢弃赃物数,然后每个物品要不然给 $A$,要不然给 $B$,要不然丢弃,三个状态转移就好了,时间复杂度 $O(n^2max_{value})$
面试官:那物品价值很大呢
(想了一会儿后反应过来要针对 $n$ 非常小来搞)
我:你直接每个物品三个状态二进制枚举?$O(3^n)$,有点丑
面试官:是的,你想想怎么优化
我:也许能少枚举一个状态 balabala?
(过了一会)
我:我会了我会了你直接折半枚举 + hash 就好了
面试官:你退役后都在干啥
我:给下一级讲讲课,学学数学……
(然后面试官以肉眼可见的速度兴奋起来了)
面试官:来个数学题?
我:。。。。好
(然后是个二次剩余)
(好像还有其他问题,我忘了 QAQ)
然后就等通知去



字节跳动(3.23 后端一面,二面,三面)


头条的面试是真的修罗场
能很清楚的感受到面试官给的压力
如果没有经验我肯定一面就直接崩了
所以说多面试还是有用的QAQ
之前的笔试感觉还是很简单的
就是带小数的题没有 $spj$ 太没有出题道德了QAQ


一面

面试官:你是搞 $ACM$ 的,那我就不问你算法题了吧?
我:。。。。。。。。。。。。。。。。。。。。
面试官:说说你的 $AI$ 下棋
我:balabala
面试官:有遇到什么问题吗?都是怎么解决的
我:balabala
(然后说了说我的那个剪枝)
面试官:你这边语言是 C++,那我先问你点 C++ 的吧,说说 static
我:变量的时候 balabala,
面试官:还有呢
我:作类的参数的时候 balabala
(漏了一个没有 this 指针)
(然后好像还问了一个东西,但是我不会)
面试官:写个 C++ 中的字符串比较函数吧
(下意识的当作 $ACM$ 来写了,就直接搓了一个和长度相关的字符集都是英文字母的比较函数)
面试官:$strlen$ 返回值是什么类型
我:$unsigned$ $int$
(然后我看了看我用 $int$ 存了)
(然后他拿了一个十六进制表示的玩意把我的代码叉掉了。。。。。)
(这里详细的说一下,面试官想要的是鲁棒性好的函数,我用 $int$ 存会出现长度过长直接炸的情况。。。。也就是我应该考虑数据非法的情况,而不是 $ACM$ 中数据保证合法,时间合理的情况)
面试官:$stl$ 库了解吧?
我:了解了解,我 C++ 没写过工程,但 stl 库用的多
面试官:$vector$ 说一说
我:官方的说法是向量,实现是不定长数组
面试官:实现说一说
我:你记录一下内部的元素个数,当等于长度的时候,你就开一个两倍的空间
面试官:然后呢?
我:你把原来的复制过去啊
(好吓人。。。还好我 $vector$ 是真的了解)
面试官:为啥是两倍扩大?不能是每次加一个定值
我:对于一个目标长度,你两倍扩到复杂度是 $log$ 的,你每次加定值是 $O(n)$ 的,这是时间和空间折中下选择的数字
面试官:那你对一个 $vector$ $push_back$ $n$ 个元素的复杂度是多少?
我:那不就是一个等比数列求前 $n$ 项和?
面试官:那是多少呢?
(手玩了一下,然后小声嘀咕好像 $2$ 的某个次方的量,然后被他听到了)
面试官:所以复杂度是 $O(2^n)$
我:这显然不对啊
(过了一会)
我:$O(2^{log_2n})$
(是的这个数字我想抽死自己。。。)
面试官:这是多少?
我:$O(n)。。。。。。。$
面试官:那我 1.1 倍会有什么问题呢
我:这个是 $vecotor$ 两倍扩大的一个缺陷,你每次扩大的一定会大于之前所有的内容之和,说明你没办法复用
面试官:那我 1.5 倍扩大扩大多少次能复用呢
我:不就是一个等比数列前 $n$ 项和解一个不等式组?
面试官:那是多少呢?
(然后我在那里算)
面试官:来个 $OS$ 的问题,进程线程的区别
我:balabala
面试官:线程通信
我:我只知道一定有信号和信号量。。。
面试官:信号和信号量的区别
我:balabala
面试官:说说信号量
(然后我就说了一丢丢。。。)
面试官:我用变量控制共同两个程序对内存的读写可以嘛
我:不可以你变量也有同步和互斥问题
面试官:那一个只读一个只写呢
我:我的直觉告诉我有问题。。。但我不知道问题在哪
面试官:来计网吧,TCP 和 UDP 区别
我:balabala
面试官:四次挥手
我:balabala
面试官:我第二次挥手后,你 $socket$ 都关闭了,客户端是怎么接受信息的
(什么玩意,不是应该问四次挥手的必要性和 2MSL 嘛???????????)
我:不知道。。。
面试官:说说 $Linux$ 下的计网通信指令
我:。。。。。。。不会。。。Windows 的我也不会。。。。。
面试官:我给你发了 Hello,我这里显示发送成功,你那里确认收到了吗?
我:肯定没有啊。。。
面试官:那他在哪。。。
我:可能在滑动窗口那里吧。。。。。。。
面试官:连连看你能想到什么算法嘛?
我:直接爆搜?或者根据你给我的两个块的开口方向能够剪枝
(这题我和他讨论了很多,最后给出了一个根据转角数判断的爆搜)

然后我以为凉了。。。
跟内推我的学长说了说
然后把手机开机。。。。。。
头条电话打过来让我马上开始二面。。。。。

二面

面试官:既然你是搞 $ACM$ 的,那我问你点难的吧
我:。。。。。。。。。。。。。。。。。。。。
(然后他不告诉我数据范围。。。我写完了尺取他才告诉我有负数。。。。。反正就是各种崩)
(然后他问了我 git 语句!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!)
(我从来不知道这个也可以问!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!)
(然后我 git 回退操作说了个二分。。。。。)
面试官:map 底层?
我:红黑树
面试官:说说红黑树
我:balabala
然后就没了。。。
当时是真的难过了。。。。
觉得人没了
但是通过了!!!!!
我都不知道为什么!
有机会一定要问问为什么我能过!

三面

面试官:说说 $ACM$ 给你带来了什么
(我他妈!!!!!!!!!!!)
(不过这个部分我确实有蛮多想说的。。以后会单独写一篇)
面试官:说说容量控制
我:balabala
面试官:说说 hash 冲突的解决方法
我:balabala
面试官:说说哈希扩容
我:balabala,然后你重新计算原来的哈希值
面试官:那不觉得很浪费么
(内心一凉。。。我记得确实是重新计算的啊QAQ)
我:你能不能用一个变量标记一下,发生冲突的时候判断是不是重新计算过的,如果不是,就对原来的进行再哈希,如果是,就按照哈希冲突
(这样其实是不对的,因为你查找的时候会有问题)
(现在我会了(骄傲),和我说的那个思想是很接近的)
面试官:给你一个大表,你要进行查找
我:哈希?
面试官:哈希冲突你准备怎么办
我:双蛤习?
面试官:再想想?在我足够多,且大于你模数的前提下,你双蛤习只能判断冲突,没办法存
(想了一会后)
我:你对冲突的建平衡树?
(后来(2019/3/27)我看了 $JAVA$ jdk1.8 才发现他问的其实就是那里的 hash_map)
面试官:后端你了解多少
我:我就懂得大概要学什么。。数据库。。高并发之类的。。。我可以学!!!!!
然后就。。。。等通知。。。。。。。



百度(3.24 C++ 开发一面)


面完头条
以为解放了
吃着麻辣香锅
然后在食堂百度的电话打过来
说我的能力算法岗肯定是不行的
问我要不要试试 $C++$ 开发
我说好吖。。。
然后就约了个时间

一面

面试官:给你一个序列,你要求最大的 $a_j - a_i$ 其中 $j > i$
(然后我给了两个方法面试官都没听懂。。。有点尴尬)
面试官:最长公共子序列
我:balabala
面试官:最长公共子串
我:balabala
面试官:说说 $C++$ 的内存调用
(然后我给他说了说 new 和 malloc 的区别)
面试官:说说 $C++$ 的多态
我:balabala
面试官:多态的实现?
我:操作符的重载我不知道,虚函数是用虚函数表
面试官:说说
我:我只知道一点简单的概念balabala
(然后就是 map -> 红黑树二连)
面试官:给你一个无限长的字节流,你要保证等概率选取
(我自己嘀咕很久以后)
我:第 $i$ 个字节流被选为预备役的概率为 $1 / i$ 就行了,然后我给他证了一下
面试官:有什么想问我的吗?
我:评价一下?
面试官:这个问题以后建议你不要问,因为 balabala
(我一脸蒙蔽)
然后 3.28 约了二面qwq