Snowflake 面试题：一维数组中人和蛋糕的最小距离（含题目解析）

# 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.

Example:

1 0 2 0 0

Answer: 1

问题分析

给你一个一维数组，里面有**"人 (1)"和"蛋糕 (2)"。要求找到任意一个人和任意一个蛋糕之间的"最小距离"**。

做法就是找出所有 1 和 2 的索引，然后算它们之间的最小绝对差值即可。

解法一：暴力枚举

def min_distance_brute_force(space):
    """
    暴力枚举所有人和蛋糕的距离
    
    时间复杂度：O(P × C)，P 是人数，C 是蛋糕数
    空间复杂度：O(P + C)
    """
    people = []
    cakes = []
    
    # 1. 收集所有人和蛋糕的位置
    for i in range(len(space)):
        if space[i] == 1:
            people.append(i)
        elif space[i] == 2:
            cakes.append(i)
    
    # 2. 计算最小距离
    min_dist = float('inf')
    for person in people:
        for cake in cakes:
            dist = abs(person - cake)
            min_dist = min(min_dist, dist)
    
    return min_dist if min_dist != float('inf') else -1

解法二：双指针（优化版）

def min_distance_two_pointers(space):
    """
    使用双指针优化
    
    时间复杂度：O(n)
    空间复杂度：O(P + C)
    """
    people = []
    cakes = []
    
    for i in range(len(space)):
        if space[i] == 1:
            people.append(i)
        elif space[i] == 2:
            cakes.append(i)
    
    if not people or not cakes:
        return -1
    
    # 双指针遍历
    min_dist = float('inf')
    i, j = 0, 0
    
    while i < len(people) and j < len(cakes):
        dist = abs(people[i] - cakes[j])
        min_dist = min(min_dist, dist)
        
        # 移动较小的指针
        if people[i] < cakes[j]:
            i += 1
        else:
            j += 1
    
    return min_dist

解法三：一次遍历（最优）

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

测试用例

# Test 1: 基本情况
space1 = [1, 0, 2, 0, 0]
print(min_distance_one_pass(space1))  # 输出: 1

# Test 2: 多个人和蛋糕
space2 = [1, 0, 1, 2, 0, 2, 1]
print(min_distance_one_pass(space2))  # 输出: 1

# Test 3: 人和蛋糕相邻
space3 = [1, 2, 0, 0]
print(min_distance_one_pass(space3))  # 输出: 0

# Test 4: 只有人或只有蛋糕
space4 = [1, 0, 1, 0, 1]
print(min_distance_one_pass(space4))  # 输出: -1

# Test 5: 空数组
space5 = []
print(min_distance_one_pass(space5))  # 输出: -1

扩展问题

1. 找出所有人到最近蛋糕的距离

def all_person_distances(space):
    """
    返回每个人到最近蛋糕的距离
    """
    n = len(space)
    people = []
    cakes = []
    
    for i in range(n):
        if space[i] == 1:
            people.append(i)
        elif space[i] == 2:
            cakes.append(i)
    
    result = []
    for person in people:
        min_dist = min(abs(person - cake) for cake in cakes)
        result.append(min_dist)
    
    return result

2. 找出距离最近的人-蛋糕对

def find_closest_pair(space):
    """
    返回距离最近的人和蛋糕的位置
    """
    people = []
    cakes = []
    
    for i in range(len(space)):
        if space[i] == 1:
            people.append(i)
        elif space[i] == 2:
            cakes.append(i)
    
    min_dist = float('inf')
    closest_pair = None
    
    for person in people:
        for cake in cakes:
            dist = abs(person - cake)
            if dist < min_dist:
                min_dist = dist
                closest_pair = (person, cake)
    
    return closest_pair, min_dist

3. 二维版本

def min_distance_2d(grid):
    """
    二维网格中人和蛋糕的最小曼哈顿距离
    """
    m, n = len(grid), len(grid[0])
    people = []
    cakes = []
    
    for i in range(m):
        for j in range(n):
            if grid[i][j] == 1:
                people.append((i, j))
            elif grid[i][j] == 2:
                cakes.append((i, j))
    
    min_dist = float('inf')
    for px, py in people:
        for cx, cy in cakes:
            dist = abs(px - cx) + abs(py - cy)
            min_dist = min(min_dist, dist)
    
    return min_dist

复杂度对比

优化技巧

1. 提前终止：如果找到距离为 0，直接返回
2. 缓存结果：如果多次查询，可以预处理
3. 二分查找：如果位置已排序，可以用二分查找优化

总结

Snowflake 人-蛋糕最小距离题考察点：

1. 数组遍历：基础的数组操作
2. 双指针技巧：优化查找过程
3. 动态规划：预处理距离信息
4. 边界处理：空数组、无人/无蛋糕等情况

oavoservice 专注于 Snowflake / Google / Amazon 等大厂面试辅导，提供 OA 代做、VO 实时辅助等服务。如需帮助，欢迎联系我们。

需要面试真题？ 立刻联系微信 Coding0201，获得真题。