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 4 5 6 2
0 0 0 0 0
0 2 0 0 2
输入中，正数不会形成cycle，比如见不

您好！
本帖隐藏的内容需要积分高于 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

请问一下 round2 后序遍历可以吗？
我测试了几个能通过， 不知道有没有缺陷
public static TreeNode deleteNode(TreeNode root) {
                if (root == null) return null;
                root.left = deleteNode(root.left);
                root.right = deleteNode(root.right);
                if (root should be deleted) {
                        if (root.left != null && root.right != null) {
                                list.add(root.left);
                                list.add(root.right);
                        }
                        else if (root.left != null) list.add(root.left);
                        else if (root.right != null) list.add(root.right);
                        root = null;

                       
                }
                return root;
        }

厉害，紫薯紫薯

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

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

reliveinfire 发表于 2018-3-30 11:13
請問第一輪的第二題有甚麼想法呢?
本來想說用memorize + dfs 但是似乎有可能會重覆走到之前計算過的點?

...

应该是每个点都要做一次dfs的，但是也可以做memorize，因为这相当于一个无环图，所以当前节点坐标和父节点坐标可以唯一确定当前点所能搜到的所有点，就可以做记忆化了

没懂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的只有一道题吧

public class Solution {
    public int getMax(int[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return 0;
        }
        int m = matrix.length, n = matrix[0].length;
        int[][][] dp = new int[m][n][4];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                for (int k = 0; k < 4; k++) {
                    dp[i][j][k] = -1;
                }
            }
        }
        int max = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] > 0) {
                    max = Math.max(max, dfs(i, j, matrix, dp , 0));
                    max = Math.max(max, dfs(i, j, matrix, dp , 1));
                    max = Math.max(max, dfs(i, j, matrix, dp ,  2));
                    max = Math.max(max, dfs(i, j, matrix, dp , 3));
                }
            }
        }
        return max;
    }

    private int dfs(int i, int j, int[][] matrix, int[][][] dp, int dir) {
        if (matrix[i][j] == 0) {
            return 0;
        }
        int sum = matrix[i][j];
        i += getDir(dir)[0];
        j += getDir(dir)[1];
        if (i<0||j<0||i>=matrix.length||j>=matrix[0].length||matrix[i][j]==0) {
            return sum;
        }
        int max = -1;
        for (int k : dirs) {
            if (k == 3 - dir) continue;
            if (dp[i][j][dir] != -1) {
                max =  Math.max(max, dp[i][j][dir] + sum);
            } else {
                max = Math.max(max, dfs(i, j, matrix, dp, k) + sum);
            }
        }
        dp[i][j][dir] = max - sum;
        return max;
    }

    private int[] dirs = {0, 1, 2, 3};

    private int[] getDir(int i) {
        if (i == 0) return new int[]{0 ,-1};
        if (i == 1) return new int[]{-1 ,0};
        if (i == 2) return new int[]{1, 0};
        if (i == 3) return new int[]{0, 1};
        return new int[0];
    }

    public static void main(String[] args) {
        int[][] matrix = {
                {0 ,1 ,0 ,3 ,4},
                {2, 2 ,0 ,7, 0},
                {0 ,4 ,5 ,6, 2},
                {0 ,0, 0, 0 ,0},
                {0 ,2 ,0, 0 ,2 },
        };
        System.out.println(new Solution().getMax(matrix));
    }
}