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

一亩三分地论坛

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

最近看过此主题的会员

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

狗狗家

[复制链接] |试试Instant~
我的人缘0
kawayipk 发表于 2017-10-12 13:24:58 | 显示全部楼层 |阅读模式
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (13)
 
 
0% (0)  踩

2017(4-6月) 码农类General 硕士 全职@Google - 内推 - 技术电面  | Fail | fresh grad应届毕业生

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

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

x
人生第一个面试就是Dream company,能拿到面试就是一份幸运,谢谢狗狗给我面试机会,以后还以你家为目标继续努力

一道题
有一个游戏,有人名和分数,实现两个function
void update(String name, int score)
. From 1point 3acres bbsint getByRank(int rank)
. 一亩-三分-地,独家发布
总结:重在交流沟通. from: 1point3acres
. From 1point 3acres bbs



上一篇:fb new grad 跪经
下一篇:FB电面刚拿到ONSITE
我的人缘0
junm5 发表于 2017-10-16 07:56:14 | 显示全部楼层
本楼: 【顶】   100% (1)
 
 
0% (0)   【踩】
全局: 顶  77% (7)
 
 
22% (2)  踩
augmented binary search tree.
update log(n), getRank log(n) , n is the size of nodes in that tree

评分

参与人数 1大米 +1 收起 理由
vrqq + 1 对嘛就是极为普通的平衡树应用

查看全部评分

回复

使用道具 举报

我的人缘0
张欣 发表于 2017-10-13 09:57:08 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
100% (1)   【踩】
全局: 顶  68% (54)
 
 
31% (25)  踩
lx5945 发表于 2017-10-13 08:42
我觉得这道题实现倒是不困难,但是就是一个相对好,可以相对满意的答案就比较难,请问大家对这道题都有什么 ...

我想的arraylist 或者priorityqueue时间复杂度都很高…
回复

使用道具 举报

我的人缘0
edyyy 发表于 2017-10-12 13:37:08 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  90% (150)
 
 
9% (16)  踩
谢谢楼主 分享,能举个例子吗?
回复

使用道具 举报

我的人缘0
 楼主| kawayipk 发表于 2017-10-12 14:48:38 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (13)
 
 
0% (0)  踩
上面的返回值写错了,应该是. 一亩-三分-地,独家发布
String getByRank(int)
. more info on 1point3acres
例子.本文原创自1point3acres论坛
比如
update("A", 100)
update("B", 120)
getByRank(1)     -> return "B" 来源一亩.三分地论坛.
update("B", 50)-google 1point3acres
update("C", 150)
getByRank(3)    -> return "B"

说明:重在沟通,我和面试官聊了10分钟,才把他想要实现的功能总结成这两个function, 他不会直接说让你写这两个function

评分

参与人数 1大米 +5 收起 理由
jigsaw_Becky + 5 感谢分享!

查看全部评分

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
zoeymiao 发表于 2017-10-12 22:13:19 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (2)
 
 
0% (0)  踩
thanks for sharing! just 1 question for entire session?
回复

使用道具 举报

我的人缘0
changju0310 发表于 2017-10-12 22:18:12 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  46% (13)
 
 
53% (15)  踩
请问楼主,这两个API有时间复杂度的限制吗
回复

使用道具 举报

我的人缘0
pbw 发表于 2017-10-12 23:30:19 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (16)
 
 
0% (0)  踩
谢谢楼主分享! 继续加油! 请问这题时间复杂度有限制没?
回复

使用道具 举报

我的人缘0
readman 发表于 2017-10-12 23:38:08 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  89% (322)
 
 
10% (38)  踩
??难道就是一个TreeMap?
回复

使用道具 举报

我的人缘0
zns1204zns 发表于 2017-10-13 08:02:35 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (2)
 
 
0% (0)  踩
多久收到的拒信能问一下吗~
回复

使用道具 举报

我的人缘0
 楼主| kawayipk 发表于 2017-10-13 08:26:34 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (13)
 
 
0% (0)  踩
zns1204zns 发表于 2017-10-13 08:02
. 牛人云集,一亩三分地多久收到的拒信能问一下吗~

一个星期吧,狗狗家HR在邮件里约了电话时间,打电话来说的。

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

回复

使用道具 举报

我的人缘0
lx5945 发表于 2017-10-13 08:42:07 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  82% (29)
 
 
17% (6)  踩
我觉得这道题实现倒是不困难,但是就是一个相对好,可以相对满意的答案就比较难,请问大家对这道题都有什么想法呢?谢谢~
回复

使用道具 举报

我的人缘0
张欣 发表于 2017-10-13 09:57:01 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  68% (54)
 
 
31% (25)  踩
lx5945 发表于 2017-10-13 08:42
我觉得这道题实现倒是不困难,但是就是一个相对好,可以相对满意的答案就比较难,请问大家对这道题都有什么 ...

我想的arraylist 或者priorityqueue时间复杂度都很高…
回复

使用道具 举报

我的人缘0
qpalzm0827 发表于 2017-10-15 04:35:04 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  75% (21)
 
 
25% (7)  踩
好像有一种tree, 每个node里面记录score和左边有多少node, 如果设计成self-balanced, 可以达到log(n) update 和 getByRank
回复

使用道具 举报

我的人缘0
waxc 发表于 2017-10-16 01:16:21 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (2)
 
 
0% (0)  踩
qpalzm0827 发表于 2017-10-15 04:35
好像有一种tree, 每个node里面记录score和左边有多少node, 如果设计成self-balanced, 可以达到log(n) updat ...

想问层住,如果用你说的这种tree的话,如何在log n 内完成update的操作?
回复

使用道具 举报

我的人缘0
waxc 发表于 2017-10-16 01:21:12 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (2)
 
 
0% (0)  踩
张欣 发表于 2017-10-13 09:57. 牛人云集,一亩三分地
我想的arraylist 或者priorityqueue时间复杂度都很高…
. visit 1point3acres for more.
我觉得用arraylist和一个hashmap可以做到update操作在O(n)而getRank操作在O(1)内完成
回复

使用道具 举报

我的人缘0
张欣 发表于 2017-10-16 02:02:09 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  68% (54)
 
 
31% (25)  踩
waxc 发表于 2017-10-16 01:21
我觉得用arraylist和一个hashmap可以做到update操作在O(n)而getRank操作在O(1)内完成

对,就是update时间复杂度o(n)感觉有点高,如果update得多的话
回复

使用道具 举报

我的人缘0
张欣 发表于 2017-10-16 02:03:55 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  68% (54)
 
 
31% (25)  踩
waxc 发表于 2017-10-16 01:21
我觉得用arraylist和一个hashmap可以做到update操作在O(n)而getRank操作在O(1)内完成

而且除了加入arraylist 会cost o(n)外,找出找哪个位置插入,binary search也会花费nlog(n)
回复

使用道具 举报

我的人缘0
waxc 发表于 2017-10-16 02:24:47 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (2)
 
 
0% (0)  踩
张欣 发表于 2017-10-16 02:03.本文原创自1point3acres论坛
而且除了加入arraylist 会cost o(n)外,找出找哪个位置插入,binary search也会花费nlog(n)

我的意思是,用arraylist和hashmap的话,找的部分可以用hashmap实现,找位置的部分也只需要O(n),原理跟insertion sort的insert部分差不多,最后,需要花的时间也是需要O(n)就能解决了~我觉得是应该用不到超过这个上限的时间复杂度。
回复

使用道具 举报

我的人缘0
张欣 发表于 2017-10-16 03:43:34 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  68% (54)
 
 
31% (25)  踩
waxc 发表于 2017-10-16 02:24
我的意思是,用arraylist和hashmap的话,找的部分可以用hashmap实现,找位置的部分也只需要O(n),原理跟i ...
. 围观我们@1point 3 acres
最后时间是o(n)没错,找位置二分查找复杂度我说错了 应该是log(n)
回复

使用道具 举报

我的人缘0
hujiaren 发表于 2017-10-16 07:46:33 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  77% (7)
 
 
22% (2)  踩
感觉如果分数在一个区间内的话,可以用bucket sort
回复

使用道具 举报

游客
请先登录

本版积分规则

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

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

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

GMT+8, 2018-9-24 12:01

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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