Finding the Closest Cake and Optimal Matching ## Introduction to the Challenge You are given a list (array) representing a line. In

Task 1: * 0 represents an empty spot. * 1 represents a cak

Finding the Closest Cake and Optimal Matching ## Introduction to the Challenge You are given a list (array) representing a line. In

Task 1: * 0 represents an empty spot. * 1 represents a cake. In

Task 2: * 0 represents an empty spot. * 1 represents a person. * 2 represents a cake. There are two parts to this interview: 1. Find the distance to the nearest cake for a specific person. 2. Pair every person with a unique cake so the total distance for everyone is as small as possible. --- ## Task 1: Nearest Cake Distance ### Requirement You are given: * A: A binary array (1 is a cake, 0 is not). * start: The index where a person is standing. You must return the shortest distance from the start position to any cake. If there are no cakes in the entire array,

return -1.

Sample Input and Output

python A = [0, 0, 1, 0, 0, 1, 0] start = 0

Output:

python 2

Explanation: The closest cake is at index 2. The distance is 2 - 0 = 2.

Solution Code (Part 1)

python 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)

Performance Analysis | Metric | Complexity | | --- | --- | | Time | O(n) worst-case | | Space | O(1) | --- ## Task 2: Global Matching ### Requirement Now the input array contains both persons and cakes: * 1 = person * 2 = cake * 0 = empty You must pair each person with exactly one unique cake. The goal is to make the sum of distances for all pairs as small as possible.

Rules: 1. Minimize the total distance sum. 2. If there are more persons than cakes,

return an error (impossible). 3. If asked about a specific person,

return the index of the cake assigned to them in this best-case scenario.

Note: You cannot simply pick the nearest cake for each person individually. One person's choice might force someone else to walk much further, increasing the total cost. You must look at the global picture.

Sample Scenario

python line = [1, 2, 0, 1, 0, 0, 2] # Persons are at indices [0, 3] # Cakes are at indices [1, 6]

Individual Nearest Choices: * Person 0 wants Cake 1 (Distance 1). * Person 3 also wants Cake 1 (Distance 2). They cannot both have Cake 1.

Global Optimal Assignment: * Person 0 takes Cake 1 (Distance 1). * Person 3 takes Cake 6 (Distance 3).

Total Distance: 1 + 3 = 4. If you query for Person 3, the correct answer is Cake 6, even though Cake 1 is closer.

Solution

Approach (Part 2) We use Dynamic Programming (DP) to solve this. First, we collect the indices of all persons and cakes. Because we scan the array once, these lists are naturally sorted. *

State: dp[i][j] represents the minimum total distance to pair the first i persons using a subset of the first j cakes. *

Choices: For every step, we decide between: 1.

Skip: Do not use cake j. We keep the cost from dp[i][j-1]. 2.

Take: Pair person i with cake j. We add the distance abs(person_i - cake_j) to the previous cost dp[i-1][j-1]. After filling the table, we backtrack to find exactly which cake was assigned to which person.

Solution Code (Part 2)

python 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]

Performance Analysis Let P be the number of persons and C be the number of cakes. | Metric | Complexity | | --- | --- | | Time | O(P * C) | | Space | O(P * C) | ### Key Takeaways * If you need to answer many questions for the same input array, run the logic once. Store the result in a HashMap (dictionary) so you can answer each query in O(1). * If Part 1 only asks for the distance (and does not require Global Optimization), the simple two-pointer scan is sufficient and faster.