# Snowflake 面试题：在一维空间中分配蛋糕，确定你最终拿到哪块蛋糕
题目描述
Each person wants to eat one cake.
People tend to get the cake that is the closest to him/her. However, if he/she finds that this cake already belongs to someone else, the person will give up that cake and look for the next closest cake.
The number of cakes is never smaller than the number of people, so everyone is guaranteed to get a cake.
Suppose you are one of the people in the space. Given the array and your position, find out which cake belongs to you.
Example:
1 0 2 0 2 0 M 0
M (me) will get the cake at index 4.
问题分析
每个人都会去抢离自己最近的蛋糕。如果最近的蛋糕被别人占了，就继续找下一个最近的。因为蛋糕数量 ≥ 人数，所以每个人最终都能分到蛋糕。
题目给了你的位置，需要根据**"最近优先、冲突让位"**的规则算出你最终会拿到哪个蛋糕。
核心规则：
- 每个人优先选择离自己最近的蛋糕
- 如果多人选择同一个蛋糕，距离更近的人获得
- 失败的人继续选择次近的蛋糕
- 重复直到所有人都分配到蛋糕
解法实现
解法一：贪心 + 模拟
def find_my_cake(space, my_position):
"""
找出我最终会拿到哪个蛋糕
Args:
space: 一维数组，1=人，2=蛋糕，0=空位，'M'=我
my_position: 我的位置索引
Returns:
我拿到的蛋糕的索引
"""
n = len(space)
# 1. 找出所有人和蛋糕的位置
people = []
cakes = []
for i in range(n):
if space[i] == 1:
people.append(i)
elif space[i] == 2:
cakes.append(i)
elif space[i] == 'M':
people.append(i)
# 2. 为每个人计算到所有蛋糕的距离，并排序
person_preferences = []
for person_pos in people:
distances = []
for cake_pos in cakes:
dist = abs(person_pos - cake_pos)
distances.append((dist, cake_pos, person_pos))
distances.sort() # 按距离排序
person_preferences.append(distances)
# 3. 模拟分配过程
allocated = {} # cake_pos -> person_pos
while len(allocated) < len(people):
# 每个人尝试选择自己最近的未分配蛋糕
for i, person_pos in enumerate(people):
if person_pos in allocated.values():
continue # 已经分配到蛋糕
# 找到最近的未分配蛋糕
for dist, cake_pos, _ in person_preferences[i]:
if cake_pos not in allocated:
# 检查是否有其他人也想要这个蛋糕且距离更近
conflict = False
for j, other_pos in enumerate(people):
if other_pos == person_pos or other_pos in allocated.values():
continue
# 检查其他人到这个蛋糕的距离
other_dist = abs(other_pos - cake_pos)
my_dist = abs(person_pos - cake_pos)
if other_dist < my_dist:
conflict = True
break
if not conflict:
allocated[cake_pos] = person_pos
break
# 4. 返回我的蛋糕
for cake_pos, person_pos in allocated.items():
if person_pos == my_position:
return cake_pos
return -1 # 不应该到达这里
解法二：优先队列（更高效）
import heapq
def find_my_cake_optimized(space, my_position):
"""
使用优先队列优化的版本
"""
n = len(space)
# 找出所有人和蛋糕
people = []
cakes = []
for i in range(n):
if space[i] == 1 or space[i] == 'M':
people.append(i)
elif space[i] == 2:
cakes.append(i)
# 为每个蛋糕建立优先队列（距离，人的位置）
cake_queues = {cake: [] for cake in cakes}
for person in people:
for cake in cakes:
dist = abs(person - cake)
heapq.heappush(cake_queues[cake], (dist, person))
# 分配蛋糕
allocated = {}
assigned_people = set()
while len(assigned_people) < len(people):
# 找出每个蛋糕的最近候选人
for cake in cakes:
if cake in allocated:
continue
while cake_queues[cake]:
dist, person = heapq.heappop(cake_queues[cake])
if person not in assigned_people:
# 检查这个人是否有更近的蛋糕
has_closer = False
for other_cake in cakes:
if other_cake == cake or other_cake in allocated:
continue
if abs(person - other_cake) < dist:
has_closer = True
break
if not has_closer:
allocated[cake] = person
assigned_people.add(person)
break
# 返回我的蛋糕
for cake, person in allocated.items():
if person == my_position:
return cake
return -1
解法三：稳定匹配（Gale-Shapley 算法变体）
def find_my_cake_stable_matching(space, my_position):
"""
使用稳定匹配算法
"""
n = len(space)
# 找出所有人和蛋糕
people = []
cakes = []
for i in range(n):
if space[i] == 1 or space[i] == 'M':
people.append(i)
elif space[i] == 2:
cakes.append(i)
# 每个人的偏好列表（按距离排序）
person_prefs = {}
for person in people:
prefs = sorted(cakes, key=lambda c: abs(person - c))
person_prefs[person] = prefs
# 每个蛋糕的偏好列表（按距离排序）
cake_prefs = {}
for cake in cakes:
prefs = sorted(people, key=lambda p: abs(cake - p))
cake_prefs[cake] = prefs
# 稳定匹配算法
free_people = set(people)
person_next = {p: 0 for p in people} # 每个人下一个要尝试的蛋糕索引
cake_partner = {} # 蛋糕当前的配对
while free_people:
person = free_people.pop()
if person_next[person] >= len(person_prefs[person]):
continue
cake = person_prefs[person][person_next[person]]
person_next[person] += 1
if cake not in cake_partner:
# 蛋糕未分配
cake_partner[cake] = person
else:
# 蛋糕已分配，比较距离
current_partner = cake_partner[cake]
current_dist = abs(cake - current_partner)
new_dist = abs(cake - person)
if new_dist < current_dist:
# 新的人更近，替换
cake_partner[cake] = person
free_people.add(current_partner)
else:
# 保持原配对
free_people.add(person)
# 返回我的蛋糕
for cake, person in cake_partner.items():
if person == my_position:
return cake
return -1
测试用例
# Test 1
space1 = [1, 0, 2, 0, 2, 0, 'M', 0]
my_pos1 = 6
print(find_my_cake(space1, my_pos1)) # 输出: 4
# Test 2: 我最近的蛋糕被抢了
space2 = [1, 2, 'M', 2, 0]
my_pos2 = 2
print(find_my_cake(space2, my_pos2)) # 输出: 3
# Test 3: 多人竞争
space3 = [1, 1, 2, 'M', 2, 1]
my_pos3 = 3
print(find_my_cake(space3, my_pos3)) # 输出: 4
复杂度分析
- 时间复杂度： O(P × C × log C)，其中 P 是人数，C 是蛋糕数
- 空间复杂度： O(P × C)
优化技巧
- 提前排序：预先计算每个人到所有蛋糕的距离
- 剪枝：如果某个蛋糕已经被更近的人占据，跳过
- 缓存：记录已分配的蛋糕，避免重复检查
总结
Snowflake 蛋糕分配题考察点：
- 贪心算法：最近优先策略
- 冲突解决：多人竞争同一资源
- 模拟过程：迭代分配直到稳定
- 稳定匹配：Gale-Shapley 算法应用
oavoservice 专注于 Snowflake / Google / Amazon 等大厂面试辅导，提供 OA 代做、VO 实时辅助等服务。如需帮助，欢迎联系我们。
需要面试真题？ 立刻联系微信 Coding0201，获得真题。