一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 1742|回复: 15
收起左侧

G家实习店面

[复制链接] |试试Instant~ |关注本帖
y42353041 发表于 2015-11-11 06:52:58 | 显示全部楼层 |阅读模式

2016(7-9月) 码农类 硕士 实习@Google - 内推 - 技术电面 |Other其他

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
刚结束的G家实习店面。. visit 1point3acres.com for more.
1. 应该是中国姐姐,我很懵,提示了我很多,很感谢。N by M grids. red cells and black cells. Compute the # of squares without black cells.
2. 美国小伙。写BigInt类的你认为需要的接口函数,只写定义就好。然后让实现了Constructor和Comp函数(比较两个BigInt)。让写了一大堆test case。
3. 同上美国小伙。一个map{“a":1, "b":2, "c":4}代表每个string(或者char,无所谓)的weight。现在有个函数vector<string> genStrings(map m, int cnt)
让你返回一个vector of string,其中各个string出现的概率和之前给的weight成比例。比如给cnt==700, 那么里面大概有100个”a“, 200个”b“, 400个”c“。
问了好久好久的细节问题,比如time complexity, space complexity,还有hash function collusion,还有这个函数怎么测试。Random函数是给的。. from: 1point3acres.com/bbs
测试的话我就说用个大点的数iterate然后数结果。他问如果”a“expect出现的次数是1M,现在出现1M+1K,你觉得程序有没有bug。我就说normal distribution有个confidence interval啊,可以算出来然后看看啊。. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
. Waral 鍗氬鏈夋洿澶氭枃绔,
就这样,希望都好运。

评分

1

查看全部评分

stonezms 发表于 2015-11-12 01:07:35 | 显示全部楼层
楼主第一题能详细讲讲么?大square里面的小square需要单独算么?
能顺便讲讲你怎么做的么?DP?
谢谢!
回复 支持 1 反对 0

使用道具 举报

Augustus 发表于 2015-11-12 07:08:03 | 显示全部楼层
感觉这次店面题目难爆了。。。。
回复 支持 反对

使用道具 举报

 楼主| y42353041 发表于 2015-11-12 08:26:56 | 显示全部楼层
楼主第一题能详细讲讲么?大square里面的小square需要单独算么?
能顺便讲讲你怎么做的么?DP?
谢谢!

. visit 1point3acres.com for more.
对,就是DP。所有size的square都算,比如一个2X2的格子有5个square,3X3的格子一共有14个square。。。
跟lc那道maximal square有点类似。
不过最后的结果要把DP的那个matrix全部扫一遍加起来就好了。
回复 支持 反对

使用道具 举报

翔在天空 发表于 2015-11-12 11:07:50 | 显示全部楼层
BigInt 类是啥
回复 支持 反对

使用道具 举报

stonezms 发表于 2015-11-12 11:18:02 | 显示全部楼层
y42353041 发表于 2015-11-12 08:26
对,就是DP。所有size的square都算,比如一个2X2的格子有5个square,3X3的格子一共有14个square。。。
...

有道理!感觉楼主面的确实有点难啊...祝offer早点到手吧
回复 支持 反对

使用道具 举报

eko910817 发表于 2015-11-17 07:04:35 | 显示全部楼层
y42353041 发表于 2015-11-11 16:26
对,就是DP。所有size的square都算,比如一个2X2的格子有5个square,3X3的格子一共有14个square。。。.鏈枃鍘熷垱鑷1point3acres璁哄潧
...

不是很明白,lz可以详细说一点吗?
回复 支持 反对

使用道具 举报

c212014 发表于 2015-11-20 04:43:20 | 显示全部楼层
lz有消息了吗?
回复 支持 反对

使用道具 举报

 楼主| y42353041 发表于 2015-11-20 06:25:54 | 显示全部楼层
. 1point 3acres 璁哄潧
lz有消息了吗?
. 1point 3acres 璁哄潧
跪了,呵呵
回复 支持 反对

使用道具 举报

wxr.dal 发表于 2015-11-20 06:29:35 | 显示全部楼层
lz这个太难了。。
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2015-12-5 11:17:34 | 显示全部楼层
写了下第一题的代码,欢迎指教
  1. public class SquaresNumber {

  2.         public static void main(String[] args) {
  3.                 int[][] matrix = {{0, 1, 1}, . more info on 1point3acres.com
  4.                                                   {1, 1, 1},
  5.                                                   {1, 1, 1}};
  6.                 getSquaresNumber(matrix);
  7.         }.1point3acres缃
  8.         public static int getSquaresNumber(int[][] matrix) {
  9.                 if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
  10.                         return 0;
  11.                 }
  12.                 int m = matrix.length;
  13.                 int n = matrix[0].length;
  14.                 int[][] dp  = new int[m][n];
  15.                 for (int i = 0; i < m; i++) {. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  16.                         if (matrix[i][0] == 1) {
  17.                                 dp[i][0] = 1;
  18.                         }
  19.                 }
  20.                 for (int i = 0; i < n; i++) {. visit 1point3acres.com for more.
  21.                         if (matrix[0][i] == 1) {
  22.                                 dp[0][i] = 1;
  23.                         }
  24.                 }.1point3acres缃
  25.                 for (int i = 1; i < m; i++) {
  26.                         for (int j = 1; j < n; j++) {. 鍥磋鎴戜滑@1point 3 acres
  27.                                 if (matrix[i][j] == 1) {
  28.                                         dp[i][j] = Math.min(dp[i - 1][j], Math.min(dp[i - 1][j - 1], dp[i][j - 1])) + 1; 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  29.                                 } else {
  30.                                         dp[i][j] = 0;
  31.                                 }
  32.                         }
  33.                 }
  34.                 int res = 0;
  35.                 for (int[] arr : dp) {
  36.                         for (int i : arr) {
  37.                                 res += i;
  38.                         }
  39.                 }. from: 1point3acres.com/bbs
  40.                 System.out.println(res);
  41.                 return res;. 鍥磋鎴戜滑@1point 3 acres
  42.         }
  43. }
复制代码
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2015-12-5 11:19:50 | 显示全部楼层
请问这个constructor就是直接将数字变为string吗?
回复 支持 反对

使用道具 举报

whisperty 发表于 2015-12-6 09:13:32 | 显示全部楼层
bobzhang2004 发表于 2015-12-5 11:17
写了下第一题的代码,欢迎指教
. visit 1point3acres.com for more.
你并没有算更大size的square啊
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2015-12-6 11:25:05 | 显示全部楼层
whisperty 发表于 2015-12-6 09:13
你并没有算更大size的square啊

dp[j] = Math.min(dp[i - 1][j], Math.min(dp[i - 1][j - 1], dp[j - 1])) + 1;
这个1代表的自己这个小得size, Math.min就是在找更大的size的square,最后是要全部相加的
回复 支持 反对

使用道具 举报

leonidas1573 发表于 2015-12-6 12:06:57 | 显示全部楼层
难度真的略高.第一题就好长....
回复 支持 反对

使用道具 举报

mchzh 发表于 2015-12-6 12:45:32 | 显示全部楼层
第一题的red cell和black cell是随机分布的?
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-8 12:14

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表