求问Two Sigma店面一题如何解？

正解就是一楼说的self-balance binary search tree，比如AVL+maintain child sum (其实是segment tree的思想)。不过这种在interview基本不可能实现。。。一个简单的实现办法大概是hash+fenwick tree...

z928czzc 发表于 2016-8-29 02:18
正解就是一楼说的self-balance binary search tree，比如AVL+maintain child sum (其实是segment tree的思 ...

Treap还是可以实现的，其他的感觉两个小时也写不出来。。。

maihuabu 发表于 2016-8-30 01:12
Treap还是可以实现的，其他的感觉两个小时也写不出来。。。

Treap是期望高度log(n)吧，而不是guarantee（以及是类似quick sort vs merge sort了）。不过老实说，我觉得自己要interview实现一个bug-free Treap也够呛。。。

z928czzc 发表于 2016-8-29 02:18
正解就是一楼说的self-balance binary search tree，比如AVL+maintain child sum (其实是segment tree的思 ...

求问hash+bit的思路

33847682 发表于 2016-8-30 12:48
求问hash+bit的思路

hash+bit不是正解，不过也算是偏门解吧，其实就是楼主办法的一个简单改进，把辅助array变成bit就是了

首先定义辅助bit，对object进行hash。简单举例，就说hash到一个1-100 int吧(假定100足够大，没conflict)。然后定义一个大小为100的bit就OK了。和楼主办法的区别就是update bit比update array来的快。

偏门解比不过AVL+maintain subtree sum，老实说，interview直接用non-balancing BST + maintain substree sum来的或许靠谱一点。self-balancing大概是真记不住。

jy_121 发表于 2016-8-4 12:52
感谢分享，留名关注下。

大神真是无处不在...

maihuabu 发表于 2016-8-4 14:16
此题考查augmented data structure。你可以任选balanced binary search tree，每个node保存self和所有child ...

每次insert的时候树会inbalance吧，怎么rebalance？

没人问这到底是Uber还是twoSigma的店面题么？

hxtang 发表于 2016-8-23 04:52
整体的思路就是搞一个weight数组，weight[k]不为0就表示index k已经allocate给某个object了，为0就表示in ...

太他妈的屌了。我之前一直觉得bit就是线段树一个特例，但是没深想，就是感觉start end有点多余，递归写起来烦。
这个人链接写的太好了！

zyoppy008 发表于 2016-11-30 10:33
太他妈的屌了。我之前一直觉得bit就是线段树一个特例，但是没深想，就是感觉start end有点多余，递归写起 ...

那个slides里的coding也是很老练，虽然竞赛选手style比较重
觉得看过那个Slide以后我就没再觉得Segment tree需要记忆