Mock interview for data science
仅限两天:购买DS501或者DS601,全站课程15% off

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
有你有策略
微策略(MicroStrategy)
2019校园招聘火热进行中
E轮2.5亿美元融资
K12教育独角兽一起作业诚聘
机器学习/数据统计/教育等职位
码农求职神器Triplebyte:
不用海投
内推多家公司面试
高效直聘+内推,70%面试率
AI帮你免费完善简历
直击全美十万个科技职位
坐标湾区
DreamCraft创始团队
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
把贵司招聘信息放这里
查看: 1321|回复: 21
收起左侧

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

[复制链接] |试试Instant~
我的人缘0
yuqiche18768 发表于 2018-2-23 04:37:10 | 显示全部楼层 |阅读模式
该内容以做模糊处理,您需要登录后才可查看. 登录 | Sign Up 注册获取更多干货
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (20)
 
 
0% (0)  踩

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之类的,是可以做到-baidu 1point3acres
O(lgn),但是O(1)impossible. 然后说给我两个function,一个做预处理,一个做binary search,让我实现,他不考虑预处理function里面的时间,
貌似是说给个sort的array,然后让做binary search,写完后,问了如果intervals可以overlap怎么办。
例如:
[10,199],[112,139],[77,77]
199->true
这时就有点纠结,有点钻到题里去了,觉得就是要我用binary search实现,想了大概10分钟左右,说用两个binary search,方向不同。自己也感觉这
方法不太行。然后他说时间到了,问了面试官问题直接走人。

总的来说,还是交流的问题,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到他的点,并不代表真的就要让你实现,面试中明确对方的意图很重要,也怪自己经验少。。

上一篇:关于测试跟QA
下一篇:fb实习现在什么情况
我的人缘0
qzhouayi 发表于 2018-2-23 05:01:06 | 显示全部楼层
如果用背包实现的话,用一个背包去预处理,是不是就可以o(1)了
回复

使用道具 举报

我的人缘0
 楼主| yuqiche18768 发表于 2018-2-23 05:15:11 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (20)
 
 
0% (0)  踩
qzhouayi 发表于 2018-2-23 05:01
如果用背包实现的话,用一个背包去预处理,是不是就可以o(1)了

有道理,现在想想是可以。。。
回复

使用道具 举报

我的人缘0
wcg 发表于 2018-2-23 05:33:01 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  77% (7)
 
 
22% (2)  踩
楼主没让算预处理时间就都读到set里面查询就是O(1)amertize 也是 constant啊
回复

使用道具 举报

我的人缘0
 楼主| yuqiche18768 发表于 2018-2-23 05:42:27 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (20)
 
 
0% (0)  踩
wcg 发表于 2018-2-23 05:33
楼主没让算预处理时间就都读到set里面查询就是O(1)amertize 也是 constant啊

O(1)的当时确实没想到,最后他叫我实现的是Binary search,应该是认为我没想到O(1)的解法才这样说的吧
回复

使用道具 举报

我的人缘0
charleszhou 发表于 2018-2-23 05:53:34 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  98% (154)
 
 
1% (3)  踩
qzhouayi 发表于 2018-2-23 05:01
如果用背包实现的话,用一个背包去预处理,是不是就可以o(1)了

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

使用道具 举报

我的人缘0
Believers 发表于 2018-2-23 05:54:12 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  91% (42)
 
 
8% (4)  踩
qzhouayi 发表于 2018-2-23 05:01
如果用背包实现的话,用一个背包去预处理,是不是就可以o(1)了

请问下怎么用背包实现?
回复

使用道具 举报

我的人缘0
ouyangivan 发表于 2018-2-23 06:09:13 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  80% (50)
 
 
19% (12)  踩
同问如何用背包实现。
回复

使用道具 举报

我的人缘0
closewen 发表于 2018-2-23 06:10:23 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  95% (19)
 
 
5% (1)  踩
用Segmentation Tree吧, Bit Indexed Tree。狗家真会考这种题。。。看来得好好准备下了
回复

使用道具 举报

我的人缘0
diefunction 发表于 2018-2-23 07:15:23 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  85% (40)
 
 
14% (7)  踩
wcg 发表于 2018-2-23 05:33
楼主没让算预处理时间就都读到set里面查询就是O(1)amertize 也是 constant啊
. 1point3acres
这个set怎么预处理才能O(1) 呀, 想不出来。
回复

使用道具 举报

游客
请先登录

本版积分规则

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

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

手机版|小黑屋|联系我们&一亩三分地论坛声明

GMT+8, 2018-11-18 18:34

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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