Snowflake 面試題：一維陣列中「人」和「蛋糕」的最小距離

題目描述

Given a 1-d space, represented as an int array. Each element in this array can have one of the three values {0, 1, 2} with meanings:

• 0 — space is empty
• 1 — there is a person at this space
• 2 — there is a cake at this space

The distance between a cake and a person is defined as the number of spaces between them.

Please write a method to get the minimum distance between any person and any cake in the space.

範例：

1 0 2 0 0

答案：1

問題分析

給你一個一維陣列，裡面有**「人 (1)」和「蛋糕 (2)」。要求找到任意一個人和任意一個蛋糕之間的「最小距離」**。

解法三：一次遍歷（最優）

def min_distance_one_pass(space):
    """
    一次遍歷找最小距離
    
    時間複雜度：O(n)
    空間複雜度：O(1)
    """
    min_dist = float('inf')
    last_person = -1
    last_cake = -1
    
    for i in range(len(space)):
        if space[i] == 1:
            last_person = i
            if last_cake != -1:
                min_dist = min(min_dist, abs(last_person - last_cake))
        
        elif space[i] == 2:
            last_cake = i
            if last_person != -1:
                min_dist = min(min_dist, abs(last_person - last_cake))
    
    return min_dist if min_dist != float('inf') else -1

解法四：動態規劃

def min_distance_dp(space):
    """
    使用動態規劃
    
    dp[i] = 從位置 i 到最近蛋糕的距離
    """
    n = len(space)
    
    # 從左到右掃描
    left_dist = [float('inf')] * n
    last_cake = -1
    
    for i in range(n):
        if space[i] == 2:
            last_cake = i
        if last_cake != -1:
            left_dist[i] = i - last_cake
    
    # 從右到左掃描
    right_dist = [float('inf')] * n
    last_cake = -1
    
    for i in range(n - 1, -1, -1):
        if space[i] == 2:
            last_cake = i
        if last_cake != -1:
            right_dist[i] = last_cake - i
    
    # 找最小距離
    min_dist = float('inf')
    for i in range(n):
        if space[i] == 1:
            dist = min(left_dist[i], right_dist[i])
            min_dist = min(min_dist, dist)
    
    return min_dist if min_dist != float('inf') else -1

複雜度對比

總結

Snowflake 人-蛋糕最小距離題考察點：

1. 陣列遍歷：基礎的陣列操作
2. 雙指標技巧：優化查找過程
3. 動態規劃：預處理距離資訊
4. 邊界處理：空陣列、無人/無蛋糕等情況

oavoservice 專注於 Snowflake / Google / Amazon 等大廠面試輔導，提供 OA 代做、VO 即時輔助等服務。如需幫助，歡迎聯繫我們。

需要面試真題？ 立刻聯繫微信 Coding0201，獲得真題。