Greedy Person-Cake Matching Distance
Updated
Problem statement
You are given an integer array a. Each cell is empty (0), holds a person (1), or holds a cake (2). The distance between a person at index i and a cake at index j is |i - j|.
Hand out cakes greedily. While at least one unmatched person and one unmatched cake remain, find the unmatched person and unmatched cake that are closest to each other, give that cake to that person, and add their distance to a running total. Matched people and cakes take no further part.
Return the total distance. If there are no people or no cakes, return 0. The input guarantees that the closest pair is unique at every step, so the process is fully determined. The result is the greedy total, which can be larger than the smallest total any matching could achieve.
Function
greedyMatchingDistance(a: int[]) → longExamples
Example 1
a = [1,0,2,0,0,1,2]return = 3The people are at indices 0 and 5, the cakes at 2 and 6. The closest pair is the person at 5 and the cake at 6, distance 1. The only pair left is 0 and 2, distance 2. The total is 3.
Example 2
a = [1,0,0,2,1,0,0,0,0,2]return = 10The closest pair is the person at 4 and the cake at 3, distance 1. That leaves the person at 0 and the cake at 9, distance 9, so the greedy total is 10. Pairing 0 with 3 and 4 with 9 would cost only 8, but the rule asks for the greedy result, not the smallest possible total.
Example 3
a = [2,2,1]return = 1The person at 2 is closest to the cake at 1 (distance 1). After that no person is left, so the cake at 0 stays unmatched. The total is 1.
Constraints
1 <= a.length <= 10^5a[i]is0,1, or2- At every step of the process, exactly one person-cake pair has the smallest distance.
More Snowflake Phone Screen questions
- Connect Four from the Last MovePHONE SCREEN · Seen Nov 2026
- Minimum Edits to a Perfect Binary TreePHONE SCREEN · Seen Nov 2026
- Configurable Per-Client Token BucketsPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Find Valid SET Card TriplesOA · PHONE SCREEN · Seen Nov 2026
- Minimum Index Distance Between Person and CakeOA · PHONE SCREEN · Seen Nov 2026
- Minimum N-ary Tree Depth DeletionsOA · PHONE SCREEN · Seen Nov 2026
- Sum of Binary Tree Boundary NodesOA · PHONE SCREEN · Seen Nov 2026
- Tree Height After Child PromotionPHONE SCREEN · Seen Oct 2026
- Minimum StackPHONE SCREEN · Seen Oct 2026
- Reverse a String with Two PointersPHONE SCREEN · Seen Oct 2026
Similar questions at other companies
- IPOTekion · PHONE SCREENTekion interview questions
- IPOInMobi · PHONE SCREENInMobi interview questions
- Lexicographically Smallest Array with K-Limited Right MovesGoogle · PHONE SCREENGoogle interview questions
- Minimum Refueling StopsBloomberg LP · PHONE SCREENBloomberg LP interview questions
- Tennis Court SchedulingAtlassian · PHONE SCREEN · ONSITE INTERVIEWAtlassian interview questions
- Maximum Number of Events That Can Be AttendedByteDance · PHONE SCREENByteDance interview questions
- Defer Expenses to Preserve BalanceDRW · PHONE SCREENDRW interview questions
- Minimize Array Sum After K Halving OperationsDocuSign · PHONE SCREENDocuSign interview questions
- Automation Pipeline, Part 3: Stage DurationPlaid · PHONE SCREENPlaid interview questions
- Minimum Sum After K Ceiling HalvingsAdobe · PHONE SCREENAdobe interview questions