題目描述
每個人都想吃一塊蛋糕。
人們傾向於獲取離自己最近的蛋糕。但是，如果發現該蛋糕已經屬於別人，這個人就會放棄該蛋糕，尋找下一個最近的蛋糕。
蛋糕的數量永遠不小於人數，所以保證每個人都能分到蛋糕。
假設你是空間中的人之一。給定陣列和你的位置，找出哪塊蛋糕屬於你。
範例：
1 0 2 0 2 0 M 0
M (我) 將獲得索引 4 的蛋糕。
問題分析
每個人都會去搶離自己最近的蛋糕。如果最近的蛋糕被別人佔了，就繼續找下一個最近的。因為蛋糕數量 ≥ 人數，所以每個人最終都能分到蛋糕。
題目給了你的位置，需要根據**「最近優先、衝突讓位」**的規則算出你最終會拿到哪個蛋糕。
解法實作
解法一：優先佇列（更高效）
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
複雜度分析
- 時間複雜度： O(P × C × log C)，其中 P 是人數， C 是蛋糕數
- 空間複雜度： O(P × C)
總結
Snowflake 蛋糕分配題考察點：
- 貪心演算法：最近優先策略
- 衝突解決：多人競爭同一資源
- 模擬過程：迭代分配直到穩定
- 穩定匹配：Gale-Shapley 演算法應用
oavoservice 專注於 Snowflake / Google / Amazon 等大廠面試輔導，提供 OA 代做、VO 即時輔助等服務。如需幫助，歡迎聯繫我們。
需要面試真題？ 立刻聯繫微信 Coding0201，獲得真題。