Airbnb 高频题目总结和分析

Airbnb 的面试跟很多独角兽公司（比如snapchat，uber）一样，不仅仅是把代码写出来，要求编译通过，并且可以跑通。这样其实对debug的能力有不小要求，Java的话可以用 System.out.println() 来debug。别的语言就是用自己的print 函数啦。

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:

1. `heights` will have length in `[1, 100]` and contain integers in `[0, 99]` .
2. `V` will be in range `[0, 2000]` .
3. `K` will 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

#
#######
#######
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]
``````

``````#       #
#       #
##ww# ###
#########
``````

``````\
\
\
---------------
\
\
\
--    <- 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:

1. `heights` will have length in `[1, 100]` and contain integers in `[0, 99]` .
2. `V` will be in range `[0, 2000]` .
3. `K` will 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
``````

``````# 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)
``````

3 Likes

Airbnb起了个Server来提供这个API的。

2019 题目统计: 统计298题，数据取自2017到今年1月全部面经，共计33类型的题目，可以分为5档，频率从高到底往下排

(46) 15.4% 倒水 (1. 没有高墙 2. 打印倒水前后情况)

(46) 15.4% 所有有向图找最大最小问题(cheapest flights/10 wizards/滑雪/nodes最大得分/换着方式问) (1. 找出路径 2. 一题多解 BFS+剪枝，DFS+剪枝，Dijkstra，DP)

(40) 13.4% file system (1. implement watch function 2. Trie or HashTable)

(27) 9.1% alien dictionary (1. how to solve with DFS 2. 如何找出所有可能方案 3. What if has cycle)

(16) 5.4% sliding puzzle (1. OOP 定义board, shuffle 2. can solve/solve 3. 优化)

(13) 4.4% Palindrome Pairs (1. 先写isPanlindrome热身)

(12) 4% find the median in large file

(12) 4% 2D list iterator (1. remove 2. 如果有多层嵌套怎么处理)

(11) 3.7% menu combination/prices sum to k (1. 菜品可以/不可以重复，每个菜选一次/多次 2. 注意double精度问题)

(11) 3.7% IP to CIDR (1. 题目不难但是很难解释)

(9) 3% Boggle game (1. 直接两层DFS + Trie求解，先把代码写出来再说 2. 如果可以斜着走)

(9) 3% guess number

(7) 2.3% queue using fixed size array(1. 实现pop)

(7) 2.3% wiggle sort 2 (1. quick select find median就可以，不需要spaceO(1))

(6) 2% travel buddy

(5) 1.7% display page

(4) 1.3% Collatz Conjecture(1. iterative and recursion 2. hashmap来优化)

(4) 1.3% Minimum Vertices to Traverse Directed Grap

(2) 0.7% employee interval

(2) 0.7% csv parser (移动到OA)

(2) 0.7 % bank system

(2) 0.7% Board Score(*新题 皇冠题，每个点开始DFS计算得分，类似于Number of Island)

(2) 0.7% Maximum Number a Night You Can Accommodate(house robber)/Interval Schedule Profit (带间隔的DP问题)

(2) 0.3% flip tile(*新题，类似于shut the box)

(0) 0% Calculator

(0) 0% Regular Expression

(0) 0% Hilbert Curve

(0) 0% Simulate Diplomacy

(0) 0% Finding Ocean

(0) 0% K Edit Distance

(0) 0% String Pyramids Transition Matrix

(0) 0% Number of Intersected Rectangle

(0) 0% echo TCP client

2. 和面试官讨论清楚题目和假设，给出解题的思维过程, 写完后给几组test，分析复杂度

3. 代码干净，逻辑清晰