没结婚也能买房啊!大波士顿地区买房小tips

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投,内推多家公司面试
[Google级团队]:实时大数据分析领域践行者
北京/深圳-大数据/搜索/机器学习职位
日志易机器大数据行业践行者Web/大数据/机器学习等职位-北京or深圳
把贵司招聘信息放这里
查看: 924|回复: 21
收起左侧

[找工就业] 谷歌新鲜跪经

[复制链接] |试试Instant~ |关注本帖
yuqiche18768 发表于 2018-2-23 04:37:10 | 显示全部楼层 |阅读模式

2018(1-3月)-[]EE硕士+<3个月短暂实习/全职 - 内推|Chicago 码农类General全职@Googlefresh grad应届毕业生

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

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

x
刚刚结束,一个三哥,上来直接放题,给一堆predefined intervals,然后输入是一个integer,问在这些intervals 的 range中能否找到该integer,
例如:
[10,39],[112,139],[77,77]
20->true
77->true
199->false
由于楼主刷题刷太多,思维定势,直接说sort然后binary search,但面试官说直接bruce force 才O(n),然后问我能不能在O(lgn)时间里实现,
能不能在O(1)时间里实现,那个intervals是predefined,之前他没说拿什么数据结构存放,我说如果是BST结构,类似TreeMap之类的,是可以做到
O(lgn),但是O(1)impossible. 然后说给我两个function,一个做预处理,一个做binary search,让我实现,他不考虑预处理function里面的时间,. From 1point 3acres bbs
貌似是说给个sort的array,然后让做binary search,写完后,问了如果intervals可以overlap怎么办。
例如:
[10,199],[112,139],[77,77]
199->true
这时就有点纠结,有点钻到题里去了,觉得就是要我用binary search实现,想了大概10分钟左右,说用两个binary search,方向不同。自己也感觉这-google 1point3acres
方法不太行。然后他说时间到了,问了面试官问题直接走人。

总的来说,还是交流的问题,follow up个人感觉可以先做merge intervals,然后再binary search,应该先问面试官是否可以merge intervals,不行再来
binary search。唉,感觉基本功和交流理解不行,题刷的再多,找工作也好难。。。祝大家2018找工作学习生活一切顺利~


补充内容 (2018-2-23 22:59):
这道题如果什么限定条件不加,输入直接List + int, O(n)不能再少。面试官问O(lgn)和O(1)只是打破常规刷题模式,看你能不能get到他的点,并不代表真的就要让你实现,面试中明确对方的意图很重要,也怪自己经验少。。
qzhouayi 发表于 2018-2-23 05:01:06 | 显示全部楼层
如果用背包实现的话,用一个背包去预处理,是不是就可以o(1)了
回复 支持 反对

使用道具 举报

 楼主| yuqiche18768 发表于 2018-2-23 05:15:11 | 显示全部楼层
qzhouayi 发表于 2018-2-23 05:01
如果用背包实现的话,用一个背包去预处理,是不是就可以o(1)了

有道理,现在想想是可以。。。
回复 支持 反对

使用道具 举报

wcg 发表于 2018-2-23 05:33:01 | 显示全部楼层
楼主没让算预处理时间就都读到set里面查询就是O(1)amertize 也是 constant啊
回复 支持 反对

使用道具 举报

 楼主| yuqiche18768 发表于 2018-2-23 05:42:27 | 显示全部楼层
wcg 发表于 2018-2-23 05:33
楼主没让算预处理时间就都读到set里面查询就是O(1)amertize 也是 constant啊
. more info on 1point3acres.com
O(1)的当时确实没想到,最后他叫我实现的是Binary search,应该是认为我没想到O(1)的解法才这样说的吧
回复 支持 反对

使用道具 举报

charleszhou 发表于 2018-2-23 05:53:34 | 显示全部楼层
qzhouayi 发表于 2018-2-23 05:01
如果用背包实现的话,用一个背包去预处理,是不是就可以o(1)了

请教一下这个背包应该怎么处理呢?
回复 支持 反对

使用道具 举报

Believers 发表于 2018-2-23 05:54:12 | 显示全部楼层
qzhouayi 发表于 2018-2-23 05:01
如果用背包实现的话,用一个背包去预处理,是不是就可以o(1)了
. 鍥磋鎴戜滑@1point 3 acres
请问下怎么用背包实现?
回复 支持 反对

使用道具 举报

ouyangivan 发表于 2018-2-23 06:09:13 | 显示全部楼层
同问如何用背包实现。
回复 支持 反对

使用道具 举报

closewen 发表于 2018-2-23 06:10:23 | 显示全部楼层
用Segmentation Tree吧, Bit Indexed Tree。狗家真会考这种题。。。看来得好好准备下了
回复 支持 反对

使用道具 举报

diefunction 发表于 2018-2-23 07:15:23 | 显示全部楼层
wcg 发表于 2018-2-23 05:33
楼主没让算预处理时间就都读到set里面查询就是O(1)amertize 也是 constant啊

这个set怎么预处理才能O(1) 呀, 想不出来。
回复 支持 反对

使用道具 举报

rapha 发表于 2018-2-23 07:46:07 | 显示全部楼层
同问什么是背包处理,谢谢!
回复 支持 反对

使用道具 举报

zhtpandog 发表于 2018-2-23 09:42:36 | 显示全部楼层
如果真的要说预处理而不计空间复杂度的话,可以先过一遍建立[min,max]范围内的hashmap,key is int, value is true or false: {1:true, 2:true, 3:false, ....99999:false}之类的。然后query不就是O(1)了么
回复 支持 反对

使用道具 举报

yiliaobailiao 发表于 2018-2-23 09:51:45 | 显示全部楼层
closewen 发表于 2018-2-23 06:10
用Segmentation Tree吧, Bit Indexed Tree。狗家真会考这种题。。。看来得好好准备下了

segment tree查询也得是logn吧?
回复 支持 反对

使用道具 举报

xljob 发表于 2018-2-23 10:07:14 | 显示全部楼层
假设数据一共范围10000,那就开一个10000大小的array,就完了,但很消耗空间
回复 支持 反对

使用道具 举报

xljob 发表于 2018-2-23 10:09:37 | 显示全部楼层
假设数据一共范围10000,那就开一个10000大小的array,就完了,但很消耗空间…线段树也不是o1啊
回复 支持 反对

使用道具 举报

closewen 发表于 2018-2-23 10:31:02 | 显示全部楼层
yiliaobailiao 发表于 2018-2-23 09:51. from: 1point3acres.com/bbs
segment tree查询也得是logn吧?

是啊,不过O(1)也只能是index全存Hash或Array了吧。少占些空间,又比O(n)快的,那也就是segment tree了吧。虽然线段树还在学。。。
回复 支持 反对

使用道具 举报

mmymichael 发表于 2018-2-23 11:23:42 | 显示全部楼层
u should practice more i think, for phone interviews u need to finish at least two medium-hard questions to get to onsite for google and fb
回复 支持 反对

使用道具 举报

greynut 发表于 2018-2-23 16:49:17 | 显示全部楼层
我觉得这题其实有点难。。。 鏉ユ簮涓浜.涓夊垎鍦拌鍧.

同问背包处理是什么
-google 1point3acres
粗略一看也只能想到binary searching tree 和 hashset 硬来. Waral 鍗氬鏈夋洿澶氭枃绔,

至于有overlap 肯定是要合并树里的节点 想想逗觉得好复杂
回复 支持 反对

使用道具 举报

 楼主| yuqiche18768 发表于 2018-2-23 22:39:59 | 显示全部楼层
greynut 发表于 2018-2-23 16:49
我觉得这题其实有点难。。。

同问背包处理是什么

背包问题来源于DP,一般的DP array里存的是子问题的解。背包问题是DP的一个特例,就是用值进行DP,DP array里存的是问题的值。背包处理在这是指,把interval当成背包,类似[10,1000],就开个boolean数组,长度为1000,0-9为false,10-999为true
回复 支持 反对

使用道具 举报

wcg 发表于 2018-2-23 22:41:36 | 显示全部楼层
diefunction 发表于 2018-2-23 07:15
这个set怎么预处理才能O(1) 呀, 想不出来。

读进去就好了吧查询不是constant?,我理解错了?怎么大家都觉得这题要什么背包,线段树
回复 支持 反对

使用道具 举报

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

关闭

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

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2018-4-21 21:52

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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