google加面

二月份google onsite面了5轮，一轮比较诡异，一轮没沟通清楚，没时间做follow up（重写了部分代码），送hc的结果是加面。加面2轮onsite，地点不变。
round 1:
（1）假设给你一个字符串的iterator，如何实现一个iterator，通过调用hasNext和next可以返回字符串的统计信息。
例子：
逐个string iterator返回的内容为："a", "a", "a", "b", "a"
你实现的iterator每个next应该返回：<a, 3>, <b, 1>, <a, 1>
正常思路写就好了，没什么fancy的内容。
（2）给一个正方形矩阵，里面都是正数或0，正数代表金矿的数量，你可以选择任何一个整数作为起点，给出可以拿到的最多的金矿，不能往回走。行走只有四个方向，上下左右。
例子：下面例子可以选取 2 2 4 5 6 7 3 4，总和达到最大值。
0 1 0 3 4
2 2 0 7 0
0

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

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

ng>
第一轮第二题输入是nxn方阵，我是定义一个同样size的矩阵里面保存一个class类型的数据，这个class差不多这样定义的
class Cell {
public int left, right, up, down;
}
用于记录原矩阵中某个非0位置的累积数值。

补充内容 (2018-4-1 01:35):
left表示从左侧进入到该位置的最大金矿，up意味着从上面进入该位置的最大金矿，当你需要邻居参数时候，比如访问你上面的邻居，你要排除他的down value，从另外3个里面选出最大值来更新当前位置。

第一题第二问，由于无环，dfs一遍不会重复，应该是不需要任何extra space（标记数组坐在原数组上）， O（nm）矩阵大小就能做。

1. #include <iostream>
   
2. #include <vector>
   
3. 
   
4. using namespace std;
   
5. 
   
6. inline check(vector<vector<int>>& vec, int i, int j){
   
7.     return i >= 0 && j >= 0 && i < vec.size() && j < vec[0].size() && vec[i][j] > 0;
   
8. }
   
9. 
   
10. int dfs(vector<vector<int>>& vec, int i, int j, int ii, int jj, int& maxmine){
    
11.     int val = vec[i][j];
    
12.     int curmax = 0, accummax = 0;
    
13.     int l = 0, r = 0, u = 0, d = 0;
    
14.     if(check(vec,i+1,j) && (i+1 != ii || j != jj))r = dfs(vec,i+1,j,i,j,maxmine);
    
15.     if(check(vec,i-1,j) && (i-1 != ii || j != jj))l = dfs(vec,i-1,j,i,j,maxmine);
    
16.     if(check(vec,i,j+1) && (i != ii || j+1 != jj))d = dfs(vec,i,j+1,i,j,maxmine);
    
17.     if(check(vec,i,j-1) && (i != ii || j-1 != jj))u = dfs(vec,i,j-1,i,j,maxmine);
    
18.     accummax = max(r,max(l,max(d,u)));
    
19.     curmax = max(l+r,max(l+u,max(l+d,max(r+u,max(r+d,u+d)))));
    
20.     maxmine = max(maxmine,curmax+val);
    
21.     vec[i][j] = 0;
    
22.     return val + accummax;
    
23. }
    
24. 
    
25. int maxMine(vector<vector<int>>& vec){
    
26.     int n = vec.size();
    
27.     if(n == 0)return 0;
    
28.     int m = vec[0].size();
    
29.     int maxmine = 0;
    
30.     for(int i=0;i<n;i++){
    
31.         for(int j=0;j<m;j++){
    
32.             if(vec[i][j] > 0){
    
33.                 dfs(vec,i,j,-1,-1,maxmine);
    
34.             }
    
35.         }
    
36.     }
    
37.     return maxmine;
    
38. }
    
39. 
    
40. int main(){
    
41.     vector<vector<int>> vec({{1,0,0,0,2,4,6,0,0,1},
    
42.                             {3,1,4,3,0,0,1,2,0,2},
    
43.                             {5,0,0,2,1,0,0,3,0,3},
    
44.                             {0,0,0,0,5,6,5,4,1,4},
    
45.                             {2,4,6,0,4,0,7,0,2,0},
    
46.                             {0,0,1,2,3,0,8,0,3,0},
    
47.                             {0,0,2,0,0,0,9,0,4,0},
    
48.                             {0,0,3,4,5,0,0,0,0,0},
    
49.                             {0,0,0,0,6,5,3,4,9,0},
    
50.                             {1,2,3,4,5,0,2,0,0,0}});
    
51.     cout << maxMine(vec) << endl;
    
52. }
    

复制代码

c艹的，上面老哥的样例，答案应该是91. 如果有问题欢迎指正~

round2应该可以简单如下解决，思路是：一个点成为一棵树的root，当且仅当它不被删除 and 它的父亲被删除

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

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

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

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

厉害，紫薯紫薯

請問第一輪的第二題有甚麼想法呢?
本來想說用memorize + dfs 但是似乎有可能會重覆走到之前計算過的點?

還是要每個點當起點做一次dfs呢?

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

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

没懂round2的例子，能不能解释一下？

其实round2 删除树的那个可以在return list里面边检测边删，遇到一个要删除的结点就把它的左右子树加入list 然后递归左右子树就行了 最后保存在list里面的就是删除过的。这也算是list添加的是copy by reference的一个优势吧

找金礦那題，leetCode上有類似的嗎？沒做過這種需要DFS+Memorization的題，想練習一下

金礦那題，正數代表金礦數量，那麼零代表什麼？代表沒有金礦嗎？我只要從最左上角一路往右走到底，接著往下一格，再一路往左走到底，再往下走一格，再一路往右到底，一直重複下去直到整個Matrix被走完，這樣一定能搜集到最多金礦。相當於算整個Matrix的總和

lf963 发表于 2018-3-30 15:02
找金礦那題，leetCode上有類似的嗎？沒做過這種需要DFS+Memorization的題，想練習一下

leetcode上memorization的只有一道题吧

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

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