5/16G家电面

昨天的电面，上来直接做题。题目是leetcode 308，面试小

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

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

，没有要求去implement。

一上来问得就是mutable的版本嘛?

edcent 发表于 2016-5-18 05:07
一上来问得就是mutable的版本嘛?

问的是mutable，但是首先问的是要求update function的时间复杂度是constant，sum的时间复杂度没有要求，然后问sum的时间复杂度是constant，update的时间复杂度没有要求。最后问如何balance

谢谢分享 lz面的是什么职位，顺便问结果如何啊

dgswh 发表于 2016-5-19 07:12
谢谢分享 lz面的是什么职位，顺便问结果如何啊

面的本科全职，第二天收到HR电话说电面过了，还没约onsite时间

请问楼主，logn的方法怎么弄的呢

Jimmy123 发表于 2016-5-29 11:07
请问楼主，logn的方法怎么弄的呢

不好意思，题目描述没说清楚，其实是说整个的2d vector的size是n*n, 时间复杂度的要求是O(logn * logn), 也就是说用2d的binary index tree去实现。

eming 发表于 2016-5-29 11:21
不好意思，题目描述没说清楚，其实是说整个的2d vector的size是n*n, 时间复杂度的要求是O(logn * logn),  ...

我的天，电面就用indexed tree， 之前没看过咋想出来

Jimmy123 发表于 2016-5-30 00:32
我的天，电面就用indexed tree， 之前没看过咋想出来

其实还好，面试官只是看你知不知道这个知识点，没有让implement，这还是很良心的。这个题我只做了immutable的版本，但是他要求update 和 sum两个都要有低于O(logn*n)的时间复杂度，那基本上可以猜出来是拿binary index tree这种形式去实现的了。

补充内容 (2016-5-30 00:48):
话说也是去年面intern的时候不知道binary index tree吃过这个亏，所以对这个知识点记得比较清楚吧。。。

eming 发表于 2016-5-30 00:47
其实还好，面试官只是看你知不知道这个知识点，没有让implement，这还是很良心的。这个题我只做了immutab ...

我最近才了解到这个，

加油