近期论坛无法登录的解决方案


一亩三分地论坛

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

一亩三分地官方iOS手机应用下载
查看: 2438|回复: 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)
set 方法设一个点的值, sum得到这一点到左上角(0, 0)点左右值的和。
(1)set多,sum少
(2)set少,sum多. 1point 3acres 璁哄潧
第二种情况主要是要在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多少的问题。。。.1point3acres缃

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

使用道具 举报

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

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

代码:
  1. #include <cstdio>
  2. #include <cstdlib>. From 1point 3acres bbs
  3. #include <cstring>
  4. #include <iostream>
  5. #include <algorithm>
  6. #include <vector>.鐣欏璁哄潧-涓浜-涓夊垎鍦

  7. using namespace std;. from: 1point3acres.com/bbs

  8. #define print(x) cout << x << endl. 鍥磋鎴戜滑@1point 3 acres
  9. #define input(x) cin >> x

  10. typedef long long llint;

  11. inline int lowbit(int x) { return x & (-x); }
  12. . visit 1point3acres.com for more.
  13. struct BITree {
  14.     vector<llint> _tree;

  15.     void init(int size) {
  16.         _tree.resize(size + 1);
  17.     }
  18. . 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  19.     void add(int pos, int value) { 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  20.         while (pos < _tree.size()) {
  21.             _tree[pos] += value;
  22.             pos += lowbit(pos);
    -google 1point3acres
  23.         }
  24.     }

  25.     llint sum(int pos) {. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  26.         llint res = 0;
  27.         while (pos > 0) {
  28.             res += _tree[pos];
  29.             pos -= lowbit(pos);-google 1point3acres
  30.         }
  31.         return res;
  32.     }.鐣欏璁哄潧-涓浜-涓夊垎鍦

  33.     llint sum(int a, int b) {. from: 1point3acres.com/bbs
  34.         return sum(b) - sum(a - 1);. more info on 1point3acres.com
  35.     }
  36. };

  37. struct BITree_2D {
  38.     vector<BITree> _tree;
  39. . 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  40.     void init(int n, int m) {
  41.         _tree.resize(n + 1);
  42.         for (int i = 0; i <= n; i++) {
  43.             _tree[i].init(m);
  44.         }
  45.     }
  46. .1point3acres缃
  47.     void add(int y, int x, int value) {
  48.         while (y < _tree.size()) {. visit 1point3acres.com for more.
  49.             _tree[y].add(x, value);
  50.             y += lowbit(y);. From 1point 3acres bbs
  51.         }
  52.     }

  53.     llint sum(int y, int x) {
  54.         llint res = 0;
  55.         while (y > 0) {
  56.             res += _tree[y].sum(x);
  57.             y -= lowbit(y);
  58.         }
  59.         return res;
  60.     }

  61.     llint sum(int y1, int x1, int y2, int x2) {
  62.         llint a = sum(y2, x2);. from: 1point3acres.com/bbs
  63.         llint b = sum(y1 - 1, x1 - 1);
  64.         llint c = sum(y2, x1 - 1);
  65.         llint d = sum(y1 - 1, x2);

  66.         return a - c - d + b;
  67.     }
  68. };
  69. .1point3acres缃
  70. int main() {
  71.     freopen("input.txt", "r", stdin);
  72.     int a, b, c, d, e;
  73.     BITree_2D tree;
  74.     while (input(a) && a != 3) {
  75.         if (a == 0) {
  76.             input(b);
  77.             tree.init(b, b);
  78.         }
  79.         if (a == 1) {
  80.             scanf("%d%d%d", &b, &c, &d);
  81.             b++;
  82.             c++;
  83.             tree.add(c, b, d);
  84.         }
  85.         if (a == 2) {
  86.             scanf("%d%d%d%d", &b, &c, &d, &e);.鐣欏璁哄潧-涓浜-涓夊垎鍦
  87.             b++;. From 1point 3acres bbs
  88.             c++;
  89.             d++;
  90.             e++;
  91.             print(tree.sum(c, b, e, d));
  92.         }
  93.     }.鐣欏璁哄潧-涓浜-涓夊垎鍦
  94.     return 0;
  95. }
复制代码
回复 支持 反对

使用道具 举报

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
记得更新哈!这样能判断要不要仔细学习下树状数组了。。
-google 1point3acres
直接学了吧
回复 支持 反对

使用道具 举报

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.com/bbs
  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. . 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  12.         def get(self, i, j):
  13.                 return self.sum[i + 1][j + 1]
复制代码
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2017-6-23 04:56

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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