谷歌onsite面经

yzeng61987 发表于 2018-3-6 10:20
楼主第四题bool matrix 存在 byte array里是从第一行开始数八个bool存成一个byte，一次往后数，最后一个如 ...

嗯 对往后面填0

lee.leon1110 发表于 2018-3-6 11:12
第5题的答案应该是[A, B, C, D,E ] 吧？，因为都能到Safe啊

要是能“一定”到safe state

lee.leon1110 发表于 2018-3-6 11:12
第5题的答案应该是[A, B, C, D,E ] 吧？，因为都能到Safe啊

要排除有环的， A 不一定到  C D E，要是到了B就在环里的了

请问楼主 boolean matrix 那题是什么思路啊？感觉这题没什么算法啊

wtcupup 发表于 2018-3-6 12:46
请问楼主 boolean matrix 那题是什么思路啊？感觉这题没什么算法啊

这题没什么算法 就是考boolean operation

感谢楼主分享！

第五题还是有点不明白：假设有两个state A -> {B, safe}, B -> {A, safe}，那么A和B是否应该被输出呢？

vtiaocao 发表于 2018-3-5 09:50
第五题这个「一定」有点意思了。。怎么解？普通BFS/DFS行吗？

完了 第二题不会。。回去刷tag。。3题原题 ...

我写了一个java的，手动测了几个test case没发现什么问题

1. class Solver {
   
2.     private boolean[] visited;
   
3.     private boolean[] safe;
   
4. 
   
5. 
   
6.     private boolean dfs(int node, Map<Integer, Set<Integer>> g, int safeNode) {
   
7. 
   
8.         assert(!visited[node]);
   
9.         if (g.get(node) == null) { // base case: dangling Node
   
10.             visited[node] = true;
    
11.             safe[node] = (node == safeNode);
    
12.             return safe[node];
    
13.         }
    
14. 
    
15.         visited[node] = true;
    
16.         for (int next : g.get(node)) {
    
17.             if (visited[next]) {
    
18.                 if (!safe[next]) {
    
19.                     safe[node] = false;
    
20.                     return false;
    
21.                 }
    
22.             } else {
    
23.                 if (!dfs(next, g, safeNode)) {
    
24.                     safe[node] = false;
    
25.                     return false;
    
26.                 }
    
27.             }
    
28.         }
    
29.         safe[node] = true;
    
30.         return true;
    
31.     }
    
32. 
    
33.     public List<Integer> solve(Map<Integer, Set<Integer>> g, int safeNode) {
    
34.         visited = new boolean[safeNode + 1];
    
35.         safe = new boolean[safeNode + 1];
    
36.         for (int i = 0; i <= safeNode; ++i) {
    
37.             if (!visited[i]) {
    
38.                 dfs(i, g, safeNode);
    
39.             }
    
40.         }
    
41. 
    
42.         List<Integer> res = new ArrayList<>();
    
43.         for (int i = 0; i < safeNode; ++i) { // won't output safe node
    
44.             if (safe[i]) {
    
45.                 res.add(i);
    
46.             }
    
47.         }
    
48.         return res;
    
49.     }
    
50. }

复制代码

619899442 发表于 2018-3-7 07:43
感谢楼主分享！

第五题还是有点不明白：假设有两个state A -> {B, safe}, B -> {A, safe}，那么A和B是否 ...

这个情况不输出A B

peterxianggao 发表于 2018-3-7 13:23
这个情况不输出A B

Make sense! 谢谢啦