一亩三分地论坛

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

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

新鲜Google面经

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

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

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

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

x
今天下午刚面的,
面试官听口音不像美国人,但是也听不出来是哪人 啊。。
做了个简单地自我介绍就开始出题了。
打开GOOGLE DOC
给一个二维矩阵,
实现两个方法,set(int x, int y), sum(int x, int y, int val)
set 方法设一个点的值, sum得到这一点到左上角(0, 0)点左右值的和。
(1)set多,sum少
(2)set少,sum多
. from: 1point3acres.com/bbs 第二种情况主要是要在set时就把sum算好,sum就是constent time了,但是set要注意更新。.鏈枃鍘熷垱鑷1point3acres璁哄潧

之前看到过这道题,大概准备了下,也没有细想,所以面的一般。
面试官全程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多少的问题。。。

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

使用道具 举报

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

感觉这题还是在考交流和tradeoff的,不是考数据结构。 鏉ユ簮涓浜.涓夊垎鍦拌鍧.

代码:
  1. #include <cstdio>
  2. #include <cstdlib>. 1point 3acres 璁哄潧
  3. #include <cstring>.1point3acres缃
  4. #include <iostream>
  5. #include <algorithm>
  6. #include <vector>

  7. using namespace std;

  8. #define print(x) cout << x << endl
  9. #define input(x) cin >> x

  10. typedef long long llint;
  11. .鏈枃鍘熷垱鑷1point3acres璁哄潧
  12. inline int lowbit(int x) { return x & (-x); }. 1point 3acres 璁哄潧

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

  15.     void init(int size) {
  16.         _tree.resize(size + 1);
  17.     }. 1point3acres.com/bbs

  18.     void add(int pos, int value) {. 鍥磋鎴戜滑@1point 3 acres
  19.         while (pos < _tree.size()) {
  20.             _tree[pos] += value;. 1point3acres.com/bbs
  21.             pos += lowbit(pos);
  22.         }
  23.     }
    -google 1point3acres

  24.     llint sum(int pos) {
  25.         llint res = 0;
  26.         while (pos > 0) {.鐣欏璁哄潧-涓浜-涓夊垎鍦
  27.             res += _tree[pos];
  28.             pos -= lowbit(pos);
  29.         }
  30.         return res;. from: 1point3acres.com/bbs
  31.     }

  32.     llint sum(int a, int b) {
  33.         return sum(b) - sum(a - 1);
  34.     }
  35. };

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

  38.     void init(int n, int m) {
  39.         _tree.resize(n + 1);
  40.         for (int i = 0; i <= n; i++) {
    .鐣欏璁哄潧-涓浜-涓夊垎鍦
  41.             _tree[i].init(m);
  42.         }
  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.     llint sum(int y, int x) {
  52.         llint res = 0;
  53.         while (y > 0) {
  54.             res += _tree[y].sum(x);
  55.             y -= lowbit(y);. 鍥磋鎴戜滑@1point 3 acres
  56.         }
  57.         return res;
  58.     }

  59.     llint sum(int y1, int x1, int y2, int x2) {
  60.         llint a = sum(y2, x2);
  61.         llint b = sum(y1 - 1, x1 - 1);
  62.         llint c = sum(y2, x1 - 1);
  63.         llint d = sum(y1 - 1, x2);

  64.         return a - c - d + b;
  65.     }
  66. };. visit 1point3acres.com for more.

  67. int main() {
  68.     freopen("input.txt", "r", stdin);. 1point 3acres 璁哄潧
  69.     int a, b, c, d, e;. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  70.     BITree_2D tree;. 1point3acres.com/bbs
  71.     while (input(a) && a != 3) {.鐣欏璁哄潧-涓浜-涓夊垎鍦
  72.         if (a == 0) {. more info on 1point3acres.com
  73.             input(b);
  74.             tree.init(b, b);
  75.         }
  76.         if (a == 1) {
  77.             scanf("%d%d%d", &b, &c, &d);
  78.             b++;
  79.             c++;
  80.             tree.add(c, b, d);
  81.         }
  82.         if (a == 2) {
  83.             scanf("%d%d%d%d", &b, &c, &d, &e);. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  84.             b++;
  85.             c++;
  86.             d++;
  87.             e++;
  88.             print(tree.sum(c, b, e, d));
  89.         }
  90.     }
  91.     return 0;
  92. }
复制代码
回复 支持 反对

使用道具 举报

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. From 1point 3acres bbs
楼主用的树状数组还是先求出每个子矩阵和的预处理方法?结果怎么样?

我都不懂树状数组是什么。。 直接就是存了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
  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]. visit 1point3acres.com for more.

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

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2017-4-29 14:57

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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