一亩三分地论坛

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

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

[找工就业] Poket Gems 1面

[复制链接] |试试Instant~ |关注本帖
penn.z 发表于 2015-5-9 07:23:38 | 显示全部楼层 |阅读模式

2015(4-6月)-[]CS硕士+3个月-1年 - 网上海投| 码农类全职@PoketGemfresh grad应届毕业生

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

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

x
原题 strstr 和 find k most frequent.
都做出来了。第二个调了会bug。
第二个复杂度应该是nlogn。当时受nlogk影响不能自拔。。又不能自圆其说。
实际上是,n个元素插入priority queue。插入复杂度是logn。插入n个是nlogn
感觉他家那个小白都面烦了,态度很不好。
他自己那边信号不好说话还巨快,不过没关系。
给他说思路他说你想怎么写就怎么写不用问我。。鬼态度。。
最后他自己也说,自己刚毕业没多久。pg是他第一份工作- -!(刚毕业就出来面试这样真的好么。). 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
然后瞬间接拒信。
不过本来也没有对这家有任何期待 就是面面玩玩的 所以心情还好
如果想mock interview的话还是可以投 对他家不要太认真就好了。


57656929bb 发表于 2015-5-9 08:03:02 | 显示全部楼层
。。。。你答错了。。。就是nlogk。。。建立堆就是n的时间复杂度。。。
回复 支持 反对

使用道具 举报

 楼主| penn.z 发表于 2015-5-9 12:49:24 | 显示全部楼层
57656929bb 发表于 2015-5-9 08:03 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
。。。。你答错了。。。就是nlogk。。。建立堆就是n的时间复杂度。。。

面试官解释的nlogn。
回复 支持 反对

使用道具 举报

 楼主| penn.z 发表于 2015-5-9 12:55:31 | 显示全部楼层
57656929bb 发表于 2015-5-9 08:03
。。。。你答错了。。。就是nlogk。。。建立堆就是n的时间复杂度。。。

因为把n个entry都插入了priority queue
每次插入是logn的复杂度。. more info on 1point3acres.com
所以还是nlogn
确实与k无关的。
回复 支持 反对

使用道具 举报

57656929bb 发表于 2015-5-10 02:18:55 | 显示全部楼层
penn.z 发表于 2015-5-9 12:55. Waral 鍗氬鏈夋洿澶氭枃绔,
因为把n个entry都插入了priority queue . 1point3acres.com/bbs
每次插入是logn的复杂度。
所以还是nlogn

.......插入是跟深度有关的。。深度是跟heap大小有关的。。。你看看算法书上的heap sort基本操作时间证明。。。
回复 支持 反对

使用道具 举报

 楼主| penn.z 发表于 2015-5-10 06:15:51 | 显示全部楼层
57656929bb 发表于 2015-5-10 02:18
.......插入是跟深度有关的。。深度是跟heap大小有关的。。。你看看算法书上的heap sort基本操作时间证明 ...

哦 你应该是对的 我用的是priority queue不是heap
但是priority queue一般的实现也是基于heap的。
所以top k的priority queue的插入复杂度是logk
n个元素都插进去应该是 nlogk没错。
我一开始也是这么解释的他没take。
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
因为讨论时考虑了一个问题是即使非top k的元素也是仍然存在queue里面
所以面试官理解为深度是log n了 他很笃定的那么解释我也就take了
他昨天给的注释如下
    // queue will end up at size n
    // add n things
    // adding is log (size)
    // n log n
- -!

回复 支持 反对

使用道具 举报

57656929bb 发表于 2015-5-10 07:19:15 | 显示全部楼层
penn.z 发表于 2015-5-10 06:15
哦 你应该是对的 我用的是priority queue不是heap
但是priority queue一般的实现也是基于heap的。
所以 ...

他的意思是全存heap里,但是没必要,可以只存k个,剩下的交给hash存,这傻逼公司面试官水平一般。。。
回复 支持 反对

使用道具 举报

shiloh00 发表于 2016-9-19 12:20:51 | 显示全部楼层
面试官水平好渣。。。
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-5 23:30

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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