📣 VIP通行证夏日特惠 限时立减$68
楼主: gougou9903
跳转到指定楼层
上一主题 下一主题
收起左侧

谷歌google跪经

 
🔗
zzgzzm 2017-1-5 13:12:28 | 只看该作者
全局:
ws775901 发表于 2017-1-4 04:14
jin chang kan dao ceng zhu zai LC zhong de tie zi, mo bai yi xia.

真不敢当,共同讨论而已
回复

使用道具 举报

🔗
littleMiao 2017-1-6 07:49:53 | 只看该作者
全局:
zzgzzm 发表于 2017-1-5 13:12
真不敢当,共同讨论而已

问下大神,对于最后一题的follow up除了楼主说的线段树还有什么思路吗?
回复

使用道具 举报

🔗
littleMiao 2017-1-6 07:49:58 | 只看该作者
全局:
zzgzzm 发表于 2017-1-5 13:12
真不敢当,共同讨论而已

问下大神,对于最后一题的follow up除了楼主说的线段树还有什么思路吗?
回复

使用道具 举报

🔗
zzgzzm 2017-1-7 21:38:41 | 只看该作者
全局:
littleMiao 发表于 2017-1-6 07:49
问下大神,对于最后一题的follow up除了楼主说的线段树还有什么思路吗?

这个按以给定weight为概率返回ID的问题应该是个高频题了。我写了一个解在第14层:用给定的weight直接构造一个pdf (probability distribution function)就是一个sorted array with max value = 1.0。然后生成一个[0, 1]之间的随机数看落到哪个区间。这个时间是O(N), 而且对于weight为double一般类型(未考虑overflow问题,但这不影响算法本质)。

我不熟悉segment tree,但从描述楼主上来说应该差不多的算法。
回复

使用道具 举报

🔗
lisuiyi 2017-1-14 08:15:03 | 只看该作者
全局:
第一题 感觉可以用DP和二分

DP 解法思路: 假设我们有 N 个 空隙可以继续放 K个加油站,  F(N,K) 表示最终答案, 即 把 K 个加油站放到这N 个空隙中 的最小的最大间距, 那么 F(N,K) 就等于 最后一个空隙 放 0 个, 1个,2个,一直到k 个的 所有情况的最小情况, F(N,K) =min( max ( F(N-1,K) , G0), max(F(N-1,K-1), G1), max(F(N-1,K-2), G3), ............ ); 其中G2 表示 最后一个空隙中放了2个加油站之后最大的空隙, 这个可以直接算出来, 因为在一个空隙中放几个加油站, 当然是越平均越好。 O(N×K×K)

二分发思路: 对结果进行二分, 假设最小的最大空隙是X , 然后我们把 K个加油站试图放到N 个空隙中 但是必须保证新的空隙不能大于 X, 如果我们经过努力把 K个全部放进去了, 结果还是有空隙大于X,说明X 太小了, 下次就二分大的值; 如果我们遍历完了所有的空隙, 但是还剩下加油站, 或者刚好把加油站用完, 说明X 太大了, 下次就二分大的数字。 O(log(Len) *N) Len 为一开始的输入的最大空隙
回复

使用道具 举报

全局:
zzgzzm 发表于 2016-11-30 07:26
感谢指正!我的确忽略了这一点,没有全面测试   :-(
Line7应该改为:

不好意思 没有看懂你这个reservoir sampling....大致意思就是去除invalid的棋子,然后随机选一个。 那比如说现在总共有1,2,3,4种糖果, 其中3是invalid的, 我随机的时候挑到了3 怎么办呢? 多谢。。
回复

使用道具 举报

全局:
spwahaha 发表于 2016-11-24 13:05
其中一种方法是先放一个
XOX                                                          XOO
OXO 这种 ...

Hi  请问一下你的idea是, 先随机出棋盘上任意一个位置,以它开始放置一个XOX
                                                                                                            OXO
然后再随机DFS其他所有位置嘛?
回复

使用道具 举报

🔗
zzgzzm 2017-2-2 06:32:33 | 只看该作者
全局:
小A要当码农 发表于 2017-2-2 03:27
不好意思 没有看懂你这个reservoir sampling....大致意思就是去除invalid的棋子,然后随机选一个。 那比 ...

若是invalid 的话自动increments 变为下一个。(相当于1,2,4作抽样。3被4吸收了)
回复

使用道具 举报

全局:
zzgzzm 发表于 2017-2-2 06:32
若是invalid 的话自动increments 变为下一个。(相当于1,2,4作抽样。3被4吸收了)

这样的话没有办法保证1,2,4概率是相同的吧?  1,2是 1/4, 4是1/2
回复

使用道具 举报

🔗
zzgzzm 2017-2-3 09:54:39 | 只看该作者
全局:
小A要当码农 发表于 2017-2-2 06:37
这样的话没有办法保证1,2,4概率是相同的吧?  1,2是 1/4, 4是1/2

抽样时还是按连续ID:1,2,3来做,只不过当抽到3时将数字3改为4而已。实际上只是ID上的manipulation
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

>
快速回复 返回顶部 返回列表