May 2009 - May 2017 论坛八周年-你的足迹,我的骄傲


一亩三分地论坛

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

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

Google 6.2电面

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

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

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

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

x
直接上题

write a grid class 鏉ユ簮涓浜.涓夊垎鍦拌鍧.

1. set the height and width
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)。悲剧). Waral 鍗氬鏈夋洿澶氭枃绔,

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

good luck. 1point 3acres 璁哄潧

评分

2

查看全部评分

本帖被以下淘专辑推荐:

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

使用道具 举报

nevets 发表于 2016-6-4 02:29:38 | 显示全部楼层
关注一亩三分地微博:
Warald
这题是经典的operation tradeoff。. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴

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

1. 维护一个正常的grid。set value O(1),取最大值O(NM),空间复杂度O(NM)。. 1point 3acres 璁哄潧
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 | 显示全部楼层
改进后的代码

  1. class Grid{
  2. private:
  3.         multiset<int> ms;
  4.         vector<vector<int>> grid;
  5. public:. 1point 3acres 璁哄潧
  6.         Grid() {
  7.         }

  8.         void setGrid(int m, int n) {
  9.                 for (int i = 0; i < m; i++) {. Waral 鍗氬鏈夋洿澶氭枃绔,
  10.                         grid.push_back(vector<int>(n, 0));
  11.                 }
    . From 1point 3acres bbs
  12.                 for (int i = 0; i < m; i++)
  13.                 for (int j = 0; j < n; j++)
  14.                         ms.insert(0);
  15.         }
  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] << " ";. 1point 3acres 璁哄潧
  20.                         }
  21.                         cout << endl;
  22.                 }
  23.         }

  24.         void setValue(int i, int j, int value) { // O(logn). from: 1point3acres.com/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;
  32.         }

  33.         int getMaxValue() { //O(logn)
  34.                 return *ms.rbegin();
  35.         }
  36. };. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷

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

使用道具 举报

 楼主| successd 发表于 2016-6-3 07:01:35 | 显示全部楼层
successd 发表于 2016-6-3 07:00.1point3acres缃
改进后的代码
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
#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):. 1point3acres.com/bbs
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):

. Waral 鍗氬鏈夋洿澶氭枃绔,用PriorityQueue update很慢啊
回复 支持 反对

使用道具 举报

ericLaw 发表于 2016-6-3 12:53:00 | 显示全部楼层
glaciersilent 发表于 2016-6-3 12:33
前面有童鞋提到用Binary index tree 或 segment tree, 这些都是求跟数列指定范围有关的问题,这题似乎是只 ...
. from: 1point3acres.com/bbs
主要是其他数据结构在处理这种题的时候总是会有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
. more info on 1point3acres.com
补充内容 (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里取值比较大小就好了。

楼主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. 1point3acres.com/bbs
楼主这个已经最优了吧,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. 1point 3acres 璁哄潧
怎么达到 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;-google 1point3acres
  6.     Map<Integer, Integer> map;// index -> value
  7.     TreeMap<Integer, Set<Integer>> max; // max -> index array
  8.     public Grid(int height, int width){. visit 1point3acres.com for more.
  9.         this.height = height;
  10.         this.width = width;
  11.         map = new HashMap<>();. Waral 鍗氬鏈夋洿澶氭枃绔,
  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)){
  17.             int oldValue = map.get(index); // get old value. 鍥磋鎴戜滑@1point 3 acres
  18.             Set oldValueSet = max.get(oldValue);
    .1point3acres缃
  19.             oldValueSet.remove(index);
  20.             if (oldValueSet.size()==0). visit 1point3acres.com for more.
  21.                 max.remove(oldValue);. Waral 鍗氬鏈夋洿澶氭枃绔,
  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->{. 1point3acres.com/bbs
  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;. from: 1point3acres.com/bbs
  42.     }
  43.     public int getMax(){
  44.         return max.lastKey();
  45.     }

  46.     public static void main(String[] args) {
  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);
  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
    .1point3acres缃
  57.         grid.set(4,4,5);
  58.         grid.set(3,3,5);. 鍥磋鎴戜滑@1point 3 acres
  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);
  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 下一条

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

custom counter

GMT+8, 2017-5-23 11:23

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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