G家实习店面

刚结束的G家实习店面。
1. 应该是中国姐姐，我很懵，提示了我很多，很感谢。N by M grids. red cells and black cells. Compute the # of squares without black cells.
2. 美国小伙。写BigInt类的你认为需要的接口函数，只写定义就好。然后让实现了Constructor和Comp函数（比较两个BigInt）。让写了一

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

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

t出现的次数是1M，现在出现1M+1K，你觉得程序有没有bug。我就说normal distribution有个confidence interval啊，可以算出来然后看看啊。

就这样，希望都好运。

楼主第一题能详细讲讲么？大square里面的小square需要单独算么？
能顺便讲讲你怎么做的么？DP？
谢谢！

写了下第一题的代码，欢迎指教

1. public class SquaresNumber {
   
2. 
   
3.         public static void main(String[] args) {
   
4.                 int[][] matrix = {{0, 1, 1},
   
5.                                                   {1, 1, 1},
   
6.                                                   {1, 1, 1}};
   
7.                 getSquaresNumber(matrix);
   
8.         }
   
9.         public static int getSquaresNumber(int[][] matrix) {
   
10.                 if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
    
11.                         return 0;
    
12.                 }
    
13.                 int m = matrix.length;
    
14.                 int n = matrix[0].length;
    
15.                 int[][] dp  = new int[m][n];
    
16.                 for (int i = 0; i < m; i++) {
    
17.                         if (matrix[i][0] == 1) {
    
18.                                 dp[i][0] = 1;
    
19.                         }
    
20.                 }
    
21.                 for (int i = 0; i < n; i++) {
    
22.                         if (matrix[0][i] == 1) {
    
23.                                 dp[0][i] = 1;
    
24.                         }
    
25.                 }
    
26.                 for (int i = 1; i < m; i++) {
    
27.                         for (int j = 1; j < n; j++) {
    
28.                                 if (matrix[i][j] == 1) {
    
29.                                         dp[i][j] = Math.min(dp[i - 1][j], Math.min(dp[i - 1][j - 1], dp[i][j - 1])) + 1;
    
30.                                 } else {
    
31.                                         dp[i][j] = 0;
    
32.                                 }
    
33.                         }
    
34.                 }
    
35.                 int res = 0;
    
36.                 for (int[] arr : dp) {
    
37.                         for (int i : arr) {
    
38.                                 res += i;
    
39.                         }
    
40.                 }
    
41.                 System.out.println(res);
    
42.                 return res;
    
43.         }
    
44. }
    

复制代码

楼主第一题能详细讲讲么？大square里面的小square需要单独算么？
能顺便讲讲你怎么做的么？DP？
谢谢！

对，就是DP。所有size的square都算，比如一个2X2的格子有5个square，3X3的格子一共有14个square。。。
跟lc那道maximal square有点类似。
不过最后的结果要把DP的那个matrix全部扫一遍加起来就好了。

感觉这次店面题目难爆了。。。。

BigInt 类是啥

y42353041 发表于 2015-11-12 08:26
对，就是DP。所有size的square都算，比如一个2X2的格子有5个square，3X3的格子一共有14个square。。。
...

有道理!感觉楼主面的确实有点难啊...祝offer早点到手吧

y42353041 发表于 2015-11-11 16:26
对，就是DP。所有size的square都算，比如一个2X2的格子有5个square，3X3的格子一共有14个square。。。
...

不是很明白，lz可以详细说一点吗？

lz有消息了吗？

lz有消息了吗？

跪了，呵呵

lz这个太难了。。