一亩三分地论坛

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

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

Google 6.2电面

[复制链接] |试试Instant~ |关注本帖
successd 发表于 2016-6-3 06:57:12 | 显示全部楼层 |阅读模式

2016(4-6月) 码农类 硕士 全职@Google - 内推 - 技术电面 |Otherfresh grad应届毕业生

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

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

x
直接上题
. 鍥磋鎴戜滑@1point 3 acres
write a grid class. From 1point 3acres bbs

1. set the height and width. from: 1point3acres.com/bbs
2. set value at arbitrary point
3. get max value of the grid

一开始问我用什么结构存这个grid, 我说vector,他问为什么,我说可以random access。
然后做题,先直接brute-force, 2问O(1), 3问O(n^2)。他说取最大值太慢了,我就用了个priority_queue(他还问了我priority_queue<int, vector<int>, less<int>>参数的意思,说他不太清楚。。),2问变O(n^2),3问变O(1)。他说不行,set value太慢了,我说创建一个vector<int> maxVallue(m, 0),记录每行的最大值,这样2问复杂度是O(n), 3问是O(m)。. 1point 3acres 璁哄潧
他又否了我的想法,说如果是一个1*1000的grid复杂度还是很高。我说binary search tree可以都O(logn),他说有duplicate怎么办,后来我说用multiset,这样都是O(logn)并且可以重复。(PS: 因为太久没用multiset+时间太赶,用法写错了。。。multiset是不能改变值的,只能找到了然后删了再加新的,当时没时间了就跟set一样直接ms[grid[i][j]] = newValue了。。。应该是ms.erase(ms.find(grid[i][j])); ms.insert(newValue)。悲剧)

这一道题就把时间用光了,前前后后写了4种方法,最后那个也不知道达到他的要求没,估计药丸

good luck

评分

2

查看全部评分

nevets 发表于 2016-6-4 02:29:38 | 显示全部楼层
这题是经典的operation tradeoff。

假设矩阵大小N*M,那么(至少)有如下做法:

1. 维护一个正常的grid。set value O(1),取最大值O(NM),空间复杂度O(NM)。
2. 二维线段树维护最大值。set value O(logNlogM),取最大值O(1),空间复杂度O(NM)。
3. 自己建heap,然后建立一个从grid cell和heap index的双向映射,然后每次更新值的时候先从grid到heap的映射中找到heap对应的index,然后根据改大还是改小决定shift up或者shift down并且维护所有变更的index。set value O(log(NM)),取最大值O(1),空间复杂度O(NM)。
4. 记录最大值和最大值坐标,每次修改到最大值所在坐标的时候更新最大值。set value 最好情况O(1),最差情况O(NM),取最大值O(1),空间复杂度O(NM)。

之后就是考虑如何tradeoff。如果set数量远远大于query数量,那么set的复杂度就要尽量低,于是方法1是最好的;如果query数量远远大于set数量,或者说set数量远远低于矩阵大小,那么方法4是最好的,因为最大值被修改的可能性不高;如果query和set数量基本相同,而且和矩阵大小是一个数量级,那么方法3应该是首选。如果这是一个实际问题,那么可能所有的情况都会出现,所以可以根据现在query和set的比例情况自适应的选择最好的处理方式。

评分

1

查看全部评分

回复 支持 2 反对 0

使用道具 举报

forteller 发表于 2016-6-3 23:17:44 | 显示全部楼层
噼里啪啦一通说 没一个靠谱的。有几个谷歌的员工彻底懂那些个数据结构懂。楼主知道一维坐标和二维坐标的转换吗?在第X Y处的数可以存在一维数组的第X*列总数 + Y的位置。数组里的第S个数对应矩阵里的X=S/列总数 Y=S%列总数。这个方法可以让一维下标和二维坐标相互转换 达到降纬的目的。
回复 支持 0 反对 2

使用道具 举报

 楼主| successd 发表于 2016-6-3 07:00:01 | 显示全部楼层
改进后的代码
. 1point 3acres 璁哄潧
  1. class Grid{. From 1point 3acres bbs
  2. private:
  3.         multiset<int> ms;
  4.         vector<vector<int>> grid;
  5. public:. 1point 3acres 璁哄潧
  6.         Grid() {
  7.         }
  8. . 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  9.         void setGrid(int m, int n) {
  10.                 for (int i = 0; i < m; i++) {
  11.                         grid.push_back(vector<int>(n, 0));
  12.                 }
  13.                 for (int i = 0; i < m; i++)
  14.                 for (int j = 0; j < n; j++)
  15.                         ms.insert(0);
  16.         }
  17.         void display(){ // test
  18.                 for (int i = 0; i < grid.size(); i++) {
  19.                         for (int j = 0; j < grid[0].size(); j++) {. 鍥磋鎴戜滑@1point 3 acres
  20.                                 cout << grid[i][j] << " ";. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  21.                         }
  22.                         cout << endl;. Waral 鍗氬鏈夋洿澶氭枃绔,
  23.                 }. 鍥磋鎴戜滑@1point 3 acres
  24.         }. 1point 3acres 璁哄潧

  25.         void setValue(int i, int j, int value) { // O(logn)
  26.                 if (grid.size() == 0)-google 1point3acres
  27.                         return;
  28.                 if (i < 0 || j < 0 || i >= grid.size() || j >= grid[0].size())
  29.                         return;. From 1point 3acres bbs
  30.                 ms.erase(ms.find(grid[i][j]));
  31.                 ms.insert(value);
  32.                 grid[i][j] = value;
  33.         }

  34.         int getMaxValue() { //O(logn)
  35.                 return *ms.rbegin();
  36.         }
  37. };

  38. int main(). 鍥磋鎴戜滑@1point 3 acres
  39. {
  40.         Grid g;
  41.         g.setGrid(5, 5);
  42.         for (int i = 0; i < 100; i++) {
  43.                 g.setValue(random(5), random(5), random(100));
  44.                 g.display();
  45.                 cout << "maxvalue: " << g.getMaxValue() << endl << endl;
  46.         }
  47. }
复制代码
回复 支持 反对

使用道具 举报

 楼主| successd 发表于 2016-6-3 07:01:35 | 显示全部楼层

#define random(x) (rand()%x)
回复 支持 反对

使用道具 举报

edcent 发表于 2016-6-3 07:07:00 | 显示全部楼层
set长宽是可以调用多次的吗?
回复 支持 反对

使用道具 举报

 楼主| successd 发表于 2016-6-3 07:10:14 | 显示全部楼层
edcent 发表于 2016-6-3 07:07
set长宽是可以调用多次的吗?

应该就一次
回复 支持 反对

使用道具 举报

ericLaw 发表于 2016-6-3 07:10:30 | 显示全部楼层
这个题,应该是用binary indexed tree吧,电面问到这种难度。真是不知道说什么好了。
回复 支持 反对

使用道具 举报

wangmengcathy 发表于 2016-6-3 11:40:03 | 显示全部楼层
问烂了的seg tree题吧...打开geeks4geeks直接开抄
回复 支持 反对

使用道具 举报

wzy0791 发表于 2016-6-3 11:58:43 | 显示全部楼层
用一个HashMap和一个Stack做应该可行啊

补充内容 (2016-6-3 12:29):
Stack好像不行,还是需要PriorityQueue才能搞定最大值
回复 支持 反对

使用道具 举报

glaciersilent 发表于 2016-6-3 12:33:20 | 显示全部楼层
前面有童鞋提到用Binary index tree 或 segment tree, 这些都是求跟数列指定范围有关的问题,这题似乎是只问整个grid的最大值,那应用这两个structure的优势在哪儿?能不能再介绍一点思路呢?. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
另外我感觉楼主打得不错吧,可能面试的也没指望一下说出最优解,就是看看思路多不多。。还有这题有点不明白的是关于这题的难点是什么呢,如果已经知道了grid的最大值,那么后续修改grid的时候只要注意更新最大值就好了,那么难点是设计一个数据结构可以在最开始最快找到最大值?
回复 支持 反对

使用道具 举报

huai10 发表于 2016-6-3 12:34:31 | 显示全部楼层
quad tree, 突然感觉cs225 学好了面试无敌啊
回复 支持 反对

使用道具 举报

mingzhou1987 发表于 2016-6-3 12:38:51 | 显示全部楼层
stack的话恐怕不行吧,比如1,3,2插入顺序,stack top holds 3, erase 3后,stack top是1而不是2啊,不知道理解对不对。。
回复 支持 反对

使用道具 举报

huai10 发表于 2016-6-3 12:39:28 | 显示全部楼层
wzy0791 发表于 2016-6-3 11:58
用一个HashMap和一个Stack做应该可行啊

补充内容 (2016-6-3 12:29):

用PriorityQueue update很慢啊
回复 支持 反对

使用道具 举报

ericLaw 发表于 2016-6-3 12:53:00 | 显示全部楼层
glaciersilent 发表于 2016-6-3 12:33
前面有童鞋提到用Binary index tree 或 segment tree, 这些都是求跟数列指定范围有关的问题,这题似乎是只 ...

主要是其他数据结构在处理这种题的时候总是会有trade off between query and update. seg tree 或者bit就把两者的平均时间都归于log,我只是根据对方的反应猜测他们想要的答案。
回复 支持 反对

使用道具 举报

1peter 发表于 2016-6-3 12:59:26 | 显示全部楼层
huai10 发表于 2016-6-3 12:34
quad tree, 突然感觉cs225 学好了面试无敌啊

quadtree对于找max value的帮助在哪里呢?
回复 支持 反对

使用道具 举报

huai10 发表于 2016-6-3 13:10:00 | 显示全部楼层
1peter 发表于 2016-6-3 12:59 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
quadtree对于找max value的帮助在哪里呢?

就是2D的seg tree

补充内容 (2016-6-3 15:03):
其实可以想象成1D的, index变一下就好了,所以最后可以做到update O(logN), max O(1)
回复 支持 反对

使用道具 举报

handsomecool 发表于 2016-6-3 13:26:38 | 显示全部楼层
楼主这个已经最优了吧,update是O(logN), getMax是O(1) . 想不到怎么可以更快了。

我觉得可以直接用set不用multiset吧,把grid坐标当成pair存进去,写个comparator去grid里取值比较大小就好了。
. 鍥磋鎴戜滑@1point 3 acres
楼主Onsite没问题,不用担心!. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴

补充内容 (2016-6-4 04:26):
我基本同意楼主的想法,但是有点小问题:multiset erase(x)会删掉所有相同的元素, 比如我multiset里面有1 2 3 4 5 5 5, 其中一个5要被update成0的时候,erase(5)会删掉所有的5,所以不行,改成map记录出现的频率吧。

补充内容 (2016-6-4 04:27):
再者就是我觉得getMax是O(1), multiset.rbegin()我看API写的是constant time
回复 支持 反对

使用道具 举报

say543 发表于 2016-6-3 14:23:06 | 显示全部楼层
handsomecool 发表于 2016-6-3 13:26
楼主这个已经最优了吧,update是O(logN), getMax是O(1) . 想不到怎么可以更快了。. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷

我觉得可以直接用set ...


怎么达到 update 是o(logN) getMax 是o(1)? 是用 要getMax 要o(1) 一定要priorty queue 但是priority queue 不好update ?
回复 支持 反对

使用道具 举报

huai10 发表于 2016-6-3 15:04:32 | 显示全部楼层
say543 发表于 2016-6-3 14:23. From 1point 3acres bbs
怎么达到 update 是o(logN) getMax 是o(1)? 是用 要getMax 要o(1) 一定要priorty queue 但是priority q ...
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
我觉得其实直接把2D变成1D array, 然后上segtree 或者index tree 也ok, 最后应该update O(lgN), max 取顶点O(1)
回复 支持 反对

使用道具 举报

handsomecool 发表于 2016-6-3 16:19:05 | 显示全部楼层
say543 发表于 2016-6-3 14:23
怎么达到 update 是o(logN) getMax 是o(1)? 是用 要getMax 要o(1) 一定要priorty queue 但是priority q ...

楼主不是用的bst么? bst update是O(logN), getMax和getMin都可以O(1)吧,直接set.begin() / set.rbegin()

补充内容 (2016-6-3 16:21):
如果update 任意一个位置则是O(logN), 最大最小则可以直接拿到。   对吧? 为啥大家在讨论quadtree segment tree?
回复 支持 反对

使用道具 举报

readman 发表于 2016-6-3 22:05:32 | 显示全部楼层
handsomecool 发表于 2016-6-3 16:19
楼主不是用的bst么? bst update是O(logN), getMax和getMin都可以O(1)吧,直接set.begin() / set.rbegin( ...

这个?
  1. import java.util.*;

  2. public class Grid {
  3.     public Grid(){}
  4.     int height;
  5.     int width;
  6.     Map<Integer, Integer> map;// index -> value. more info on 1point3acres.com
  7.     TreeMap<Integer, Set<Integer>> max; // max -> index array
  8.     public Grid(int height, int width){
  9.         this.height = height;
  10.         this.width = width;
  11.         map = new HashMap<>();. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  12.         max  = new TreeMap<>();
  13.     }

  14.     public void set(int height, int width, int value) {
  15.         int index = setIndex(height, width);. Waral 鍗氬鏈夋洿澶氭枃绔,
  16.         if (map.containsKey(index)){
  17.             int oldValue = map.get(index); // get old value
  18.             Set oldValueSet = max.get(oldValue);.鐣欏璁哄潧-涓浜-涓夊垎鍦
  19.             oldValueSet.remove(index);
  20.             if (oldValueSet.size()==0)
  21.                 max.remove(oldValue);
  22.             if (max.containsKey(value))
  23.                 max.get(value).add(index);
  24.             else
  25.                 max.computeIfAbsent(value, k->{
  26.                     Set set = new HashSet<Integer>();
  27.                     set.add(index);
  28.                     return set;
  29.                 });
  30.         }
  31.         else {
  32.             max.computeIfAbsent(value, k->{
  33.                 Set set = new HashSet<Integer>();
  34.                 set.add(index);
  35.                 return set;
  36.             });
  37.         }
  38.         map.put(index,value);
  39.     }
  40. . 鍥磋鎴戜滑@1point 3 acres
  41.     public int setIndex(int height, int width){. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  42.         return  height * this.height + width;
  43.     }
  44.     public int getMax(){
  45.         return max.lastKey();
  46.     }

  47.     public static void main(String[] args) {
  48.         Grid grid = new Grid(5,5);
  49.         grid.set(1,1,5);
  50.         grid.set(2,2,10);
  51.         grid.set(3,3,10);
  52.         grid.set(4,4,15);. Waral 鍗氬鏈夋洿澶氭枃绔,
  53.         System.out.println(grid.getMax());    //15
  54.         grid.set(4,4,20);
  55.         System.out.println(grid.getMax());    //20
  56.         grid.set(4,4,15);. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  57.         System.out.println(grid.getMax());    //15
  58.         grid.set(4,4,5);
  59.         grid.set(3,3,5);
  60.         System.out.println(grid.getMax());    //10. visit 1point3acres.com for more.
  61.         grid.set(1,1,50);
  62.         System.out.println(grid.getMax());    //50. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  63.         grid.set(1,1,0);
  64.         grid.set(2,2,0);
  65.         grid.set(3,3,0);
  66.         grid.set(4,4,0);
    .鏈枃鍘熷垱鑷1point3acres璁哄潧
  67.         System.out.println(grid.getMax());    //0
  68.     }
  69. }
复制代码
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-8 20:09

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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