一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 882|回复: 8
收起左侧

Google电面

[复制链接] |试试Instant~ |关注本帖
mayingjie116 发表于 2014-12-18 04:46:10 | 显示全部楼层 |阅读模式

2014(10-12月) 码农类 硕士 全职@Google - 内推 - 技术电面 |Other

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
上来直接给题,实在太直接了。。。. From 1point 3acres bbs
float []a = {  .... };. From 1point 3acres bbs
float w = 0.28;-google 1point3acres
output: W大小的区间内最多能包含的float数量。. more info on 1point3acres.com
大家有思路吗。。
感觉对面在忙别的,45分钟到了就挂了。
lklk1986fa 发表于 2014-12-18 05:36:36 | 显示全部楼层
请问楼主,array 是sorted 的么, 能否举个列子w区间是怎么定义的呢,多谢
回复 支持 反对

使用道具 举报

GabrielYeah 发表于 2014-12-18 07:17:38 | 显示全部楼层
我的一个想法是先Sort,然后对每一个元素作为中点,算出它能覆盖到的范围,然后往两边做Binary Search,这样的话时间复杂度是O(n log n)。不知道有没有更好的。.1point3acres缃

补充内容 (2014-12-18 07:42):
刚刚跟同学讨论了一下,sort之后可以不用两边二分查,维护一个长度为W的动态窗口就好,这样搜一遍就可以,除去sort之外,O(n)就可以了
回复 支持 反对

使用道具 举报

 楼主| mayingjie116 发表于 2014-12-18 09:54:04 | 显示全部楼层
lklk1986fa 发表于 2014-12-18 05:36. visit 1point3acres.com for more.
请问楼主,array 是sorted 的么, 能否举个列子w区间是怎么定义的呢,多谢
.鐣欏璁哄潧-涓浜-涓夊垎鍦
array是unsorted,w的定义的话比如float w = 0.28, 可以随便取区间但是长度都是0.28,需要求出能够包含在此区间长度的最多的number。
回复 支持 反对

使用道具 举报

 楼主| mayingjie116 发表于 2014-12-18 09:58:11 | 显示全部楼层
GabrielYeah 发表于 2014-12-18 07:17
我的一个想法是先Sort,然后对每一个元素作为中点,算出它能覆盖到的范围,然后往两边做Binary Search,这 ...

先sort没问题。但是不能把元素作为中点。我的想法是遍历,每次把元素作为左边界,设为i,求出i能够到达的最远的number,设为j,update最大值为j-i+1。但是不知道怎么把复杂度弄成O(n)。
你说的维护窗口的具体是怎么实现的?求指导。
回复 支持 反对

使用道具 举报

lqs4188980 发表于 2014-12-18 10:34:49 | 显示全部楼层
mayingjie116 发表于 2014-12-18 09:58
先sort没问题。但是不能把元素作为中点。我的想法是遍历,每次把元素作为左边界,设为i,求出i能够到达的 ...

大概双指针可以维护这个窗口。

两个指针初始都从第一个元素出发,移动右指针直到超出窗口大小,用右指针的index减去左指针的index,得到一个该窗口内元素个数,更新maximum; 之后移动左指针直到再次满足窗口大小,继续移动右指针到超出窗口大小,更新maximum.
回复 支持 反对

使用道具 举报

 楼主| mayingjie116 发表于 2014-12-18 12:02:07 | 显示全部楼层
lqs4188980 发表于 2014-12-18 10:34
大概双指针可以维护这个窗口。. more info on 1point3acres.com

两个指针初始都从第一个元素出发,移动右指针直到超出窗口大小,用右指 ...
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
我演算了一下,这是个很棒的思路。
在i移动时,可以保证i-j窗口内包含的数字个数不超过maximum。
回复 支持 反对

使用道具 举报

GabrielYeah 发表于 2014-12-18 14:48:46 | 显示全部楼层
mayingjie116 发表于 2014-12-18 09:58. visit 1point3acres.com for more.
先sort没问题。但是不能把元素作为中点。我的想法是遍历,每次把元素作为左边界,设为i,求出i能够到达的 ...

嗯,前面没考虑好,中点是不行的,动态窗口就是楼上说的方法。
回复 支持 反对

使用道具 举报

 楼主| mayingjie116 发表于 2014-12-18 22:37:41 | 显示全部楼层
GabrielYeah 发表于 2014-12-18 14:48
嗯,前面没考虑好,中点是不行的,动态窗口就是楼上说的方法。

很棒的思路!
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-8 14:23

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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