买新车如何让dealer直接竞价?

一亩三分地论坛

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

最近看过此主题的会员

H1B/绿卡遥遥无期
又不想回国
来东南亚最大的互联网集团工作?
码农求职神器Triplebyte:
不用海投
内推多家公司面试
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
查看: 1041|回复: 21
收起左侧

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

[复制链接] |试试Instant~ |关注本帖
我的人缘0
yuqiche18768 发表于 2018-2-23 04:37:10 | 显示全部楼层 |阅读模式
  此人我要顶:
 
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之类的,是可以做到
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 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
如果用背包实现的话,用一个背包去预处理,是不是就可以o(1)了
回复 支持 反对

使用道具 举报

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

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

使用道具 举报

我的人缘0
wcg 发表于 2018-2-23 05:33:01 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
楼主没让算预处理时间就都读到set里面查询就是O(1)amertize 也是 constant啊
回复 支持 反对

使用道具 举报

我的人缘0
 楼主| yuqiche18768 发表于 2018-2-23 05:42:27 | 显示全部楼层
  此人我要顶:
 
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% (暂未有人投票) 【我投】
qzhouayi 发表于 2018-2-23 05:01. visit 1point3acres for more.
如果用背包实现的话,用一个背包去预处理,是不是就可以o(1)了

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

使用道具 举报

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

. visit 1point3acres for more.请问下怎么用背包实现?
回复 支持 反对

使用道具 举报

我的人缘0
ouyangivan 发表于 2018-2-23 06:09:13 | 显示全部楼层
  此人我要顶:
 
0% (0) 【我投】
  此人我要踩:
 
100% (6) 【我投】
同问如何用背包实现。
Mobile Apps Category (English)728x90
回复 支持 反对

使用道具 举报

我的人缘0
closewen 发表于 2018-2-23 06:10:23 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
用Segmentation Tree吧, Bit Indexed Tree。狗家真会考这种题。。。看来得好好准备下了
回复 支持 反对

使用道具 举报

我的人缘0
diefunction 发表于 2018-2-23 07:15:23 | 显示全部楼层
  此人我要顶:
 
66% (2) 【我投】
  此人我要踩:
 
34% (1) 【我投】
wcg 发表于 2018-2-23 05:33
楼主没让算预处理时间就都读到set里面查询就是O(1)amertize 也是 constant啊
.本文原创自1point3acres论坛
这个set怎么预处理才能O(1) 呀, 想不出来。
回复 支持 反对

使用道具 举报

我的人缘0
rapha 发表于 2018-2-23 07:46:07 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
同问什么是背包处理,谢谢!
回复 支持 反对

使用道具 举报

我的人缘0
zhtpandog 发表于 2018-2-23 09:42:36 | 显示全部楼层
  此人我要顶:
 
91% (41) 【我投】
  此人我要踩:
 
9% (5) 【我投】
如果真的要说预处理而不计空间复杂度的话,可以先过一遍建立[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 | 显示全部楼层
  此人我要顶:
 
50% (1) 【我投】
  此人我要踩:
 
50% (1) 【我投】
closewen 发表于 2018-2-23 06:10
用Segmentation Tree吧, Bit Indexed Tree。狗家真会考这种题。。。看来得好好准备下了

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

使用道具 举报

我的人缘0
xljob 发表于 2018-2-23 10:07:14 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
假设数据一共范围10000,那就开一个10000大小的array,就完了,但很消耗空间
回复 支持 反对

使用道具 举报

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

使用道具 举报

我的人缘0
closewen 发表于 2018-2-23 10:31:02 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
yiliaobailiao 发表于 2018-2-23 09:51
segment tree查询也得是logn吧?

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

使用道具 举报

我的人缘0
mmymichael 发表于 2018-2-23 11:23:42 | 显示全部楼层
  此人我要顶:
 
53% (16) 【我投】
  此人我要踩:
 
47% (14) 【我投】
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% (暂未有人投票) 【我投】
我觉得这题其实有点难。。。

同问背包处理是什么

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

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

使用道具 举报

我的人缘0
 楼主| yuqiche18768 发表于 2018-2-23 22:39:59 | 显示全部楼层
  此人我要顶:
 
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% (暂未有人投票) 【我投】
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

关闭

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

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

custom counter

GMT+8, 2018-6-22 05:37

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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