【生活质量系列】评测几款用过的咖啡机

一亩三分地论坛

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

最近看过此主题的会员

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

uber的一道电面题,求讨论

[复制链接] |试试Instant~
我的人缘0
vae371 发表于 2017-10-31 07:22:55 | 显示全部楼层 |阅读模式
本楼: 【顶】   100% (1)
 
 
0% (0)   【踩】
全局: 顶  96% (28)
 
 
3% (1)  踩

2017(10-12月) 码农类General 硕士 全职@Uber - 内推 - 技术电面  | Other | fresh grad应届毕业生

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

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

x
给一堆interval,比如{3,6},{2,4},然后给一个数,返回哪些interval包含了这个数,比如5就返回{3,6},{2,4},2就只返回{2,4}


上一篇:说一个刚刚结束的谷歌电面
下一篇:Facebook电面新鲜面经
我的人缘0
cx101220012 发表于 2017-11-13 09:03:45 | 显示全部楼层
本楼: 【顶】   100% (1)
 
 
0% (0)   【踩】
全局: 顶  92% (51)
 
 
7% (4)  踩
1.用hashmap 存。。。key是所有可能的number。。。value是list of interval。。。Pros: time complexity O(1)....Cons: space complexity (k*n) k is average size of one interval, n is number of intervals...

2.预先 根据start sort 存下来, 根据end sort 存下来。。。然后分别取start <= target, end>=target 在两个cache的list, 然后做interval。。。。time complexity 是O(lgn+k), k is potential output number...最坏情况下并没比直接搜要快。。。
回复

使用道具 举报

我的人缘0
jiayi411 发表于 2017-10-31 10:14:18 | 显示全部楼层
本楼: 【顶】   100% (1)
 
 
0% (0)   【踩】
全局: 顶  68% (142)
 
 
31% (66)  踩
直接比是O(n),排序是O(nlgn)
回复

使用道具 举报

我的人缘0
Corey_Lancer 发表于 2017-10-31 07:26:43 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  81% (13)
 
 
18% (3)  踩
复杂度什么要求。。? 还是有比check 每个interval更快方法么。。
回复

使用道具 举报

我的人缘0
 楼主| vae371 发表于 2017-10-31 07:30:04 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  96% (28)
 
 
3% (1)  踩
Corey_Lancer 发表于 2017-10-31 07:26
复杂度什么要求。。? 还是有比check 每个interval更快方法么。。

预处理一下,应该是有机会到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
yaya330 发表于 2017-10-31 08:18:40 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  95% (68)
 
 
4% (3)  踩
同求预处理方法,我遇到的是给一堆interval,再给一堆数,算每个interval包含了哪些数
回复

使用道具 举报

我的人缘0
ld_xixi 发表于 2017-10-31 08:25:21 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  94% (18)
 
 
5% (1)  踩
interval排个序, 然后跟二分跟start比?
回复

使用道具 举报

我的人缘0
ld_xixi 发表于 2017-10-31 08:26:12 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  94% (18)
 
 
5% (1)  踩
vae371 发表于 2017-10-31 07:30
预处理一下,应该是有机会到O(1)的吧,不然就遍历一下太简单了。。。
. From 1point 3acres bbs
怎么做到O(1)?

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

回复

使用道具 举报

我的人缘0
littlegrass 发表于 2017-10-31 08:34:32 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (14)
 
 
0% (0)  踩
请问 楼主是什么时候内推的?
回复

使用道具 举报

我的人缘0
velinforever 发表于 2017-10-31 08:41:08 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (3)
 
 
0% (0)  踩
segment tree?
回复

使用道具 举报

我的人缘0
 楼主| vae371 发表于 2017-10-31 08:43:37 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  96% (28)
 
 
3% (1)  踩
ld_xixi 发表于 2017-10-31 08:25
interval排个序, 然后跟二分跟start比?

恩,但这个还不是最优解

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

回复

使用道具 举报

我的人缘0
ld_xixi 发表于 2017-10-31 09:02:52 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  94% (18)
 
 
5% (1)  踩
vae371 发表于 2017-10-31 08:43
恩,但这个还不是最优解

求指教, 怎么招也得排一把序吧
回复

使用道具 举报

我的人缘0
storypku 发表于 2017-10-31 10:04:58 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (12)
 
 
0% (0)  踩
后边一个是个数而非尾数?
回复

使用道具 举报

我的人缘0
ld_xixi 发表于 2017-11-1 00:45:37 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  94% (18)
 
 
5% (1)  踩
jiayi411 发表于 2017-10-31 10:14
直接比是O(n),排序是O(nlgn)

恩 是啊 脑抽脑抽,感觉做array不排个序就不会了
回复

使用道具 举报

我的人缘0
linlin1990 发表于 2017-11-1 01:21:20 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  73% (36)
 
 
26% (13)  踩
为什么5就返回{3,6},{2,4}?
回复

使用道具 举报

我的人缘0
voelunteer 发表于 2017-11-7 13:57:14 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (3)
 
 
0% (0)  踩
感觉是leetcode 刺破气球那道题改编
回复

使用道具 举报

我的人缘0
nicklyz 发表于 2017-11-13 09:14:41 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  98% (141)
 
 
1% (2)  踩
请问一下楼主的timelne是怎样的
回复

使用道具 举报

我的人缘0
zhxymacau2017 发表于 2018-1-19 08:25:34 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  66% (2)
 
 
33% (1)  踩
cx00001 发表于 2017-11-13 09:03
1.用hashmap 存。。。key是所有可能的number。。。value是list of interval。。。Pros: time complexity O( ...

正解
回复

使用道具 举报

我的人缘0
zhxymacau2017 发表于 2018-1-19 08:25:35 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  66% (2)
 
 
33% (1)  踩
cx00001 发表于 2017-11-13 09:03
1.用hashmap 存。。。key是所有可能的number。。。value是list of interval。。。Pros: time complexity O( ...

正解
回复

使用道具 举报

我的人缘0
treeguard 发表于 2018-4-13 14:12:51 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (16)
 
 
0% (0)  踩
或者弄个interval tree? 感觉面试的时候要写出来也是挺难的
回复

使用道具 举报

游客
请先登录

本版积分规则

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

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

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

GMT+8, 2018-9-25 05:21

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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