# 一道泄露并遭禁用的谷歌面试题，背后玄机全解析

• 它很容易表述和理解。
• 它有很多解决方案，每个解决方案都要求不同程度的算法和数据结构知识。
• 每个解决方案都可以通过相对较少的代码行来实现，非常适合用在时间紧凑的面试场景中。

## 讨论

• 6–1–8
• 6–1–6
• 6–7–2
• 6–7–6
• 6–0–4
• 6–0–6

### 第 0 级：下一跳

``````def neighbors(position):
...
``````

``````NEIGHBORS_MAP = {
1: (6, 8),
2: (7, 9),
3: (4, 8),
4: (3, 9, 0),
5: tuple(),  # 5 没有邻居
6: (1, 7, 0),
7: (2, 6),
8: (1, 3),
9: (2, 4),
0: (4, 6),
}
def neighbors(position):
return NEIGHBORS_MAP[position]
``````

### 第 1 级：递归生成号码

``````def yield_sequences(starting_position, num_hops, sequence=None):
if sequence is None:
sequence = [starting_position]

if num_hops == 0:
yield sequence
return

for neighbor in neighbors(starting_position):
yield from yield_sequences(
neighbor, num_hops - 1, sequence + [neighbor])

def count_sequences(starting_position, num_hops):
num_sequences = 0
for sequence in yield_sequences(starting_position, num_hops):
num_sequences += 1
return num_sequences
``````

``````from neighbors import neighbors

def count_sequences(start_position, num_hops):
if num_hops == 0:
return 1

num_sequences = 0
for position in neighbors(start_position):
num_sequences += count_sequences(position, num_hops - 1)
return num_sequences

if __name__ == '__main__':
print(count_sequences(6, 2))
``````

### 第 3 级：memoization

``````def count_sequences(start_position, num_hops):
cache = {}

def helper(position, num_hops):
if (position, num_hops) in cache:
return cache[ (position, num_hops) ]

if num_hops == 0:
return 1

else:
num_sequences = 0
for neighbor in neighbors(position):
num_sequences += helper(neighbor, num_hops - 1)
cache[ (position, num_hops) ] = num_sequences
return num_sequences

res = helper(start_position, num_hops)
return res
``````

### 第 4 级：动态规划

``````def count_sequences(start_position, num_hops):
prior_case = [1] * 10
current_case = [0] * 10
current_num_hops = 1

while current_num_hops <= num_hops:
current_case = [0] * 10
current_num_hops += 1

for position in range(0, 10):
for neighbor in neighbors(position):
current_case[position] += prior_case[neighbor]
prior_case = current_case

return current_case[start_position]
``````

## 总结

• 先手动解决小规模问题。对于这个面试题，当你手动画出函数调用结构时，递归关系和重复的函数调用就变得更加明显。
• 注意不要计算不需要用到的东西，例如那个初级解决方案生成号码，但实际上用不到它们。减少不必要的计算通常可以提供更简单的解决方案。
• 了解递归。递归在大多数生产代码中几乎是没有用的，因为它可能会爆栈，但却是一种非常强大的算法设计策略。递归解决方案通常可以进行调整和改进：指数级复杂度解决方案与线性最优 memoization 解决方案之间的差异其实是最小的。
• 了解 Big-O！在面试过程中，你很有可能会在某个时间点被问到这个问题。
• 总是想方设法找到 memoization 解决方案。如果你的函数是确定性的，并且会使用相同的输入多次调用它，那么可能可以从 memoization 解决方案中受益。
• 查找并写出递归关系。对于这个面试题，把递归关系写出来，就可以发现 N 跳的计数只取决于 N-1 跳的计数。

2 Likes