Google北京实习电面

今天下午刚电话面试的谷歌北京的实习生职位。人生中的第一次找工作面试，紧张死。。。在这里分享一下题目啦。
如下，表示一张图，以第一个为例：结点0可以到达结点1,2,4。每个节点都只有两种状态failure和success。

“Give

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

x">

以结点2为例，因为2既能到达3又能到达5，由于3是failure的，所以2也是failure，即只有2能到达的所有状态都是success，结点2才是success的。


以上。

祝楼主顺利通过面试！顺便问下，您知道google北京的实习时间是从什么时间开始，什么时间结束吗？

Anubarak 发表于 2017-2-9 01:59
祝楼主顺利通过面试！顺便问下，您知道google北京的实习时间是从什么时间开始，什么时间结束吗？

7月到10月的14周全天实习

christineniu 发表于 2017-2-9 16:23
7月到10月的14周全天实习

9月份不就开学了吗…

BingleLove 发表于 2017-2-9 17:11
9月份不就开学了吗…

是的，但是实习时间上是这样要求的。

楼主，就问了一道题是么？ 祝楼主拿offer

楼主请问题目里的state是什么意思？能把题目说仔细一点吗？谢谢！

楼主求微信抱团啊！刚好也是这周onsite

1. import java.util.*;
   
2. public class MachineSuccess {
   
3.     public static void main(String[] args){
   
4.         MachineSuccess m = new MachineSuccess();
   
5. 
   
6.         Node n0 = new Node(0);
   
7.         Node n1 = new Node(1);
   
8.         Node n2 = new Node(2);
   
9.         Node n3 = new Node(3);
   
10.         Node n4 = new Node(4);
    
11.         Node n5 = new Node(5);
    
12.         Node n6 = new Node(6);
    
13.         Node nFailure = new Node(false);
    
14.         Node nSuccess = new Node(true);
    
15. 
    
16.         n0.children.add(n1);
    
17.         n0.children.add(n4);
    
18.         n0.children.add(n5);
    
19. 
    
20.         n1.children.add(n2);
    
21. 
    
22.         n2.children.add(nSuccess);
    
23. 
    
24.         n3.children.add(nFailure);
    
25.         n3.children.add(n6);
    
26. 
    
27.         n4.children.add(n3);
    
28. 
    
29.         n5.children.add(nFailure);
    
30. 
    
31.         n6.children.add(n0);
    
32.         n6.children.add(nSuccess);
    
33. 
    
34.         System.out.println(m.machineState(n0));
    
35.         System.out.println(m.machineState(n1));
    
36.         System.out.println(m.machineState(n2));
    
37.         System.out.println(m.machineState(n3));
    
38.         System.out.println(m.machineState(n4));
    
39.         System.out.println(m.machineState(n5));
    
40.         System.out.println(m.machineState(n6));
    
41.     }
    
42. 
    
43.     boolean machineState(Node node){
    
44.         HashSet<Node> visited = new HashSet<Node>();
    
45.         return DFS(node,visited);
    
46.     }
    
47.     //Assumption 1: Success node and Failure node must be leaf node
    
48.     //              (a node doesn't have children)
    
49.     //Assumption 2: A leaf node(a node doesn't have children) must be
    
50.     //              either Success node or Failure node
    
51.     //e.g. {0->[1,2,3], 2->[0], 3->[1]} doesn't exist
    
52.     //     because node 1 is leaf node but it is neither Success node nor Failure node
    
53.     boolean DFS(Node node, HashSet<Node> visited){
    
54.         if(node.val == -1)  //if we reach Success node or Failure node
    
55.             return node.isSuccess;
    
56.         visited.add(node);
    
57.         for(Node child : node.children){
    
58.             if(!visited.contains(child) && !DFS(child,visited))
    
59.                 return false;
    
60.         }
    
61.         return true;
    
62.     }
    
63. }
    
64. 
    
65. class Node{
    
66.     int val;
    
67.     ArrayList<Node> children = new ArrayList<Node>();
    
68.     boolean isSuccess;
    
69.     Node(int val){
    
70.         this.val = val;
    
71.     }
    
72.     Node(boolean isSuccess){    //we use val = -1 to represent that
    
73.         this.val = -1;          //this node is either a Success node or Failure node
    
74.         this.isSuccess = isSuccess;
    
75.     }
    
76. }
    

复制代码