GG的面试。。感觉GG了。。

今天我电面也面了第一题，先随便写了一个n^2 logn的，结果想用two pointers改成n^2的卡住了……

lklk1986fa 发表于 2015-2-7 06:28
bless楼主，第三题最优可以做到update lgn  sum lgn, 参考2d segment tree

2d 树状数组就行了。 sum O(1).

第四题又是滑雪题。

Linzertorte 发表于 2015-2-11 04:21
2d 树状数组就行了。 sum O(1).

求解释Binary indexed tree 如何达到O(1)的，网上查了查好像是log(n)啊，reference http://en.wikipedia.org/wiki/Fenwick_tree

lklk1986fa 发表于 2015-2-11 05:07
求解释Binary indexed tree 如何达到O(1)的，网上查了查好像是log(n)啊，reference http://en.wikipedia. ...

哦。对。我弄错了。

tabrisjayson 发表于 2015-2-11 00:40
1 2 9
3 4 8
5 6 7

楼主，不应该是1,3,5,6,7,8,9这条path么。。。。

Linzertorte 发表于 2015-2-11 04:21
第四题又是滑雪题。

大牛。。。滑雪题？？能多透露点么

yapingchen1990 发表于 2015-2-12 02:52
大牛。。。滑雪题？？能多透露点么

http://poj.org/problem?id=1088

我问错了。。。其实我想问的是第五题。。抱歉

好喜欢考segment tree的样子...