Oracle Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: In-Person
good approach, but do you really have to visit all the nodes up to Adan and Eve? I think It will be only if you fall in the worse case scenario.
What about alternately visit parents for You and Einstein until you get a visited node ?
What could be the special cases ( weirdo relationship in history) ?
Is this a Creationist model (Adam / Eve) or an Evolutionary model (First humans were descendants of apes)? :P
Either way, perhaps Iterative Deepening Search would be appropriate for this problem?
This would be done by having two independent searches (running in parallel or sequentially while alternating) marking each visited node and checking in each last level of every iteration whether there are any nodes marked, for such, you've discovered all the first common ancestors of two given nodes.
Interesting test cases would be:
- There is Inbreeding in the genealogy tree of one person.
- Two persons are actually the same one.
- Two persons have only one first common ancestor
- Two persons have multiple first common ancestors.
- One person is the first common ancestor of the other.
- There is no first common ancestor (in an Evolutionary model).
Adam and Eve are the only nodes in directed acyclic graph (DAG) with in-degree zero. Start from 'you' or Einstein, follow the child to parent pointers in a dfs like manner. Eventually you will find the special nodes 'Adam' and 'Eve'. Now run another dfs starting with 'Adam'/'Eve', this time following parent to child pointers. The first node for which one of it's child reports having you in it's sub-tree, and another child reports having Einstein in sub-tree, is "a" first common ancestor. This is where it gets complicated because of a lack of "first common ancestor" definition (partly because of possible weirdo relationships in the history). There could be multiple candidates in a DAG unlike trees.
- lasthope November 19, 2013