gg intern 02/09面经

趁着跑test来发面经求RP
约的时间是今天12:00PM-1:00PM第一轮 1:00PM-2:00PM第二轮

第一轮印度小哥 口音虽然重。。。但是平时跟印度人组队学习的唯一好处就是现在听他们讲话无压力= =
上来直接做题

then 时间复杂度空间复杂度
之前没看过面经 面完查到

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

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

面amazon 求a也收了他 于是咱们就可以一起去Seattle愉快地浪起来了~~~

然后似乎左和上可以一起算，右和下可以一起算，于是乎可以两次遍历就得到最大值

第二题google变了N种问法考的....有炸弹，怪兽和墙的，有人，花和墙的....现在又来了人，灯和墙.....也是醉了.....是fulltime onsite经常遇到的一道题，第一题还真没见过....再次证明了狗家题库浩如烟海

第二题解法，只是这个是flower and garden

1. ublic class FlowersInGarden {
   
2. 
   
3.         public static void main(String[] args) {
   
4.                 char[][] matrix = {{'f', 'x', 'x', 'w', 'f'},
   
5.                                      {'f', 'f', 'x' ,'x' ,'x'},
   
6.                                      {'x', 'x', 'f', 'w', 'f'},
   
7.                                      {'f', 'f', 'x', 'w', 'x'}};
   
8.                 maxFlowersInGarden(matrix);
   
9.         }
   
10.        
    
11.         public static int maxFlowersInGarden(char[][] matrix) {
    
12.                 if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
    
13.                         return 0;
    
14.                 }
    
15.                 int m = matrix.length;
    
16.                 int n = matrix[0].length;
    
17.                
    
18.                 int[][] res = new int[m][n];
    
19.                 for (int i = 0; i < m; i++) {
    
20.                         int count = 0;
    
21.                         int j = 0;
    
22.                         int start = 0;
    
23.                         while (j < n) {
    
24.                                 if (matrix[i][j] == 'f') {
    
25.                                         count++;
    
26.                                 } else if (matrix[i][j] == 'w') {
    
27.                                         for (int k = start; k < j; k++) {
    
28.                                                 res[i][k] = count;
    
29.                                         }
    
30.                                         start = j + 1;
    
31.                                         count = 0;
    
32.                                 }
    
33.                                 j++;
    
34.                         }
    
35.                         for (int k = start; k < j; k++) {
    
36.                                 res[i][k] = count;
    
37.                         }
    
38.                 }
    
39.                 for (int j = 0; j < n; j++) {
    
40.                         int count = 0;
    
41.                         int i = 0;
    
42.                         int start = 0;
    
43.                         while (i < m) {
    
44.                                 if (matrix[i][j] == 'f') {
    
45.                                         count++;
    
46.                                 } else if (matrix[i][j] == 'w') {
    
47.                                         for (int k = start; k < i; k++) {
    
48.                                                 res[k][j] += count;
    
49.                                         }
    
50.                                         start = i + 1;
    
51.                                         count = 0;
    
52.                                 }
    
53.                                 i++;
    
54.                         }
    
55.                         for (int k = start; k < i; k++) {
    
56.                                 res[k][j] += count;
    
57.                         }
    
58.                 }
    
59.                 for (int i = 0; i < m; i++) {
    
60.                         for (int j = 0; j < n; j++) {
    
61.                                 if (matrix[i][j] == 'f') {
    
62.                                         res[i][j] -= 1;
    
63.                                 }
    
64.                         }
    
65.                 }
    
66.                 int max = 0;
    
67.                 for (int i = 0; i < m; i++) {
    
68.                         for (int j = 0; j < n; j++) {
    
69.                                 System.out.print(res[i][j] + " ");
    
70.                                 max = Math.max(max, res[i][j]);
    
71.                         }
    
72.                         System.out.println();
    
73.                 }
    
74.                
    
75.                
    
76.                 return max;
    
77.         }
    
78. }
    

复制代码

johnjavabean 发表于 2016-2-10 14:36
第二题google变了N种问法考的....有炸弹，怪兽和墙的，有人，花和墙的....现在又来了人，灯和墙.....也是醉 ...

可以求第二题的做法咩？！

ilyak 发表于 2016-2-10 14:59
可以求第二题的做法咩？！

新建一个矩阵，先按行得到每个点往左往右看能看到灯总数，墙的点为0，然后再按列遍历，把上下看的总数加上去，最后求一个max，时间复杂度空间复杂度都是n^2

哦哦哦相当于brute force遍历整个matrix可以落脚的点？谢谢！

johnjavabean 发表于 2016-2-9 23:02
新建一个矩阵，先按行得到每个点往左往右看能看到灯总数，墙的点为0，然后再按列遍历，把上下看的总数加 ...

这个时间复杂度是O(n^3) 空间复杂度是O(n)

ilyak 发表于 2016-2-10 15:04
哦哦哦相当于brute force遍历整个matrix可以落脚的点？谢谢！

并不是....你这样复杂度是m*n*(m+n)

candy_shmily 发表于 2016-2-10 15:06
这个时间复杂度是O(n^3) 空间复杂度是O(n)

看来我表述的不清楚，第一遍按行左到右，dp[i][j] = dp[i][j-1] + 1 if m[i][j] == L，遇到W直接设成0，然后从右到左再加一遍，然后从上到下，从下到上，最后一遍可以顺便求出max，四边遍历，每次n^2，所以n^2时间n^2空间

补充内容 (2016-2-10 15:13):
晕....打[   i  ]会直接变斜体，其实是dp[ i   ][j]啦

johnjavabean 发表于 2016-2-9 23:07
并不是....你这样复杂度是m*n*(m+n)

worst case有N*N个点要check 每个点要最多要check行和列2N 于是N^3

johnjavabean 发表于 2016-2-9 23:12
看来我表述的不清楚，第一遍按行左到右，dp[j] = dp[j-1] + 1 if m[j] == L，遇到W直接设成0，然后从右到 ...

那我们的方法不一样 你的比较高端 是她的follow up 我没写出来 只会N^3的