Snowflake Interview Question: Min Distance Between Person and Cake

Problem Description

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

Problem Analysis

Given a 1D array with "Person (1)" and "Cake (2)", find the "Minimum Distance" between any person and any cake.

Solution 3: One Pass (Optimal)

def min_distance_one_pass(space):
    """
    Find minimum distance in one pass.
    
    Time Complexity: O(n)
    Space Complexity: 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

Solution 4: Dynamic Programming

def min_distance_dp(space):
    """
    Using DP.
    dp[i] = distance to nearest cake from index i.
    """
    n = len(space)
    
    # Left to right scan
    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 to left scan
    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
    
    # Find min distance
    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

Complexity Comparison

Summary

Snowflake Person-Cake Min Distance Problem covers:

1. Array Traversal: Basic array operations
2. Two Pointer Technique: Optimizing search process
3. Dynamic Programming: Precomputing distances
4. Edge Case Handling: Empty array, no person/cake scenarios

oavoservice specializes in interview coaching for Snowflake / Google / Amazon, offering OA support and real-time VO assistance. Contact us if you need help.

Need real interview questions? Contact WeChat Coding0201 immediately to get real questions.