Airbnb 的面试跟很多独角兽公司（比如snapchat，uber）一样，不仅仅是把代码写出来，要求编译通过，并且可以跑通。这样其实对debug的能力有不小要求，Java的话可以用 System.out.println() 来debug。别的语言就是用自己的print 函数啦。
接下来要说的题目和出现频率数据来自面试学生的反馈，地里的帖子以及 Glassdoor。
2018年10 - 12月 期间，出现最多的店面题目是 Pour Water 和 Sliding Puzzle。
Pour Water 这题虽然 leetcode上有， 链接是 https://leetcode.com/problems/pour-water/ 。题目如下：
We are given an elevation map, heights[i] representing the height of the terrain at that index. The width at each index is 1. After V units of water fall at index K , how much water is at each index?
Water first drops at index K and rests on top of the highest terrain or water at that index. Then, it flows according to the following rules:
- If the droplet would eventually fall by moving left, then move left.
- Otherwise, if the droplet would eventually fall by moving right, then move right.
- Otherwise, rise at it’s current position.
Here, “eventually fall” means that the droplet will eventually be at a lower level if it moves in that direction. Also, “level” means the height of the terrain plus any water in that column.
We can assume there’s infinitely high terrain on the two sides out of bounds of the array. Also, there could not be partial water being spread out evenly on more than 1 grid block - each unit of water has to be in exactly one block.
Note:
-
heightswill have length in[1, 100]and contain integers in[0, 99]. -
Vwill be in range[0, 2000]. -
Kwill be in range[0, heights.length - 1].
Input: heights = [2,1,1,2,1,2,2], V = 4, K = 3
Output: [2,2,2,3,2,2,2]
Explanation:
# #
# #
## # ###
#########
0123456 <- index
The first drop of water lands at index K = 3:
# #
# w #
## # ###
#########
0123456
When moving left or right, the water can only move to the same level or a lower level.
(By level, we mean the total height of the terrain plus any water in that column.)
Since moving left will eventually make it fall, it moves left.
(A droplet "made to fall" means go to a lower height than it was at previously.)
# #
# #
## w# ###
#########
0123456
Since moving left will not make it fall, it stays in place. The next droplet falls:
# #
# w #
## w# ###
#########
0123456
Since the new droplet moving left will eventually make it fall, it moves left.
Notice that the droplet still preferred to move left,
even though it could move right (and moving right makes it fall quicker.)
# #
# w #
## w# ###
#########
0123456
# #
# #
##ww# ###
#########
0123456
After those steps, the third droplet falls.
Since moving left would not eventually make it fall, it tries to move right.
Since moving right would eventually make it fall, it moves right.
# #
# w #
##ww# ###
#########
0123456
# #
# #
##ww#w###
#########
0123456
Finally, the fourth droplet falls.
Since moving left would not eventually make it fall, it tries to move right.
Since moving right would not eventually make it fall, it stays in place:
# #
# w #
##ww#w###
#########
0123456
The final answer is [2,2,2,3,2,2,2]:
#
#######
#######
0123456
还有别的例子如下：
Input: heights = [1,2,3,4], V = 2, K = 2
Output: [2,3,3,4]
Explanation:
The last droplet settles at index 1, since moving further left would not cause it to eventually fall to a lower height.
Input: heights = [3,1,3], V = 5, K = 1
Output: [4,4,4]
但是在真实面试中的要求其实跟 leetcode 题目并不一样。首先会要求把 terrain 和 droplet 的形状打印出来，类似下面
# #
# #
##ww# ###
#########
需要写一个函数把上图画出来。
接下来就是跟leetcode题目要求一致了。但是水滴的流向等需求也有变换。有时候认为左右两边是无限高的墙，水滴碰到就停在那里。有时候是假设左右两边是无限大的深渊，水滴碰到就没了 - 掉到深渊里去了。
这题难度挺大，稍微一变种代码就得改动很大。
中心解题思路应该是找 valley。逻辑主要是怎么找到真正的valley，特别是碰到一段水平线的情况下，如下图:
\
\
\
---------------
\
\
\
-- <- valley
这题在做的过程中需要不断打印形状，验证逻辑正确。跟面试官对一些假设的交流也很重要。
Sliding Puzzle 这题 leetcode也有收录， 参考 https://leetcode.com/problems/sliding-puzzle/solution/
题目如下：
On a 2x3 board , there are 5 tiles represented by the integers 1 through 5, and an empty square represented by 0.
A move consists of choosing 0 and a 4-directionally adjacent number and swapping it.
The state of the board is solved if and only if the board is [[1,2,3],[4,5,0]].
Given a puzzle board, return the least number of moves required so that the state of the board is solved. If it is impossible for the state of the board to be solved, return -1.
Note:
-
heightswill have length in[1, 100]and contain integers in[0, 99]. -
Vwill be in range[0, 2000]. -
Kwill be in range[0, heights.length - 1].
例子：
Input: board = [[1,2,3],[4,0,5]]
Output: 1
Explanation: Swap the 0 and the 5 in one move.
Input: board = [[1,2,3],[5,4,0]]
Output: -1
Explanation: No number of moves will make the board solved.
Input: board = [[4,1,2],[5,0,3]]
Output: 5
Explanation: 5 is the smallest number of moves that solves the board.
An example path:
After move 0: [[4,1,2],[5,0,3]]
After move 1: [[4,1,2],[0,5,3]]
After move 2: [[0,1,2],[4,5,3]]
After move 3: [[1,0,2],[4,5,3]]
After move 4: [[1,2,0],[4,5,3]]
After move 5: [[1,2,3],[4,5,0]]
Input: board = [[3,2,4],[1,5,0]]
Output: 14
这题也是一样，需要写个函数把 puzzle 打印出来，这是leetcode 并没有要求的。有时候面试官会简化条件，默认是3 * 3的matrix。虽然这道题理论上应该用 A* Search 来做，这个算法我也研究过，但是不建议在面试中使用，因为面试官有的都不知道，而且可能表示你做过这题。用基本的 BFS 来做就可以了，虽然有可能这种做法会爆 - runtime 和 内存开销太大。 具体代码和思路，特别是OOD相关的，我会在 第七课：Airbnb 专题之OOD 中细讲，这里就不多说了。感兴趣的可以看下 OOD 与多线程 Udemy 课程 。
别的低频题有 airbnb电面
要猜出一四位数字，每位数字上是1到6。
提供一个API，返回有几个数字是对的（不考虑位置），以及考虑位置有几个数字是严格match的。
要求多次调用这个 API，返回这个数字究竟是多少。
例子：
# correct code: 3264
# GUESS 1111 => 0 0 (no correct digits)
# GUESS 1214 => 2 2 (digits 2 and 4 are correct and on correct position)
# GUESS 6111 => 1 0 (digit 6 is present, but on a different position)
# GUESS 6211 => 2 1 (digits 6 and 2 are present, only 2 is on correct position)
这题在onsite是挺高频的。很多人在研究算法，优化猜的次数。其实重点还在临时查找网上的socket programming 来编程，调用这个API。Airbnb起了个Server来提供这个API的。airbnb允许你自己去放狗搜，解决问题，这也是实际工作的能力考察。如果你network programming和TCP 编程很熟，那就不用查了。其实就是参考网上的例子改改。这步调通以后，才开始写算法部分。算法我就不具体讨论了。其实不需要非常优化，就不断枚举猜都行。这块并不是重点。
附送别的同学总结的2017深秋版（他家题目目前还没变）