谷歌onsite面经

1 利口以斯遛 变形
2 利口散久久
3 研究
4 利口散以 + encode binary in bytes 就是给一个matrix of size M * N，这个matrix被encode在bytes里比如一个 4 * 4 的 bool matrix
[ 0 0 0 0
  1 0 0 1
  0 0 0 0
  0 0 0 1]
会被encode成 byte array [9, 1]
然后要写一个函数 set_one(vector<byte> arr, int M, int N, in

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

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

14:33):
第四题补充：
就是给一个boolean matrix的interface
但是 underline的存储是在一个byte array里面
比如一个16*5的boolean matrix是可以存在一个10个element的byte array里的

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. }

复制代码

第五题，基本的DFS+memo．楼上几位说是倒序BFS的都是误入歧途的思想．
贴一下我的C++，如果有bug还请指正，如果有帮助还请点赞打个赏．

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

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

第五题这个「一定」有点意思了。。怎么解？普通BFS/DFS行吗？

完了 第二题不会。。回去刷tag。。3题原题都是在Gtag里的(虽然只包括了一半的题)

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

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

第五题DFS就可以了

多谢楼主，请问楼主第三题能说清楚一下嘛？ 多谢了

补充内容 (2018-3-5 14:16):
对不起。。是第四题，没怎么看懂。。

请问楼主第三题研究是什么？第四题楼主的做法是什么能说下吗？是直接找到set相应位置，修改相应的数，还是再重新遍历一遍算啊，用了bit manipulation吗？

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

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

jasonyang04 发表于 2018-3-5 16:00
请问楼主第三题研究是什么？第四题楼主的做法是什么能说下吗？是直接找到set相应位置，修改相应的数，还是 ...

找到对应的start和end位置 然后用bit mask & 一下