Google Interview - 判断任意两个人是否有血缘关系

Given a family tree for a few generations for the entire population and two people, write a routine that will find out if they are blood related. Siblings are blood related since they have the same parents. Cousins are blood related since one of their parents have the same parents etc. 

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.

即判断两个人在家族图谱中是否存在血缘关系。

 

给你两个人A和B，自己设计数据结构，判断他们是否有血缘关系。我的答案：一开始看不懂这题，紧张的要死，后来终于想到了，这不是二叉树嘛。设计两个TreeNode(int id, TreeNode left, TreeNode right)，left和right是root节点的parents，判断A和B是否包含有id相同的节点。我给了俩个答案，第一个是递归，第二个用HashSet。都问了时间复杂度和空间复杂度。由于HashSet方法要遍历二叉树，我还介绍了下遍历二叉树的三种方法（Recursive, Iterative, Morris Traversal），面试官好像对Morris遍历比较感兴趣，让我简单讲了下。

 

public static class Person {
  Person[] parents;
}

// naming for cousins is: n th cousin m times removed
// where n is the min generations to a common ancestor and m is the number of generations difference between the 2 cousins
// so this is going to be O((2^n+m)+2) which is still more efficient than dfs assuming the num generations in the population is > n+m
public boolean bloodRelated(Person p1, Person p2) {
  // simple search would go down p1's children/grandchildren/etc and see if we find p2
  // then vice versa
  // then worry about cousin style relationships
  // here we'd go up the parent tree on both until we found a common node (or ran out of data)

  // we could take this last approach anyway and it would get us a parent-child match too
  Set<Person> p1Ancestors = new HashSet<Person>();
  Set<Person> p2Ancestors = new HashSet<Person>();

  // so ideally here we're going to do BFS, but we're going to do 2 at once to try to minimize the depth we have to go
  List<Person> p1Discovered = new LinkedList<Person>();
  p1Discovered.add(p1);
  List<Person> p2Discovered = new LinkedList<Person>();
  p2Discovered.add(p2);

  while (!p1Discovered.isEmpty() || !p2Discovered.isEmpty()) {
    Person nextP1 = p1Discovered.remove(0);
    if (nextP1 != null) {
      if (p2Ancestors.contains(nextP1)) {
        return true;
      }

      for (Person parent : nextP1.parents) {
        p1Discovered.add(parent);
      }
      p1Ancestors.add(nextP1);
    }

    Person nextP2 = p2Discovered.remove(0);
    if (nextP2 != null) {
      if (p1Ancestors.contains(nextP2)) {
        return true;
      }

      for (Person parent : nextP2.parents) {
        p2Discovered.add(parent);
      }
      p2Ancestors.add(nextP2);
    }
  }
  return false;
}

 

Reference:

http://www.careercup.com/question?id=4812957531766784

http://www.1point3acres.com/bbs/thread-133598-1-1.html