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

Neil_Acton

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

Neil_Acton

maihuabu 发表于 2016-8-5 23:48
就是这个，书里可能讲的更详细些。

能说下 segment tree 怎么实现么。
每个Leaf node里村什么？每个node记录的辅助变量又是什么呢？

我想了几种情况都没有很好的能够实现 random sample的。

Neil_Acton

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

hxtang

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

maihuabu

Neil_Acton 发表于 2016-8-23 03:31
能说下 segment tree 怎么实现么。
每个Leaf node里村什么？每个node记录的辅助变量又是什么呢？

面试的话我会写treap，AVL和RB Tree都太繁琐了，时间不够。

Neil_Acton

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

xihaokai1

jiaozhu200601 发表于 2016-8-22 03:24
请问为什么需要一个Node，感觉直接 Map也可以直接实现了，同时注意维持一个totalweight 的global variabl ...

因为方便remove呀。

Neil_Acton

我考了类似的题目。给了order(n)的思路后。面试官说不错就直接实现了。然后也没有follow up要 log(n)solution 就说实现不错就聊别的了

z928czzc

Fenwick tree居然还有人考，丧心病狂。。。

z928czzc

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