亚麻OA求砸,面经神衣护体!


一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
天天打游戏、照样领工资、还办H1B
这份工作你要不要?
把贵司招聘信息放这里
查看: 1105|回复: 22
收起左侧

狗狗家

[复制链接] |试试Instant~ |关注本帖
kawayipk 发表于 2017-10-12 13:24:58 | 显示全部楼层 |阅读模式

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

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

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

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

一道题
有一个游戏,有人名和分数,实现两个function
void update(String name, int score)
int getByRank(int rank)

总结:重在交流沟通
. visit 1point3acres.com for more.


本帖被以下淘专辑推荐:

  • · google|主题: 11, 订阅: 0
edyyy 发表于 2017-10-12 13:37:08 | 显示全部楼层
谢谢楼主 分享,能举个例子吗?
回复 支持 反对

使用道具 举报

 楼主| kawayipk 发表于 2017-10-12 14:48:38 | 显示全部楼层
上面的返回值写错了,应该是
String getByRank(int)

例子
. Waral 鍗氬鏈夋洿澶氭枃绔,比如
update("A", 100)
update("B", 120). 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
getByRank(1)     -> return "B"
update("B", 50)
update("C", 150)
getByRank(3)    -> return "B"

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

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

zoeymiao 发表于 2017-10-12 22:13:19 | 显示全部楼层
thanks for sharing! just 1 question for entire session?
回复 支持 反对

使用道具 举报

changju0310 发表于 2017-10-12 22:18:12 | 显示全部楼层
请问楼主,这两个API有时间复杂度的限制吗
回复 支持 反对

使用道具 举报

pbw 发表于 2017-10-12 23:30:19 | 显示全部楼层
谢谢楼主分享! 继续加油! 请问这题时间复杂度有限制没?
回复 支持 反对

使用道具 举报

readman 发表于 2017-10-12 23:38:08 | 显示全部楼层
??难道就是一个TreeMap?
回复 支持 反对

使用道具 举报

zns1204zns 发表于 7 天前 | 显示全部楼层
多久收到的拒信能问一下吗~
回复 支持 反对

使用道具 举报

 楼主| kawayipk 发表于 7 天前 | 显示全部楼层
zns1204zns 发表于 2017-10-13 08:02
多久收到的拒信能问一下吗~

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

使用道具 举报

lx5945 发表于 7 天前 | 显示全部楼层
我觉得这道题实现倒是不困难,但是就是一个相对好,可以相对满意的答案就比较难,请问大家对这道题都有什么想法呢?谢谢~
回复 支持 反对

使用道具 举报

张欣 发表于 7 天前 | 显示全部楼层
lx5945 发表于 2017-10-13 08:42
我觉得这道题实现倒是不困难,但是就是一个相对好,可以相对满意的答案就比较难,请问大家对这道题都有什么 ...

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

使用道具 举报

张欣 发表于 7 天前 | 显示全部楼层
lx5945 发表于 2017-10-13 08:42. more info on 1point3acres.com
我觉得这道题实现倒是不困难,但是就是一个相对好,可以相对满意的答案就比较难,请问大家对这道题都有什么 ...

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

使用道具 举报

qpalzm0827 发表于 5 天前 | 显示全部楼层
好像有一种tree, 每个node里面记录score和左边有多少node, 如果设计成self-balanced, 可以达到log(n) update 和 getByRank
回复 支持 反对

使用道具 举报

waxc 发表于 4 天前 | 显示全部楼层
qpalzm0827 发表于 2017-10-15 04:35
好像有一种tree, 每个node里面记录score和左边有多少node, 如果设计成self-balanced, 可以达到log(n) updat ...

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

使用道具 举报

waxc 发表于 4 天前 | 显示全部楼层
张欣 发表于 2017-10-13 09:57
我想的arraylist 或者priorityqueue时间复杂度都很高…

我觉得用arraylist和一个hashmap可以做到update操作在O(n)而getRank操作在O(1)内完成
回复 支持 反对

使用道具 举报

张欣 发表于 4 天前 | 显示全部楼层
waxc 发表于 2017-10-16 01:21.1point3acres缃
我觉得用arraylist和一个hashmap可以做到update操作在O(n)而getRank操作在O(1)内完成

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

使用道具 举报

张欣 发表于 4 天前 | 显示全部楼层
waxc 发表于 2017-10-16 01:21
我觉得用arraylist和一个hashmap可以做到update操作在O(n)而getRank操作在O(1)内完成
. from: 1point3acres.com/bbs
而且除了加入arraylist 会cost o(n)外,找出找哪个位置插入,binary search也会花费nlog(n)
回复 支持 反对

使用道具 举报

waxc 发表于 4 天前 | 显示全部楼层
张欣 发表于 2017-10-16 02:03
而且除了加入arraylist 会cost o(n)外,找出找哪个位置插入,binary search也会花费nlog(n)

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

使用道具 举报

张欣 发表于 4 天前 | 显示全部楼层
waxc 发表于 2017-10-16 02:24
我的意思是,用arraylist和hashmap的话,找的部分可以用hashmap实现,找位置的部分也只需要O(n),原理跟i ...

最后时间是o(n)没错,找位置二分查找复杂度我说错了 应该是log(n)
回复 支持 反对

使用道具 举报

hujiaren 发表于 4 天前 | 显示全部楼层
感觉如果分数在一个区间内的话,可以用bucket sort
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-10-20 09:53

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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