`

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

分享到:
评论

相关推荐

    vue-interview-questions-master.zip

    VUE 面试题汇合 vue-interview-questions-master VUE 面试题汇合 vue-interview-questions-master VUE 面试题汇合 vue-interview-questions-master VUE 面试题汇合 vue-interview-questions-master VUE 面试题...

    interview-docs-master.zip

    【压缩包子文件的文件名称列表】: "interview-docs-master" 指出压缩包内有一个名为"interview-docs-master"的文件或目录。通常,这样的结构可能包含一个顶级目录,里面按照不同主题组织了各种文档,比如FAQs、面试...

    123-Essential-JavaScript-Interview-Question, JavaScript访问问题.zip

    123-Essential-JavaScript-Interview-Question, JavaScript访问问题 123 -JavaScript-Interview-Questions这本书将由 2018年06月 完成并可以供购买。 如果你想让我把这本书的早期拷贝,请在这里添加你的NAME 和电子...

    Algorithm-coding-interview-university.zip

    本压缩包中的"coding-interview-university-master"目录,很可能是包含了一个逐步学习算法和数据结构的课程结构,这对于准备技术面试,尤其是硅谷流行的“编程面试”极其有价值。 学习算法,首先要理解基础的数据...

    Interview-code-practice-python-master_escapek5u_python_

    标题中的"Interview-code-practice-python-master_escapek5u_python_"暗示了这是一个关于Python编程的面试题练习项目,可能包含了各种常见的编程题目,旨在帮助开发者准备技术面试。"escapek5u"可能是创建或整理这个...

    Algorithm_for_Interview-Chinese-master.zip

    "Algorithm_for_Interview-Chinese-master.zip" 这个压缩包文件很可能包含了丰富的面试准备资料,聚焦于C++语言,涵盖了多种核心算法和概念。让我们深入探讨一下这些关键知识点。 1. **查找与排序**: - **查找...

    Technical-Interview-Preparation-Checklist.pdf

    Technical-Interview-Preparation-Checklist.pdf

    Interview-Materials.rar__interview_interview-q

    这份名为"Interview-Materials.rar__interview_interview-q"的压缩包文件显然是为准备IT行业面试者精心准备的一份资源集合。它涵盖了C、C++以及Linux等多个关键领域的知识,帮助求职者一站式获取必要的面试准备材料...

    DOCKER-INTERVIEW-QUESTIONS.pdf

    DOCKER-INTERVIEW-QUESTIONS.pdf

    Java-Interview-超全集合github上评分最高的jiva面试题

    "Java-Interview-超全集合github上评分最高的jiva面试题"就是一个这样的宝藏,它涵盖了Java编程语言、Git版本控制工具以及面试策略等多个方面的知识点。以下是这些内容的详细解析: 1. **Java基础** - **数据类型...

    amusi#Deep-Learning-Interview-Book#深度学习框架1

    深度学习框架001 深度学习框架有哪些?002 介绍一下TensorFlow常用的Optimizer003 Caffe的depthwise为什么慢,怎么解决00

    115-Java-Interview-Questions-and-Answers, 115 Java访谈问题和答案- 终极列表.zip

    115-Java-Interview-Questions-and-Answers, 115 Java访谈问题和答案- 终极列表 #115-Java-Interview-Questions-and-Answers我们将讨论关于Java面试中可以使用的各种问题,以便雇主在Java和面向对象编程方面测试你的...

    Angular-angular-interview-questions.zip

    Angular-angular-interview-questions.zip,300个角度面试问答列表[WIP]角度面试问答,Angularjs于2016年发布,是Angularjs的重写版。它专注于良好的移动开发、模块化和改进的依赖注入。angular的设计目的是全面解决...

    Java interview-高级Java面试题2019-java-interview.zip

    Java interview-高级Java面试题2019_java-interview.zip

    java面试题-java-interview-questions-master.zip

    java面试题_java-interview-questions-master.zip2、在 Java 程序中怎么保证多线程的运行安全? 出现线程安全问题的原因一般都是三个原因: 1、 线程切换带来的原子性问题 解决办法:使用多线程之间同步...

    Interview-main-源码.rar

    在编程领域,面试是检验开发者技能的重要环节,而"Interview-main-源码.rar"这个压缩包很可能包含了常见的面试题目和相关问题的解答,以及可能的实现源代码。这份源码是开发者们提升自身技能、准备面试的宝贵资源。...

    frame-project-interview-master.zip

    "frame-project-interview-master.zip" 这个文件名暗示了一个与软件开发相关的项目,特别是面试准备或框架实践。"frame"可能指的是编程框架,如Spring、Angular或者React,而"project-interview"则可能表示这是一个...

    royIdoodle#fe-interview-chaos#003.判断链表是否有环1

    判断链表是否有环LeetCode原题难度: 简单解题* Definition for singly-linked list.* function ListNod

    coding-interview-in-java.pdf

    - 判断两个字符串是否相差一个字符编辑(插入、删除或替换)。这是一个字符串相似度问题,也称为编辑距离问题。 9. MergeSortedArray - 将两个有序数组合并为一个有序数组。这是基础的数组操作,也是对排序算法的...

    The-Ultimate-Strategy-to-Preparing-for-a-Coding-Interview-Medium.pdf

    The-Ultimate-Strategy-to-Preparing-for-a-Coding-Interview-Medium.pdf

Global site tag (gtag.js) - Google Analytics