推荐:数据科学课程和书籍清单以及培训讲座


一亩三分地论坛

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

一亩三分地官方iOS手机应用下载
查看: 2480|回复: 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多
第二种情况主要是要在set时就把sum算好,sum就是constent time了,但是set要注意更新。
. Waral 鍗氬鏈夋洿澶氭枃绔,
之前看到过这道题,大概准备了下,也没有细想,所以面的一般。
面试官全程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 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
和这题模型一样。

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

代码:
  1. #include <cstdio>
  2. #include <cstdlib>
  3. #include <cstring>
  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. inline int lowbit(int x) { return x & (-x); }. 1point 3acres 璁哄潧

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

  14.     void init(int size) {
  15.         _tree.resize(size + 1);.鏈枃鍘熷垱鑷1point3acres璁哄潧
  16.     }

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

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

  31.     llint sum(int a, int b) {
  32.         return sum(b) - sum(a - 1);. Waral 鍗氬鏈夋洿澶氭枃绔,
  33.     }
  34. };

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

  37.     void init(int n, int m) {
  38.         _tree.resize(n + 1);
  39.         for (int i = 0; i <= n; i++) {. From 1point 3acres bbs
  40.             _tree[i].init(m);
  41.         }
  42.     }

  43.     void add(int y, int x, int value) {
  44.         while (y < _tree.size()) {
  45.             _tree[y].add(x, value);
  46.             y += lowbit(y);. Waral 鍗氬鏈夋洿澶氭枃绔,
  47.         }
  48.     }.鏈枃鍘熷垱鑷1point3acres璁哄潧

  49.     llint sum(int y, int x) {
    鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  50.         llint res = 0;
  51.         while (y > 0) {
  52.             res += _tree[y].sum(x);. 鍥磋鎴戜滑@1point 3 acres
  53.             y -= lowbit(y);
  54.         }
  55.         return res;
  56.     }

  57.     llint sum(int y1, int x1, int y2, int x2) {
  58.         llint a = sum(y2, x2);
  59.         llint b = sum(y1 - 1, x1 - 1);
  60.         llint c = sum(y2, x1 - 1);
  61.         llint d = sum(y1 - 1, x2);
  62. .1point3acres缃
  63.         return a - c - d + b;
  64.     }
  65. };. 鍥磋鎴戜滑@1point 3 acres

  66. int main() {
  67.     freopen("input.txt", "r", stdin);
  68.     int a, b, c, d, e;
  69.     BITree_2D tree;
  70.     while (input(a) && a != 3) {
  71.         if (a == 0) {
  72.             input(b);
  73.             tree.init(b, b);
  74.         }
  75.         if (a == 1) {
  76.             scanf("%d%d%d", &b, &c, &d);
  77.             b++;
  78.             c++;
  79.             tree.add(c, b, d);
  80.         }
  81.         if (a == 2) {
  82.             scanf("%d%d%d%d", &b, &c, &d, &e);
  83.             b++;
  84.             c++;
  85.             d++;
  86.             e++;
  87.             print(tree.sum(c, b, e, d));
  88.         } 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  89.     }
  90.     return 0;
  91. }
复制代码
回复 支持 反对

使用道具 举报

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. 1point3acres.com/bbs
我都不懂树状数组是什么。。 直接就是存了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)):. 鍥磋鎴戜滑@1point 3 acres
  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):. 1point 3acres 璁哄潧
  12.                 return self.sum[i + 1][j + 1]
复制代码
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-7-29 01:19

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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