How should I practice Minimum Distance Matching in a Forest?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Scale AI phone screen and onsite interview problems in FastPrep.

Is Minimum Distance Matching in a Forest associated with Scale AI?

FastPrep tags this as a Scale AI phone screen and onsite interview coding practice problem when the problem catalog has that company and stage context.

Minimum Distance Matching in a Forest

Scale AI● HardNEW GRADPHONE SCREENONSITE INTERVIEW

Learn

Problem statement

edges describes an undirected forest with uniquely labeled integer nodes. Match every label in left to a distinct label in right.

The cost of a pair is the number of forest edges on their path. Nodes in different trees cannot be paired. right may contain extra labels that remain unused.

Return the minimum total distance of a valid one-to-one matching, or -1 when no matching covers every label in left.

Function

minimumForestMatchingDistance(edges: int[][], left: int[], right: int[]) → int

Examples

Example 1

edges = [[1,2],[2,3],[2,4],[5,6]]left = [1,3]right = [4,2]return = 3

Either pairing has total distance 3.

Example 2

edges = [[1,2],[3,4]]left = [1,3]right = [4,2]return = 2

Pair 1 with 2 and 3 with 4; the right-array order need not be preserved.

Example 3

edges = [[1,2],[3,4]]left = [1,2]right = [3,4]return = -1

Every possible pair crosses disconnected trees.

Constraints

1 <= edges.length <= 200000.
The graph is an undirected forest with no duplicate edge.
Every query label appears in at least one edge.
1 <= left.length <= right.length <= 12.
Labels within each query array are unique.