[职场感言] 工作一年了,聊聊三件事

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
E轮2.5亿美元融资
K12教育独角兽一起作业
北京-诚聘人工智能/教育/大数据岗
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
码农求职神器Triplebyte:
不用海投
内推多家公司面试
把贵司招聘信息放这里
查看: 1876|回复: 16
收起左侧

Pocket Gems第一轮电面

[复制链接] |试试Instant~ |关注本帖
anonym 发表于 2015-2-6 11:54:30 | 显示全部楼层 |阅读模式

2015(1-3月) 码农类General 硕士 全职@Pocket Gems - 猎头 - 技术电面  | Pass |

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

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

x
都是面经原题。
1. StrStr():
时间复杂度,worst case举例。
来源一亩.三分地论坛.
2. K most frequently occurring numbers:
时间复杂度。
follow-up:infinite stream of sorted numbers coming(用什么实现,伪代码,时间复杂度)。




补充内容 (2015-3-23 11:50):
第一题时间复杂度O(n),worst case是在111111111112中找11112这种。
第二题时间复杂度O(n*log(n));follow-up我用了一个heap,时间复杂度O(n*log(k))。. Waral 博客有更多文章,

补充内容 (2015-4-14 02:13):
第一题时间复杂度O(m*n) 打错了

评分

1

查看全部评分

nibuxing 发表于 2015-2-28 00:17:58 | 显示全部楼层
你是自己网申的还是内推的啊
回复 支持 反对

使用道具 举报

 楼主| anonym 发表于 2015-3-5 07:16:51 | 显示全部楼层
nibuxing 发表于 2015-2-27 11:17 来源一亩.三分地论坛.
你是自己网申的还是内推的啊

猎头投的
回复 支持 反对

使用道具 举报

dsq704136 发表于 2015-3-26 06:33:35 | 显示全部楼层
请问下第二题,follow up之前楼主用什么方法实现的?如果用heap的话需要自己实现heap么?还是可以直接用priorityQ?
回复 支持 反对

使用道具 举报

 楼主| anonym 发表于 2015-3-26 13:22:30 | 显示全部楼层
dsq704136 发表于 2015-3-25 17:33
请问下第二题,follow up之前楼主用什么方法实现的?如果用heap的话需要自己实现heap么?还是可以直接用pri ...
. 留学申请论坛-一亩三分地
我是用的Map存了每个数字出现的次数 然后扔到List里面sort
不需要自己实现 可以用PriorityQueue的
回复 支持 反对

使用道具 举报

dsq704136 发表于 2015-3-27 03:43:09 | 显示全部楼层
anonym 发表于 2015-3-26 13:22
我是用的Map存了每个数字出现的次数 然后扔到List里面sort
不需要自己实现 可以用PriorityQueue的

好的!这就放心了,非常感谢!
回复 支持 反对

使用道具 举报

ryuichist 发表于 2015-4-14 13:21:42 | 显示全部楼层
第一题,如果是stream的话,这个要怎么解决呢?是每一段时间取一次,然后更新PQ?
回复 支持 反对

使用道具 举报

ryuichist 发表于 2015-4-14 13:22:18 | 显示全部楼层
哦还有第一题,第一题可以到O(N)?worst case应该是o(mn)吧
Mobile Apps Category (English)728x90
回复 支持 反对

使用道具 举报

 楼主| anonym 发表于 2015-4-14 15:12:08 | 显示全部楼层
ryuichist 发表于 2015-4-14 00:21
第一题,如果是stream的话,这个要怎么解决呢?是每一段时间取一次,然后更新PQ?

stream是sort过的 每次碰到一个新数就把刚才的放进PQ里面
回复 支持 反对

使用道具 举报

 楼主| anonym 发表于 2015-4-14 15:12:23 | 显示全部楼层
ryuichist 发表于 2015-4-14 00:22
哦还有第一题,第一题可以到O(N)?worst case应该是o(mn)吧

嗯 我打错了
回复 支持 反对

使用道具 举报

ryuichist 发表于 2015-4-14 15:19:14 | 显示全部楼层
anonym 发表于 2015-4-14 15:12
stream是sort过的 每次碰到一个新数就把刚才的放进PQ里面

喔,好的,stream是sort过的应该就简单了。遇到新的就加进去,遇到以前有的就更新
回复 支持 反对

使用道具 举报

frankrenyu 发表于 2015-5-20 06:56:45 | 显示全部楼层
楼主我想请教一下 ,第二题的follow up之用一个minheap 能行吗?  如果你新进来的数只有2个,然后minheap里面已经有了k个元素,那么我们放进去minheap势必要把堆顶元素弹出来,这样有可能是不对的吧,我在想需不需要一个map来记录frequent,谢谢楼主!
回复 支持 反对

使用道具 举报

 楼主| anonym 发表于 2015-5-23 17:01:57 | 显示全部楼层
frankrenyu 发表于 2015-5-19 17:56
楼主我想请教一下 ,第二题的follow up之用一个minheap 能行吗?  如果你新进来的数只有2个,然后minheap里 ...

没太明白你的意思 举个例子?
回复 支持 反对

使用道具 举报

xanadulord 发表于 2015-5-27 11:10:51 | 显示全部楼层
第二题有点不太明白,sort过和没有sort过的区别在哪里呢?没有sort的话,用map 和 heap做出来的复杂度也是nlogk呀?
回复 支持 反对

使用道具 举报

twosum 发表于 2015-5-31 11:25:23 | 显示全部楼层
第一题可以用KMP算法,O(n)
回复 支持 反对

使用道具 举报

 楼主| anonym 发表于 2015-6-1 07:56:04 | 显示全部楼层
xanadulord 发表于 2015-5-26 22:10
第二题有点不太明白,sort过和没有sort过的区别在哪里呢?没有sort的话,用map 和 heap做出来的复杂度也是n ...
. 一亩-三分-地,独家发布
因为是infinite stream, 不能通过遍历把每个数字的frequency存在HashTable里,所以只有sort过才能count frequency。
回复 支持 反对

使用道具 举报

xanadulord 发表于 2015-6-1 10:29:14 | 显示全部楼层
anonym 发表于 2015-6-1 07:56
因为是infinite stream, 不能通过遍历把每个数字的frequency存在HashTable里,所以只有sort过才能count  ...

. 一亩-三分-地,独家发布噢,明白了!follow up相当于把没有follow up的两个过程一起做了,一边计数,一边放minheap。
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2018-5-24 03:04

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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