Clarify and Find Common Ancestors in a Graph
RipplingSoftware Engineer · Technical Screen
Last updated
Reason about graph common ancestors by clarifying edge direction, DAG versus tree structure, self-ancestry, output semantics, and reachability algorithms.
Explain how you would find common ancestors in a graph. Begin by clarifying the edge direction, graph structure, queried vertices, and whether the result should contain every common ancestor or only a nearest or lowest one.
Constraints
The graph representation, acyclicity, number of parents, self-ancestor convention, and output rule are unspecified. Do not silently turn the task into a binary-tree lowest-common-ancestor problem. Use a clearly labeled hypothetical interpretation to explain an algorithm, then discuss how a different output rule changes it.
Clarifying Questions
- Do edges point from parent to child, and can a vertex have several parents?
- Is the graph a tree, a directed acyclic graph, or a general directed graph?
- Is a queried vertex its own ancestor?
- Are we returning all common ancestors, a Boolean, or one or more lowest ancestors?
Hints
Hint 1
Reverse the reachability direction: When edges point from parent to child, walking incoming edges from a queried vertex reveals its ancestors.
Follow-up questions
- How would repeated queries on an unchanged graph affect preprocessing choices?
- Can two vertices in a DAG have several incomparable lowest common ancestors?
Solution walkthrough is for members
Get the full walkthrough with reference code and complexity analysis, plus Kitty Coach at 300 messages a day. Hints, the code runner and community answers stay free.