interview questions shared by candidates
You have a genealogy: 1) Describe a data structure to represent it. 2) Given any two people within the genealogy, describe an algorithm to determine if they share a common ancestor. You just need to return true/false, not all ancestors.
1) Each person is represented by an object, with two pointers: "mom" and "dad" that point to their respective parent. 2) Choose one of the two people arbitrarily. Perform depth-first traversal and create a set of ancestors reachable from that person. Perform depth-first traversal on the 2nd person and for each node visited check if they are in the set; if yes, return true. Use a hash-set for best performance.
calculate the height of person 1 in the tree, calculate the height of person 2. Move them up to be the same height. Then keep going until they intersect.
@user: Its not a tree. A genealogy is a graph due to the fact that you have maternal and paternal trees intersecting. Therefore there is no root from which to calculate height.