楼主: feierqi
跳转到指定楼层
上一主题 下一主题
收起左侧

Google 11/10 onsite MTV

🔗
stellari 2015-11-20 13:32:25 | 只看该作者
全局:
feierqi 发表于 2015-11-20 05:03
第四题好多解法,我已开始说了个brute force的就是类似missing range然后找random,time是O(range of ar ...

我的思路和楼主可能差不多:

先数出每个missing range中的元素个数。比如上下界是[0 10000],数组是
A =【1 5 7 】
那么总共有4个missing range,其中元素个数分别是
Nmiss = [1 3 1 9993]
再对Nmiss的累加求和,得
Ncum = [1 4 5 9998]

用getRandom得到[0, 1]上的数字,再映射到[0 10000]上。比如我们得到的是3,那么就在Ncum中找第一个大于3的元素(即4)的位置。4是第2个元素,也就是说我们新生成的元素将在A的第1个元素1和第2个元素5之间。然后再调用一次getRandom,映射到[2, 4]上。即得最终要求的元素。


补充内容 (2015-11-21 11:33):
不用再调用第二次getRandom了。只要将第一次得到的数字3减去Ncum中“最后一个小于3的数字”,得2,然后取出[2 4]中第2个数字,即3就可以了。
回复

使用道具 举报

🔗
ohbrown 2015-11-21 07:40:31 | 只看该作者
全局:
请问第二题getSum(x,y)是算(0, 0) 到 (x, y)子矩阵所有值的和吗? 那个rb_tree需要自己实现吗? 还是直接调用就行呀? 比如STL的map什么的?
回复

使用道具 举报

🔗
zwcelesta 2015-11-22 14:29:54 | 只看该作者
全局:
stellari 发表于 2015-11-20 13:32
我的思路和楼主可能差不多:

先数出每个missing range中的元素个数。比如上下界是[0 10000],数组是

你这个应该是rand生成0到9998之间才行。
其实可以直接存好missing_range_start{0,2,6,8}
然后存个missing_range_cumlength{1,4,5,9998}
回复

使用道具 举报

🔗
maomaoxiong 2015-11-23 05:40:13 | 只看该作者
全局:
random这题就是用segment tree。
回复

使用道具 举报

🔗
LifeGoesOn 2015-11-27 09:04:46 | 只看该作者
全局:
楼主能不能讨论一下:

补充内容 (2015-11-27 09:07):
发太快了, #1 为什么用到LRU?是不是read each line 然后 找到longest sub string 就可以了? #2 能不能具体说说第二题两个方法是什么, 怎么用RBTree?

补充内容 (2015-11-27 09:08):
#4, 被random pick到的number 需不需要从missing range中取出来, 这样就需要split missing range
回复

使用道具 举报

🔗
LifeGoesOn 2015-11-27 15:16:16 | 只看该作者
全局:
LifeGoesOn 发表于 2015-11-27 09:04
楼主能不能讨论一下:

补充内容 (2015-11-27 09:07):

自己figure out 第二题了, 大概就是用个TreeMap<x, TreeMap<y, value>> 吧, LZ的题各种tricky啊
回复

使用道具 举报

🔗
JaySong 2015-11-29 05:25:29 | 只看该作者
全局:
先恭喜楼主拿到offer! 请教一个问题: 对于第二题要自己实现RB Tree吗,还是可以直接用java自带的TreeMap呢,谢谢楼主!
回复

使用道具 举报

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

本版积分规则

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