这周一参加了Airbnb中国部门的校招面试，周五通过邮件收到了offer，非常开心，于是记录一下airbnb面试的过程。
Airbnb的校招面试和国内的公司很不一样。国内的面试一般都是通过针对简历或者他们具体的工作场景提问题，在白纸上手写代码等方式来评估面试者的水平；Airbnb的三轮面试都是在笔记本电脑上写具体的程序并通过他们给您的样例。面试官会让你在https://coderpad.io 上针对他提出的算法题写一个能运行的程序，并可以通过面试官给你的几个样例。当然，这三轮面试的算法题的难度适中
第一轮面试
第一轮面试的题目是：给你一个机票价格的列表，列表中每一项为【出发地，目的地，价格】，面试官给你一个起点s和终点e，要求你找出一个不超过K次转机的最便宜的从s到e的方案。
这个题目其实还是蛮简单的，最基础的就是用搜索剪枝的方式写一个递归程序进行求解，当然还可以略微改动一下迪杰斯特拉算法得到效率更高的解法。 但是我在一开始用递归的方式去做的时候写了一个非常不容易被察觉的bug（很蠢的bug），用了很久去找这个bug所以没有时间去写迪杰斯特拉方法进行求解了。
第二轮面试
第二轮面试的题目是：给你一个字符串和一个Transform表，判断这个字符串是不是符合Transform表的输出（True或者False），Transform是这样，对于一个长度为n的字符串，相邻的两个字符组合起来作为Transform表的输入，输出在表中查询，如输入字符串为“AABBCC”，那么我们分别把“AA,AB,BB,BC,CC”作为Transform表的输入，得到了转化之后的字符串，例如“CABDC”，然后一直这样做，直到只剩下了一个字母，如果这个字母为“C”或者“D”，那么就是True，否则为False。
这个题目困难的地方是在于一个字符串“AABBCC”可能可以通过Transform表生成多个转化后的输入，因为输入为“AA”，transform表的输出可能为A或者C这样。但是也可以通过递归的方式去求解这道题目。
在做完之后，又和面试官聊了聊如何优化这个算法（暂存表）。聊完这些又和面试官聊了一会儿LGD和OG的ti8决赛23333（LGD真是让人生气，又让人觉得可惜，又让人觉得无奈）。
第三轮面试
第三轮面试的题目是：按照节点ID的顺序给你一些树的节点，节点里面存的值仅为0或者1。给你一些边，边存储的是树的边，如“1 2”表示节点2是节点1的孩子。给你节点的初始值，给你节点的目标值，你需要计算最少通过几次“操作”，树可以从的初始值可以变为目标值。 “操作”是按照这个规则进行的，比如我要改变节点a的值（原本为0），那么我们会首先改变节点a的值（变为1），然后再去改变a的孩子的孩子的值，然后再依次变化下去直到没有节点的值可以更改（有点类似于红黑树的操作）。
这个题目其实还是挺难的，因为你要在30多分钟的时间里（面试时间45分钟，面试官描述题目描述了好久）写出来这个题目。首先，你要根据给你的边和节点去构造一棵树，然后你要通过层次遍历的方式以此把每个节点的值变为目标值，同时，你也要写好这个“操作”的函数，所以时间还是非常紧张的。 而且coderpad和leetcode不一样，需要你自己去手写输入，所以样例都需要你自己输入，很慢很麻烦。
面试总结
Airbnb的面试给我的感受就是他们很重视你实际写代码的能力，虽然三轮面试的算法题不算很难，但是你需要在30几分钟的时间内写好一个可以运行正确无误的程序，并通过面试官的几个样例，还是有一定的挑战性的。当然，Airbnb的面试其实也挺基础的，对于在大学里面认真学习了的或者刷了好几遍leetcode的计算机系同学来说，不算特别难。
网友评论