Google Interview Question: You have a genealogy: 1) Desc... | Glassdoor

Interview Question

Software Engineer Interview Mountain View, CA

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.
Tags:
data structures, software design, analytical, analytical reasoning, algorithm, engineering
Answer

Interview Answer

6 Answers

0

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.

Interview Candidate on Mar 21, 2010
1

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 on Apr 14, 2010
3

@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.

Anonymous on Apr 14, 2010
0

If you've optimizing for worst case, hash set is O(n) for search. You'd do better in worst case with a sorted structure. You'd do even better if you store a "visited" flag at each node. Alternately you can number each node and keep an array of visited flags.

since depth first seach might find a longer link through dad before checking mom, you're better off with breadth first search. Anything reachable in one hop would be seen before anything reachable at best in 2 hops

Anonymous on Apr 23, 2010
0

Yes. Good points. The second traversal should be breadth first. The first traversal it doesn't matter, as you need to visit all ancestors anyways.

The use of a visited flag is a good optimization. Based upon the way the question was worded, it wasn't clear if you could design the data structure to optimize the algorithm or not.

Anonymous on Apr 24, 2010
0

I belive both the first and second should be BFS traversals

RAHUL on Aug 18, 2013

Add Answers or Comments

To comment on this, Sign In or Sign Up.