May 2009 - May 2017 论坛八周年-你的足迹,我的骄傲


一亩三分地论坛

 找回密码
 获取更多干活,快来注册

一亩三分地官方iOS手机应用下载
查看: 2224|回复: 12
收起左侧

新鲜Google面经

[复制链接] |试试Instant~ |关注本帖
tianshaobo47 发表于 2015-10-3 13:25:56 | 显示全部楼层 |阅读模式

2015(10-12月) 码农类 硕士 全职@Google - Other - 技术电面 |Otherfresh grad应届毕业生

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

您需要 登录 才可以下载或查看,没有帐号?获取更多干活,快来注册

x
今天下午刚面的,
面试官听口音不像美国人,但是也听不出来是哪人 啊。。. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
做了个简单地自我介绍就开始出题了。
打开GOOGLE DOC
给一个二维矩阵,
实现两个方法,set(int x, int y), sum(int x, int y, int val)
. from: 1point3acres.com/bbs set 方法设一个点的值, sum得到这一点到左上角(0, 0)点左右值的和。
(1)set多,sum少. Waral 鍗氬鏈夋洿澶氭枃绔,
(2)set少,sum多
第二种情况主要是要在set时就把sum算好,sum就是constent time了,但是set要注意更新。

之前看到过这道题,大概准备了下,也没有细想,所以面的一般。. 鍥磋鎴戜滑@1point 3 acres
面试官全程Ok,感觉很冷淡。。

发面经攒RP,求on site。。

评分

1

查看全部评分

本帖被以下淘专辑推荐:

zxy_snow 发表于 2015-10-3 13:44:57 | 显示全部楼层
关注一亩三分地微博:
Warald
竟然是树状数组,简直不能太坑。。。
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2015-10-3 13:54:00 来自手机 | 显示全部楼层
这题面的很多啊。求大神分享最优解,或者提供最优解链接
回复 支持 反对

使用道具 举报

Wizmann 发表于 2015-10-3 15:45:17 | 显示全部楼层
2D树状数组修改、查询都是O(logn * logn)的。。。所以并没有set/sum多少的问题。。。. 1point 3acres 璁哄潧

估计这题应该不是考这个的。
回复 支持 反对

使用道具 举报

Wizmann 发表于 2015-10-3 16:21:13 | 显示全部楼层
POJ 1195
和这题模型一样。

感觉这题还是在考交流和tradeoff的,不是考数据结构。
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
代码:
  1. #include <cstdio>. more info on 1point3acres.com
  2. #include <cstdlib>. 1point 3acres 璁哄潧
  3. #include <cstring>
  4. #include <iostream>
  5. #include <algorithm>.鏈枃鍘熷垱鑷1point3acres璁哄潧
  6. #include <vector>.鏈枃鍘熷垱鑷1point3acres璁哄潧

  7. using namespace std;

  8. #define print(x) cout << x << endl
  9. #define input(x) cin >> x
  10. . 1point3acres.com/bbs
  11. typedef long long llint;.鏈枃鍘熷垱鑷1point3acres璁哄潧

  12. inline int lowbit(int x) { return x & (-x); }

  13. struct BITree {
  14.     vector<llint> _tree;

  15.     void init(int size) {. From 1point 3acres bbs
  16.         _tree.resize(size + 1);. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  17.     }
  18. . 1point3acres.com/bbs
  19.     void add(int pos, int value) {
  20.         while (pos < _tree.size()) {
  21.             _tree[pos] += value;
  22.             pos += lowbit(pos);
  23.         }
  24.     }

  25.     llint sum(int pos) {
  26.         llint res = 0;
  27.         while (pos > 0) {
  28.             res += _tree[pos];. Waral 鍗氬鏈夋洿澶氭枃绔,
  29.             pos -= lowbit(pos);
  30.         }.1point3acres缃
  31.         return res;
  32.     }

  33.     llint sum(int a, int b) {
  34.         return sum(b) - sum(a - 1);
  35.     }
  36. };. From 1point 3acres bbs

  37. struct BITree_2D {
  38.     vector<BITree> _tree;

  39.     void init(int n, int m) {
  40.         _tree.resize(n + 1);. Waral 鍗氬鏈夋洿澶氭枃绔,
  41.         for (int i = 0; i <= n; i++) {. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  42.             _tree[i].init(m);
  43.         }
  44.     }

  45.     void add(int y, int x, int value) {
  46.         while (y < _tree.size()) {.鐣欏璁哄潧-涓浜-涓夊垎鍦
  47.             _tree[y].add(x, value);
  48.             y += lowbit(y);
  49.         }. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  50.     }
  51. 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  52.     llint sum(int y, int x) {-google 1point3acres
  53.         llint res = 0;
  54.         while (y > 0) {
  55.             res += _tree[y].sum(x);
  56.             y -= lowbit(y);. from: 1point3acres.com/bbs
  57.         }
  58.         return res;
  59.     }

  60.     llint sum(int y1, int x1, int y2, int x2) {
  61.         llint a = sum(y2, x2);
  62.         llint b = sum(y1 - 1, x1 - 1);
  63.         llint c = sum(y2, x1 - 1);
  64.         llint d = sum(y1 - 1, x2);
  65. . 鍥磋鎴戜滑@1point 3 acres
  66.         return a - c - d + b; 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  67.     } 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  68. };

  69. int main() {
  70.     freopen("input.txt", "r", stdin);
  71.     int a, b, c, d, e;
  72.     BITree_2D tree;. 鍥磋鎴戜滑@1point 3 acres
  73.     while (input(a) && a != 3) {
  74.         if (a == 0) {
  75.             input(b);
  76.             tree.init(b, b);. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  77.         }
  78.         if (a == 1) {.鏈枃鍘熷垱鑷1point3acres璁哄潧
  79.             scanf("%d%d%d", &b, &c, &d);
  80.             b++;
  81.             c++;
  82.             tree.add(c, b, d);
  83.         }
  84.         if (a == 2) {. 1point3acres.com/bbs
  85.             scanf("%d%d%d%d", &b, &c, &d, &e);
  86.             b++;
  87.             c++;
  88.             d++;.鏈枃鍘熷垱鑷1point3acres璁哄潧
  89.             e++;
  90.             print(tree.sum(c, b, e, d));
  91.         }
  92.     }
  93.     return 0;
  94. }
复制代码
回复 支持 反对

使用道具 举报

zxy_snow 发表于 2015-10-3 17:13:26 | 显示全部楼层
Wizmann 发表于 2015-10-3 16:21
POJ 1195
和这题模型一样。

你这个代码不还是树状数组么。。
回复 支持 反对

使用道具 举报

hj867955629 发表于 2015-10-5 02:01:17 | 显示全部楼层
楼主用的树状数组还是先求出每个子矩阵和的预处理方法?结果怎么样?
回复 支持 反对

使用道具 举报

 楼主| tianshaobo47 发表于 2015-10-5 09:19:04 | 显示全部楼层
hj867955629 发表于 2015-10-5 02:01
楼主用的树状数组还是先求出每个子矩阵和的预处理方法?结果怎么样?
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
我都不懂树状数组是什么。。 直接就是存了SUM。。
面试官很冷淡,也不知道是不是他要的答案。很可能会悲剧。。
回复 支持 反对

使用道具 举报

hj867955629 发表于 2015-10-5 10:33:38 | 显示全部楼层
tianshaobo47 发表于 2015-10-5 09:19
我都不懂树状数组是什么。。 直接就是存了SUM。。
面试官很冷淡,也不知道是不是他要的答案。很可能会悲 ...
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
记得更新哈!这样能判断要不要仔细学习下树状数组了。。
回复 支持 反对

使用道具 举报

Linzertorte 发表于 2015-10-5 11:10:57 | 显示全部楼层
hj867955629 发表于 2015-10-5 10:33
记得更新哈!这样能判断要不要仔细学习下树状数组了。。

直接学了吧
回复 支持 反对

使用道具 举报

darkwowgamer 发表于 2015-10-11 03:46:21 | 显示全部楼层
回复 支持 反对

使用道具 举报

tangvictor 发表于 2015-10-19 04:59:58 | 显示全部楼层
贴个我写的用sum二维数组的方法。。
  1. class Array:. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  2.         def __init__(self, A):
  3.                 self.sum = [[0] * (len(A[0]) + 1) for i in range(len(A) + 1)]
  4.                 self.A = A
  5.                 self.set(0, 0, self.A[0][0])

  6.         def set(self, i, j, value):
  7.                 self.A[i][j] = value.1point3acres缃
  8.                 for x in range(i + 1, len(self.sum)):
  9.                         for y in range(j + 1, len(self.sum)):
  10.                                 self.sum[x][y] = self.sum[x - 1][y] + self.sum[x][y - 1] + self.A[x - 1][y - 1] - self.sum[x - 1][y - 1]

  11.         def get(self, i, j):
  12.                 return self.sum[i + 1][j + 1]
复制代码
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-5-23 09:33

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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