How should I practice Deepest Common Ancestors in a Multi-Parent DAG?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Salesforce onsite interview problems in FastPrep.

Is Deepest Common Ancestors in a Multi-Parent DAG associated with Salesforce?

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

Problem · Graph

Deepest Common Ancestors in a Multi-Parent DAG

Learn this problem

● Hard

SalesforceFULLTIMEONSITE INTERVIEW

See Salesforce hiring insights

Problem statement

The graph has nodes numbered from 0 through nodeCount - 1. Every pair [parent, child] in edges is a directed edge from an ancestor toward a descendant.

A node is an ancestor of itself. The depth of a node is the maximum number of edges on any path from a zero-indegree root to that node.

Return every node that is an ancestor of both first and second and has maximum depth among their common ancestors. Return the node IDs in ascending order. Return an empty array when there is no common ancestor.

Function

deepestCommonAncestors(nodeCount: int, edges: int[][], first: int, second: int) → int[]

Examples

Example 1

nodeCount = 5edges = [[0,2],[1,2],[2,3],[2,4]]first = 3second = 4return = [2]

Nodes 0, 1, and 2 are common ancestors. Node 2 has the greatest depth.

Example 2

nodeCount = 6edges = [[0,2],[1,3],[2,4],[3,4],[2,5],[3,5]]first = 4second = 5return = [2,3]

Nodes 2 and 3 are incomparable common ancestors at the same maximum depth, so both are returned.

Constraints

1 <= nodeCount <= 100000.
0 <= edges.length <= 200000.
Every edge contains two valid, distinct node IDs.
The graph contains no directed cycle.
first and second are valid node IDs.