废柴的我该如何谈恋爱?

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货

最近看过此主题的会员

坐标湾区
DreamCraft创始团队
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
码农求职神器Triplebyte:
不用海投
内推多家公司面试
前Google华人高管创立
面试offer一键直通
Leap.ai助你进入热门独角兽
查看: 1157|回复: 21
收起左侧

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

[复制链接] |试试Instant~
我的人缘0
yuqiche18768 发表于 2018-2-23 04:37:10 | 显示全部楼层 |阅读模式
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (16)
 
 
0% (0)  踩

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

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

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

x
刚刚结束,一个三哥,上来直接放题,给一堆predefined intervals,然后输入是一个integer,问在这些intervals 的 range中能否找到该integer,. more info on 1point3acres
例如:
[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里面的时间,. more info on 1point3acres
貌似是说给个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找工作学习生活一切顺利~. from: 1point3acres


补充内容 (2018-2-23 22:59):
这道题如果什么限定条件不加,输入直接List + int, O(n)不能再少。面试官问O(lgn)和O(1)只是打破常规刷题模式,看你能不能get到他的点,并不代表真的就要让你实现,面试中明确对方的意图很重要,也怪自己经验少。。

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

使用道具 举报

我的人缘0
 楼主| yuqiche18768 发表于 2018-2-23 05:15:11 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (16)
 
 
0% (0)  踩
qzhouayi 发表于 2018-2-23 05:01. From 1point 3acres bbs
如果用背包实现的话,用一个背包去预处理,是不是就可以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% (16)
 
 
0% (0)  踩
wcg 发表于 2018-2-23 05:33
楼主没让算预处理时间就都读到set里面查询就是O(1)amertize 也是 constant啊
. From 1point 3acres bbs
O(1)的当时确实没想到,最后他叫我实现的是Binary search,应该是认为我没想到O(1)的解法才这样说的吧

21.000+ students read the Road to learn React. The course weaves all the opinionated roadmaps into one roadmap to master React. It gives you all the fundamentals in React. You will build a Hacker News App along the way.

回复

使用道具 举报

我的人缘0
charleszhou 发表于 2018-2-23 05:53:34 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  97% (141)
 
 
2% (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)   【踩】
全局: 顶  81% (44)
 
 
18% (10)  踩
同问如何用背包实现。

With React+D3v4 you'll learn the basics of building fast data visualization components in about an hour.

回复

使用道具 举报

我的人缘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)   【踩】
全局: 顶  84% (39)
 
 
15% (7)  踩
wcg 发表于 2018-2-23 05:33. From 1point 3acres bbs
楼主没让算预处理时间就都读到set里面查询就是O(1)amertize 也是 constant啊

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

使用道具 举报

我的人缘0
rapha 发表于 2018-2-23 07:46:07 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (2)
 
 
0% (0)  踩
同问什么是背包处理,谢谢!

Learn React.js, Redux & Immutable.js while building a weather app

回复

使用道具 举报

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

使用道具 举报

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

segment tree查询也得是logn吧?
回复

使用道具 举报

我的人缘0
xljob 发表于 2018-2-23 10:07:14 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  84% (11)
 
 
15% (2)  踩
假设数据一共范围10000,那就开一个10000大小的array,就完了,但很消耗空间
回复

使用道具 举报

我的人缘0
xljob 发表于 2018-2-23 10:09:37 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  84% (11)
 
 
15% (2)  踩
假设数据一共范围10000,那就开一个10000大小的array,就完了,但很消耗空间…线段树也不是o1啊
回复

使用道具 举报

我的人缘0
closewen 发表于 2018-2-23 10:31:02 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  95% (19)
 
 
5% (1)  踩
yiliaobailiao 发表于 2018-2-23 09:51
segment tree查询也得是logn吧?
. Waral 博客有更多文章,
是啊,不过O(1)也只能是index全存Hash或Array了吧。少占些空间,又比O(n)快的,那也就是segment tree了吧。虽然线段树还在学。。。
回复

使用道具 举报

我的人缘0
mmymichael 发表于 2018-2-23 11:23:42 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  67% (304)
 
 
32% (146)  踩
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
回复

使用道具 举报

我的人缘0
greynut 发表于 2018-2-23 16:49:17 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  90% (28)
 
 
9% (3)  踩
我觉得这题其实有点难。。。

同问背包处理是什么

粗略一看也只能想到binary searching tree 和 hashset 硬来

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

使用道具 举报

我的人缘0
 楼主| yuqiche18768 发表于 2018-2-23 22:39:59 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (16)
 
 
0% (0)  踩
greynut 发表于 2018-2-23 16:49
我觉得这题其实有点难。。。

同问背包处理是什么

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

使用道具 举报

我的人缘0
wcg 发表于 2018-2-23 22:41:36 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  77% (7)
 
 
22% (2)  踩
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

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

GMT+8, 2018-9-22 03:54

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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