📣 黑五价提前开抢|VIP一年通行证5折,蓝莓、Offer多多同步特惠
回复: 20
跳转到指定楼层
上一主题 下一主题
收起左侧

新鲜店面骨狗

全局:

2018(10-12月) 码农类General 硕士 实习@google - 内推 - 技术电面  | | Other | 应届毕业生

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

x
第一次发帖,感觉跪了,发了一个simpson家谱的题目来,问我找两个node的edge数量,因为是家谱所以不是树
您好!
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Popular Interview Questions from Top Companies
度信息,最后找到共同ancestor之后两个深度之和就是结果。。。

评分

参与人数 5大米 +11 收起 理由
kekewu + 3 很有用的信息!
littlegrass + 3 很有用的信息!
dranderson + 1 给你点个赞!
stella落尘 + 1 很有用的信息!
reliveinfire + 3 很有用的信息!

查看全部评分


上一篇:Yelp 好好的Skype终面 又改回了三番onsite。很醉。。
下一篇:新鲜谷歌电面

本帖被以下淘专辑推荐:

  • · google|主题: 216, 订阅: 124
推荐
 楼主| chengrr 2017-12-14 12:42:32 | 只看该作者
全局:
您好!
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Popular Interview Questions from Top Companies

评分

参与人数 1大米 +3 收起 理由
kekewu + 3 给你点个赞!

查看全部评分

回复

使用道具 举报

推荐
 楼主| chengrr 2017-12-14 08:01:04 | 只看该作者
全局:
您好!
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Popular Interview Questions from Top Companies

评分

参与人数 1大米 +1 收起 理由
kekewu + 1 给你点个赞!

查看全部评分

回复

使用道具 举报

推荐
lf963 2018-4-8 06:52:11 | 只看该作者
全局:
用BFS找圖的最短路徑
我假設夫妻之間的距離為0
並把夫妻當成一個 node 來看
也就是說原本 Abe 和 Mona 在圖中應該是兩個不同的 node,但我把他們用同個 node 來代表,此 node 命名為 abeMona



  1. import java.util.*;
  2. public class Simpson {
  3.     public static void main(String[] args){
  4.         Map<PersonNode,Set<PersonNode>> familyTree = new HashMap<>();

  5.         PersonNode abe = new PersonNode("Abe");
  6.         familyTree.put(abe,new HashSet<>());

  7.         PersonNode mona = new PersonNode("Mona");
  8.         familyTree.put(mona,new HashSet<>());

  9.         PersonNode clancy = new PersonNode("Clancy");
  10.         familyTree.put(clancy,new HashSet<>());

  11.         PersonNode jacqueline = new PersonNode("Jacqueline");
  12.         familyTree.put(jacqueline,new HashSet<>());

  13.         PersonNode herb = new PersonNode("Herb");
  14.         familyTree.put(herb,new HashSet<>());

  15.         PersonNode homer = new PersonNode("Homer");
  16.         familyTree.put(homer,new HashSet<>());

  17.         PersonNode marge = new PersonNode("Marge");
  18.         familyTree.put(marge,new HashSet<>());

  19.         PersonNode patty = new PersonNode("Patty");
  20.         familyTree.put(patty,new HashSet<>());

  21.         PersonNode selma = new PersonNode("Selma");
  22.         familyTree.put(selma,new HashSet<>());

  23.         PersonNode bart = new PersonNode("Bart");
  24.         familyTree.put(bart,new HashSet<>());

  25.         PersonNode lisa = new PersonNode("Lisa");
  26.         familyTree.put(lisa,new HashSet<>());

  27.         PersonNode maggie = new PersonNode("Maggie");
  28.         familyTree.put(maggie,new HashSet<>());

  29.         PersonNode ling = new PersonNode("Ling");
  30.         familyTree.put(ling,new HashSet<>());



  31.         /*We view couple as one single node*/
  32.         PersonNode abeMona = new PersonNode("AbeMona");
  33.         familyTree.put(abeMona,new HashSet<>());

  34.         PersonNode clancyJacqueline = new PersonNode("ClancyJacqueline");
  35.         familyTree.put(clancyJacqueline,new HashSet<>());

  36.         PersonNode homerMarge = new PersonNode("HoerMarge");
  37.         familyTree.put(homerMarge,new HashSet<>());


  38.         /*construct edges*/
  39.         familyTree.get(abeMona).add(herb);
  40.         familyTree.get(abeMona).add(homerMarge);

  41.         familyTree.get(clancyJacqueline).add(homerMarge);
  42.         familyTree.get(clancyJacqueline).add(patty);
  43.         familyTree.get(clancyJacqueline).add(selma);

  44.         familyTree.get(herb).add(abeMona);

  45.         familyTree.get(homerMarge).add(abeMona);
  46.         familyTree.get(homerMarge).add(clancyJacqueline);
  47.         familyTree.get(homerMarge).add(bart);
  48.         familyTree.get(homerMarge).add(lisa);
  49.         familyTree.get(homerMarge).add(maggie);

  50.         familyTree.get(patty).add(clancyJacqueline);

  51.         familyTree.get(selma).add(clancyJacqueline);
  52.         familyTree.get(selma).add(ling);

  53.         familyTree.get(bart).add(homerMarge);

  54.         familyTree.get(lisa).add(homerMarge);

  55.         familyTree.get(maggie).add(homerMarge);

  56.         familyTree.get(ling).add(selma);



  57.         /*If someone is married, put that person and his/her spouse into this map*/
  58.         HashMap<PersonNode,PersonNode> couple = new HashMap<>();

  59.         couple.put(abe,abeMona);
  60.         couple.put(mona,abeMona);

  61.         couple.put(clancy,clancyJacqueline);
  62.         couple.put(jacqueline,clancyJacqueline);

  63.         couple.put(homer,homerMarge);
  64.         couple.put(marge,homerMarge);


  65.         Simpson s = new Simpson();
  66.         int distance = s.findShortestDistance(abe,mona, familyTree,couple);
  67.         System.out.println(distance);
  68.     }

  69.     int findShortestDistance(PersonNode A, PersonNode B, Map<PersonNode,Set<PersonNode>> familyTree, HashMap<PersonNode,PersonNode> couple){
  70.         //if person A and person B are couple, return 0;
  71.         if(couple.containsKey(A) && couple.containsKey(B) && couple.get(A).equals(couple.get(B)))
  72.             return 0;
  73.         //if person A is married but B is not his/her spouse, we use A's spouse to search instead of A
  74.         if(couple.containsKey(A))
  75.             A = couple.get(A);

  76.         //if person B is married but A is not his/her spouse, we use B's spouse to search instead of B
  77.         if(couple.containsKey(B))
  78.             B = couple.get(B);
  79.         Queue<PersonNode> myQ = new LinkedList<>();
  80.         Set<PersonNode> visited = new HashSet<>();
  81.         int distance = 0;
  82.         myQ.add(A);
  83.         visited.add(A);

  84.         while(!myQ.isEmpty()){
  85.             int qSize = myQ.size();
  86.             for(int i=0; i<qSize; i++){
  87.                 PersonNode curPerson = myQ.poll();
  88.                 if(curPerson == B)
  89.                     return distance;

  90.                 for(PersonNode p : familyTree.get(curPerson)){
  91.                     if(!visited.contains(p)){
  92.                         myQ.add(p);
  93.                         visited.add(curPerson);
  94.                     }
  95.                 }
  96.             }
  97.             distance++;
  98.         }
  99.         //we cannot find a path from A to B
  100.         return -1;
  101.     }
  102. }

  103. class PersonNode{
  104.     String name;
  105.     PersonNode(String name){
  106.         this.name = name;
  107.     }

  108.     public boolean equals(Object o){
  109.         PersonNode p = (PersonNode) o;
  110.         return this.name.equals(p.name);
  111.     }

  112.     public int hashCode(){
  113.         return name.hashCode();
  114.     }
  115. }


复制代码

回复

使用道具 举报

🔗
b01501085 2017-12-14 08:28:28 | 只看该作者
全局:
所以tree root是連到Abe 和 Clancy嗎?
回复

使用道具 举报

🔗
stella落尘 2017-12-14 10:53:12 | 只看该作者
全局:
祝楼主好运 我想请问为什么bart到selma的edge距离是3?  Homer Marge 是一个人么
回复

使用道具 举报

🔗
mushbunny 2017-12-14 11:12:05 | 只看该作者
全局:
您好!
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Popular Interview Questions from Top Companies
回复

使用道具 举报

🔗
 楼主| chengrr 2017-12-14 12:39:10 | 只看该作者
全局:
b01501085 发表于 2017-12-14 08:28
所以tree root是連到Abe 和 Clancy嗎?

Abe 和 Mona 是夫妻, Clancy 和 Jacquin是夫妻,抱歉图画的不太好, Homer和Marge是夫妻,其他都是单身

评分

参与人数 1大米 +3 收起 理由
kekewu + 3 给你点个赞!

查看全部评分

回复

使用道具 举报

🔗
 楼主| chengrr 2017-12-14 12:40:39 | 只看该作者
全局:
您好!
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Popular Interview Questions from Top Companies

评分

参与人数 1大米 +3 收起 理由
kekewu + 3 很有用的信息!

查看全部评分

回复

使用道具 举报

🔗
星星点灯 2017-12-14 12:48:00 | 只看该作者
全局:
学习受教了, 羡慕LZ的思路
回复

使用道具 举报

🔗
stella落尘 2017-12-14 13:06:34 | 只看该作者
全局:

谢谢!明白了!祝楼主面试成功!
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

>
快速回复 返回顶部 返回列表