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


一亩三分地论坛

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

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

Google 6.2电面

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

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

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

您需要 登录 才可以下载或查看,没有帐号?获取更多干活,快来注册

x
直接上题

write a grid class. From 1point 3acres bbs

1. set the height and width. From 1point 3acres 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)。.鐣欏璁哄潧-涓浜-涓夊垎鍦
他又否了我的想法,说如果是一个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

查看全部评分

本帖被以下淘专辑推荐:

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

使用道具 举报

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

使用道具 举报

 楼主| successd 发表于 2016-6-3 07:00:01 | 显示全部楼层
改进后的代码
. From 1point 3acres bbs
  1. class Grid{
  2. private:
  3.         multiset<int> ms;
  4.         vector<vector<int>> grid;. more info on 1point3acres.com
  5. public:
  6.         Grid() {
  7.         }

  8.         void setGrid(int m, int n) {
  9.                 for (int i = 0; i < m; i++) {
  10.                         grid.push_back(vector<int>(n, 0));
  11.                 }
  12.                 for (int i = 0; i < m; i++)
  13.                 for (int j = 0; j < n; j++)
  14.                         ms.insert(0);
  15.         }-google 1point3acres
  16.         void display(){ // test
  17.                 for (int i = 0; i < grid.size(); i++) {
  18.                         for (int j = 0; j < grid[0].size(); j++) {
  19.                                 cout << grid[i][j] << " ";
  20.                         }
  21.                         cout << endl;-google 1point3acres
  22.                 }
  23.         }

  24.         void setValue(int i, int j, int value) { // O(logn). From 1point 3acres bbs
  25.                 if (grid.size() == 0)
  26.                         return;
  27.                 if (i < 0 || j < 0 || i >= grid.size() || j >= grid[0].size())
  28.                         return;
  29.                 ms.erase(ms.find(grid[i][j]));
  30.                 ms.insert(value);
    . 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  31.                 grid[i][j] = value;. Waral 鍗氬鏈夋洿澶氭枃绔,
  32.         }

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

  37. int main(). 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  38. {
  39.         Grid g;
  40.         g.setGrid(5, 5);
  41.         for (int i = 0; i < 100; i++) {
  42.                 g.setValue(random(5), random(5), random(100));
  43.                 g.display();
    . From 1point 3acres bbs
  44.                 cout << "maxvalue: " << g.getMaxValue() << endl << endl;
  45.         }
  46. } 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
复制代码
回复 支持 反对

使用道具 举报

 楼主| 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的帮助在哪里呢?
. from: 1point3acres.com/bbs
就是2D的seg tree. more info on 1point3acres.com

补充内容 (2016-6-3 15:03):. Waral 鍗氬鏈夋洿澶氭枃绔,
其实可以想象成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里取值比较大小就好了。

楼主Onsite没问题,不用担心!
.鏈枃鍘熷垱鑷1point3acres璁哄潧
补充内容 (2016-6-4 04:26):. 1point 3acres 璁哄潧
我基本同意楼主的想法,但是有点小问题: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
怎么达到 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. Waral 鍗氬鏈夋洿澶氭枃绔,
怎么达到 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()
. 1point3acres.com/bbs
补充内容 (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(){}. 鍥磋鎴戜滑@1point 3 acres
  4.     int height;.1point3acres缃
  5.     int width;
  6.     Map<Integer, Integer> map;// index -> value
  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);
  16.         if (map.containsKey(index)){. more info on 1point3acres.com
  17.             int oldValue = map.get(index); // get old value
  18.             Set oldValueSet = max.get(oldValue);. From 1point 3acres bbs
  19.             oldValueSet.remove(index);
  20.             if (oldValueSet.size()==0). visit 1point3acres.com for more.
  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);. 1point 3acres 璁哄潧
  28.                     return set;
  29.                 });
  30.         }. 鍥磋鎴戜滑@1point 3 acres
  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.     public int setIndex(int height, int width){
  41.         return  height * this.height + width;
  42.     }
  43.     public int getMax(){
  44.         return max.lastKey();
  45.     }

  46.     public static void main(String[] args) {. 1point 3acres 璁哄潧
  47.         Grid grid = new Grid(5,5);
  48.         grid.set(1,1,5);
  49.         grid.set(2,2,10);
  50.         grid.set(3,3,10);
    .鏈枃鍘熷垱鑷1point3acres璁哄潧
  51.         grid.set(4,4,15);
  52.         System.out.println(grid.getMax());    //15
  53.         grid.set(4,4,20);
  54.         System.out.println(grid.getMax());    //20
  55.         grid.set(4,4,15);
  56.         System.out.println(grid.getMax());    //15
  57.         grid.set(4,4,5);
  58.         grid.set(3,3,5);
    .鐣欏璁哄潧-涓浜-涓夊垎鍦
  59.         System.out.println(grid.getMax());    //10
  60.         grid.set(1,1,50);
  61.         System.out.println(grid.getMax());    //50
  62.         grid.set(1,1,0);. 1point 3acres 璁哄潧
  63.         grid.set(2,2,0);
  64.         grid.set(3,3,0);
  65.         grid.set(4,4,0);
  66.         System.out.println(grid.getMax());    //0. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  67.     }
  68. }
复制代码
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-8-19 15:54

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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