Software Engineer · Full Journey · Coding

Snowflake — Software Engineer ✅ Passed

Level: Unknown Level

Round: Full Journey · Type: Coding · Difficulty: 7/10 · Duration: 120 min · Interviewer: Neutral

Topics: Arrays, Dynamic Programming

Location: San Francisco Bay Area

Interview date: 2025-12-28

Summary

Round 1: Nearest Cake Distance

Question: Given a binary array and a starting index, find the shortest distance to the nearest cake (1) from the starting position. What is the time and space complexity?

---

Round 2: Global Matching

Question: Given an array containing persons (1) and cakes (2), pair each person with a unique cake to minimize the total distance. If there are more persons than cakes, return an error. Return the index of the cake assigned to a specific person in the optimal scenario. What is the time and space complexity?

Details

Task 1: Nearest Cake Distance

I was given a binary array A and a starting index start. My task was to return the shortest distance from the start position to any cake (represented by 1). If no cakes were present, I had to return -1.

I used a two-pointer approach, searching left and right from the starting position until I found a cake in either direction. I then calculated the distances and returned the minimum.

The provided code was:

` def nearest_cake_distance(A: list[int], start: int) -> int: n = len(A) # Check if start index is valid if start < 0 or start >= n: raise ValueError("start out of range")

# Search to the left
left = start
while left >= 0 and A[left] != 1:
    left -= 1

# Search to the right
right = start
while right < n and A[right] != 1:
    right += 1

best = float("inf")

# Calculate distance if a cake was found on the left
if left >= 0:
    best = min(best, start - left)
    
# Calculate distance if a cake was found on the right
if right < n:
    best = min(best, right - start)

return -1 if best == float("inf") else int(best)

`

The time complexity is O(n) in the worst case, where n is the length of the array. The space complexity is O(1).

Task 2: Global Matching

In the second part, the input array contained persons (1) and cakes (2). I needed to pair each person with a unique cake to minimize the total distance, raising an error if there were more persons than cakes. I also had to return the index of the assigned cake for a specific person in this optimal scenario.

The key was that I couldn't simply pick the nearest cake for each person individually. I needed to look at the global picture and use dynamic programming (DP) to ensure an optimal matching.

The provided code was:

` def assign_cakes_globally(line: list[int]) -> dict[int, int]: persons = [i for i, v in enumerate(line) if v == 1] cakes = [i for i, v in enumerate(line) if v == 2]

p = len(persons)
c = len(cakes)

if p == 0:
    return {}
if p > c:
    raise ValueError("impossible: fewer cakes than persons")

INF = 10**18
# dp[i][j] stores min cost to match i persons using first j cakes
dp = [[INF] * (c + 1) for _ in range(p + 1)]
# take[i][j] stores whether we used cake j for person i
take = [[False] * (c + 1) for _ in range(p + 1)]

# Base case: 0 cost to match 0 persons
for j in range(c + 1):
    dp[0][j] = 0

for i in range(1, p + 1):
    for j in range(1, c + 1):
        # Choice 1: Skip the current cake (j-1)
        best = dp[i][j - 1]
        choose_take = False

        # Choice 2: Pair person i-1 with cake j-1
        cand = dp[i - 1][j - 1] + abs(persons[i - 1] - cakes[j - 1])
        if cand < best:
            best = cand
            choose_take = True

        dp[i][j] = best
        take[i][j] = choose_take

# Reconstruct the assignment map by backtracking
assignment: dict[int, int] = {}
i, j = p, c
while i > 0 and j > 0:
    if take[i][j]:
        # We used cake j-1 for person i-1
        assignment[persons[i - 1]] = cakes[j - 1]
        i -= 1
        j -= 1
    else:
        # We skipped cake j-1
        j -= 1

if i != 0:
    raise RuntimeError("reconstruction failed")

return assignment

def assigned_cake_for_person(line: list[int], person_index: int) -> int: assignment = assign_cakes_globally(line) if person_index not in assignment: raise ValueError("person index not found in input") return assignment[person_index] `

Let P be the number of persons and C be the number of cakes. The time complexity is O(P * C) and the space complexity is O(P * C) due to the DP table.