一亩三分地论坛

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

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

新鲜Google面经

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

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

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

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

x
今天下午刚面的,. visit 1point3acres.com for more.
面试官听口音不像美国人,但是也听不出来是哪人 啊。。
做了个简单地自我介绍就开始出题了。
打开GOOGLE DOC
给一个二维矩阵,
实现两个方法,set(int x, int y), sum(int x, int y, int val)
set 方法设一个点的值, sum得到这一点到左上角(0, 0)点左右值的和。
(1)set多,sum少. 鍥磋鎴戜滑@1point 3 acres
(2)set少,sum多
第二种情况主要是要在set时就把sum算好,sum就是constent time了,但是set要注意更新。

之前看到过这道题,大概准备了下,也没有细想,所以面的一般。
面试官全程Ok,感觉很冷淡。。

发面经攒RP,求on site。。
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷

评分

1

查看全部评分

本帖被以下淘专辑推荐:

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

使用道具 举报

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
和这题模型一样。

感觉这题还是在考交流和tradeoff的,不是考数据结构。

代码:
  1. #include <cstdio>
  2. #include <cstdlib>
  3. #include <cstring>
  4. #include <iostream>
  5. #include <algorithm>
  6. #include <vector>

  7. using namespace std;
  8. . 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  9. #define print(x) cout << x << endl
  10. #define input(x) cin >> x

  11. typedef long long llint;

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

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

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

  18.     void add(int pos, int value) {
  19.         while (pos < _tree.size()) {
  20.             _tree[pos] += value;. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  21.             pos += lowbit(pos);
  22.         }
  23.     }

  24.     llint sum(int pos) {. 1point3acres.com/bbs
  25.         llint res = 0;
  26.         while (pos > 0) {. more info on 1point3acres.com
  27.             res += _tree[pos];
  28.             pos -= lowbit(pos);
  29.         }
  30.         return res;-google 1point3acres
  31.     }. 1point3acres.com/bbs

  32.     llint sum(int a, int b) {
  33.         return sum(b) - sum(a - 1);
  34.     }
  35. };
  36. .鏈枃鍘熷垱鑷1point3acres璁哄潧
  37. struct BITree_2D {
  38.     vector<BITree> _tree;. 1point 3acres 璁哄潧

  39.     void init(int n, int m) {
  40.         _tree.resize(n + 1);
  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);. visit 1point3acres.com for more.
  48.             y += lowbit(y);
  49.         }
  50.     }

  51.     llint sum(int y, int x) {
  52.         llint res = 0;
  53.         while (y > 0) {. From 1point 3acres bbs
  54.             res += _tree[y].sum(x);
  55.             y -= lowbit(y);
  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);.1point3acres缃
  63.         llint d = sum(y1 - 1, x2);

  64.         return a - c - d + b;
  65.     }
  66. };

  67. int main() {
    . 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  68.     freopen("input.txt", "r", stdin);
  69.     int a, b, c, d, e;
  70.     BITree_2D tree;
  71.     while (input(a) && a != 3) {. 1point3acres.com/bbs
  72.         if (a == 0) {
  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.         }. more info on 1point3acres.com
  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.     }-google 1point3acres
  91.     return 0;
  92. }. From 1point 3acres bbs
复制代码
回复 支持 反对

使用道具 举报

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

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

使用道具 举报

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

使用道具 举报

 楼主| tianshaobo47 发表于 2015-10-5 09:19:04 | 显示全部楼层
hj867955629 发表于 2015-10-5 02:01. 1point 3acres 璁哄潧
楼主用的树状数组还是先求出每个子矩阵和的预处理方法?结果怎么样?

我都不懂树状数组是什么。。 直接就是存了SUM。。
面试官很冷淡,也不知道是不是他要的答案。很可能会悲剧。。
回复 支持 反对

使用道具 举报

hj867955629 发表于 2015-10-5 10:33:38 | 显示全部楼层
tianshaobo47 发表于 2015-10-5 09:19
我都不懂树状数组是什么。。 直接就是存了SUM。。. 1point 3acres 璁哄潧
面试官很冷淡,也不知道是不是他要的答案。很可能会悲 ...

记得更新哈!这样能判断要不要仔细学习下树状数组了。。
回复 支持 反对

使用道具 举报

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

直接学了吧
回复 支持 反对

使用道具 举报

darkwowgamer 发表于 2015-10-11 03:46:21 | 显示全部楼层
重复率很高啊.鐣欏璁哄潧-涓浜-涓夊垎鍦
http://www.1point3acres.com/bbs/thread-143755-1-1.html
回复 支持 反对

使用道具 举报

tangvictor 发表于 2015-10-19 04:59:58 | 显示全部楼层
贴个我写的用sum二维数组的方法。。
  1. class Array:. more info on 1point3acres.com
  2.         def __init__(self, A):. more info on 1point3acres.com
  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]

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

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-11 12:40

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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