热腾腾的Google面经

去他大爷的保密协议，趁着记忆还在写一个回馈大家

您好！
本帖隐藏的内容需要积分高于 388 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 388 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

mengmeng88717 发表于 2016-6-29 11:59
TreeMap这样呢？
外层key是x，内层key是y

我觉得差不多，这应该是他expected的解法

换成C++就是用
map<int, map<int, int>> 外层k是x，内层k是y,最里层是value 加的话直接index到那个entry加  求和的话两层循环外层从mp.lowerbound(x1) 遍历到mp.upperbound(x2), 内层 从mp.lowerbound(y1) 遍历到 mp.lowerbound(y2)累加起来，还是学艺不精啊。。以后有机会再战了

hychin 发表于 2016-6-29 12:20
我觉得差不多，这应该是他expected的解法

换成C++就是用

我想问一下 map套map可以， 那vector套vector不一样可以嘛。。。vector就保持sorted 插入的时候binary search插入 这样子貌似更快？内存找到index range可以直接累加 好像，c++ map iterator 移动复杂度并不是o(1) 这个我不确定，好像distance不是o(1) 因为他毕竟是树结构的， 两个index直接移动反而没有vector两个index直接移动快？

补充内容 (2016-10-2 16:45):
但是vector插入复杂度太高太坑爹了 综合来说还是map好 maybe

第一题可以用treemap
1） add(x, y, value)  --> treemap.put(x * col + y, value)
2)   get sum(x1, y1, x2, y2) --> treemap.subMap(x1 * col + y1, true, x2 * col + y2) 然后遍历submap累加下结果

add是logn，getSum应该是这个range里实际存储了多少个值＊logn
觉得这个题和稀疏矩阵乘法有点类似，原则就是不储存空值
欢迎讨论～

补充内容 (2016-6-29 10:19):
treemap.subMap(x1 * col + y1, true, x2 * col + y2， true)打漏了一个参数

请问楼主第一题用什么方法呢？我只能想到O(n)的方法了，n是有value的坐标的数目。谢谢！

第一题用ArrayList + BIT ? 这样可以实现Add和get都是 O(logn)。

chenzhan171 发表于 2016-6-29 07:17
第一题用ArrayList + BIT ? 这样可以实现Add和get都是 O(logn)。

fenwick树有范围的吧....
第一题我觉得Segment Tree 2D吧...不过代码写的时候没fenwick好写.. 但理论上来说fenwick能做的 线段树都能

mengmeng88717 发表于 2016-6-29 10:19
第一题可以用treemap
1） add(x, y, value)  --> treemap.put(x * col + y, value)
2)   get sum(x1, y1 ...

请问, 不知道col的情况下...怎么做...第一题不是说没边界么..

第一题咋解啊？

readman 发表于 2016-6-29 10:51
请问, 不知道col的情况下...怎么做...第一题不是说没边界么..

我的理解是平面很大而有内存限制，请楼主澄清下知不知道col？

mengmeng88717 发表于 2016-6-29 11:24
我的理解是平面很大而有内存限制，请楼主澄清下知不知道col？

不知道col的边界的，我画个原图给你看就明白了

一个这样子的平面
------------------------------------------------------------》 unlimit bound
|
|
|
|
|
|
|
|
|

mengmeng88717 发表于 2016-6-29 11:24
我的理解是平面很大而有内存限制，请楼主澄清下知不知道col？

不知道col的边界的，我画个原图给你看就明白了

一个这样子的平面
------------------------------------------------------------》 unlimit bound
|
|
|
|
|
|
|
|
\|/
unlimit bound