一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 1293|回复: 16
收起左侧

Pocket Gems第一轮电面

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

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

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

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

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))。

补充内容 (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)吧
回复 支持 反对

使用道具 举报

 楼主| 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. Waral 鍗氬鏈夋洿澶氭枃绔,
第二题有点不太明白,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。
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

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

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-6 10:55

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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