一亩三分地论坛

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

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

Pocket Gems 第一轮,有一道题不一样,求二面面筋

[复制链接] |试试Instant~ |关注本帖
liokumo 发表于 2015-3-14 08:17:50 | 显示全部楼层 |阅读模式

2015(4-6月) 码农类 硕士 全职@Pocket Gems - 网上海投 - 技术电面 |Pass

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

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

x
我是这周三面的,本来挺有信心,因为地里的人都面的一样的题,所以准备了挺多,那两道题的各种解法都写了一下,要的话跟我说。

1, strstr
. from: 1point3acres.com/bbs 2, Kth most frequent number

可能是有准备,写的太顺了,中间出了一两个不是啥大问题的小bug。他都给我指出来了,弄得我非常害怕😨。半个小时就写完了这两道题, 然后,又出一道:

Max Array
Input : An array of n numbers, and a number k. visit 1point3acres.com for more.
Output : An array of n numbers
where. more info on 1point3acres.com
output = MAX(input, input[i + 1]...... input[i + k - 1]). 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴

example:
[1, 3, 5, 7, 3, 4, 2, 9],  k = 3-google 1point3acres
[5, 7, 7, 7, 4, 9, 9, 9]

不是啥难题,不过当时被新题这个想法吓住了……憋了半个小时没憋出来。期间提到各种解法,从O(nk)到O(nlgk), 然后他非要我弄到O(n), 然后我要提示,他提示过我才想起得用Stack,但是Stack我也没想出解法来(楼主很菜,被你们发现了)。最后就这么草草结束了。. Waral 鍗氬鏈夋洿澶氭枃绔,

颓废了两天,今天居然接到2nd interview,不知道是不是他们内部系统出错了。

求二面面筋啊,这回我一定不那么快写完了……一定拖到1个小时写完

另,求米啊,都快没有米搜索了……
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
. more info on 1point3acres.com


补充内容 (2015-3-14 08:19):
忘了给邮箱了,二面面筋求发邮箱啊~~liang.yiy@husky.neu.edu

评分

2

查看全部评分

shinichish 发表于 2015-3-14 08:23:19 | 显示全部楼层
Max Array这题用deque解,楼主加油!
回复 支持 1 反对 0

使用道具 举报

 楼主| liokumo 发表于 2015-3-14 08:45:07 | 显示全部楼层
shinichish 发表于 2015-3-14 08:23. visit 1point3acres.com for more.
Max Array这题用deque解,楼主加油!

是他提示的我用Stack,但是我也确实没想到怎么用Stack解,亲好厉害,能不能说说Deque怎么解啊?. visit 1point3acres.com for more.
另,亲面过pocket gems吧?能不能给个二面代码啥的……
回复 支持 反对

使用道具 举报

shinichish 发表于 2015-3-14 08:52:05 | 显示全部楼层
liokumo 发表于 2015-3-13 16:45-google 1point3acres
是他提示的我用Stack,但是我也确实没想到怎么用Stack解,亲好厉害,能不能说说Deque怎么解啊?
另,亲 ...

我onsite过了。。。很不幸最后没能拿到offer,就是这题deque的题没解出来,真的很巧妙!
两轮电面面筋:
http://www.1point3acres.com/bbs/thread-119909-1-1.html
onsite面筋:
http://www.1point3acres.com/bbs/thread-120184-1-1.html
回复 支持 反对

使用道具 举报

wrj5518 发表于 2015-3-14 08:53:25 | 显示全部楼层
shinichish 发表于 2015-3-14 08:23
Max Array这题用deque解,楼主加油!

deque的话,如果弹出的是最大值,再弹入一个新值以后,不是还要遍历整个queue来找新的最大值?
回复 支持 反对

使用道具 举报

 楼主| liokumo 发表于 2015-3-14 09:02:32 | 显示全部楼层
shinichish 发表于 2015-3-14 08:52
我onsite过了。。。很不幸最后没能拿到offer,就是这题deque的题没解出来,真的很巧妙!.鏈枃鍘熷垱鑷1point3acres璁哄潧
两轮电面面筋: ...

晕啊,这是onsite的题啊,我之前都没敢看onsite的题
回复 支持 反对

使用道具 举报

 楼主| liokumo 发表于 2015-3-14 09:03:37 | 显示全部楼层
wrj5518 发表于 2015-3-14 08:53
deque的话,如果弹出的是最大值,再弹入一个新值以后,不是还要遍历整个queue来找新的最大值?

是啊,那样不就不是O(n)了?
回复 支持 反对

使用道具 举报

shinichish 发表于 2015-3-14 09:22:18 | 显示全部楼层
wrj5518 发表于 2015-3-13 16:53.鐣欏璁哄潧-涓浜-涓夊垎鍦
deque的话,如果弹出的是最大值,再弹入一个新值以后,不是还要遍历整个queue来找新的最大值?

对于每个元素来说,至多分别被enqueue和dequeue一次,有n个元素,所以复杂度O(n)
回复 支持 反对

使用道具 举报

shinichish 发表于 2015-3-14 09:22:29 | 显示全部楼层
liokumo 发表于 2015-3-13 17:03
是啊,那样不就不是O(n)了?

参考楼上回答
回复 支持 反对

使用道具 举报

wrj5518 发表于 2015-3-14 09:30:01 | 显示全部楼层
shinichish 发表于 2015-3-14 09:22
对于每个元素来说,至多分别被enqueue和dequeue一次,有n个元素,所以复杂度O(n)

但是每个元素可能被遍历k遍(比如一个单调下降的数组),总共n个元素,所以复杂度是O(nk),不是O(n)
回复 支持 反对

使用道具 举报

 楼主| liokumo 发表于 2015-3-14 10:24:50 | 显示全部楼层
面我的人说用Stack,谁知道能用Stack来个O(n)解法么?
另,我收回这题不难这句话,越想越不会……
回复 支持 反对

使用道具 举报

57656929bb 发表于 2015-3-14 10:53:30 | 显示全部楼层
wrj5518 发表于 2015-3-14 09:30
但是每个元素可能被遍历k遍(比如一个单调下降的数组),总共n个元素,所以复杂度是O(nk),不是O(n). 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
...

你把算法写出来就知道了,每个元素被遍历一次,被pop一次,所以是2n,这个deque的精髓在于并不用维持queue的大小为k,如果在一个元素之前进来,又比这个元素小,就可以一次把他们deque完
回复 支持 反对

使用道具 举报

77777777 发表于 2015-3-17 04:48:31 | 显示全部楼层
楼主你可不可以给我发一份你的代码什么的 我的邮箱是shuchang407@gmail.com 谢楼主!
回复 支持 反对

使用道具 举报

dsq704136 发表于 2015-3-26 05:22:52 | 显示全部楼层
请问一下楼主面试时候第二题用什么方法解得,可以发我一份代码么?谢谢!祝offer!dsq704136@gmail.com
回复 支持 反对

使用道具 举报

nathanwong 发表于 2015-3-27 12:55:55 | 显示全部楼层
lz 那两道题的各种解法都写了一下,要的话跟我说

能否发一下 nathanwong.others@gmail.com 谢谢了
回复 支持 反对

使用道具 举报

xxtsxxts 发表于 2015-4-1 04:07:43 | 显示全部楼层
麻烦楼主把两道题的解法发我一下,329992361@qq.com,谢谢了!
回复 支持 反对

使用道具 举报

haomin_zz 发表于 2015-4-4 06:53:04 | 显示全部楼层
楼主求发一面代码,谢谢啦 359038152@qq.com
回复 支持 反对

使用道具 举报

miraclebingo 发表于 2015-4-6 13:01:18 | 显示全部楼层
lz能发一份代码吗?多谢!zzcai1990@gmail.com
回复 支持 反对

使用道具 举报

miraclebingo 发表于 2015-4-6 15:12:02 | 显示全部楼层
liokumo 发表于 2015-3-14 10:24
面我的人说用Stack,谁知道能用Stack来个O(n)解法么?
另,我收回这题不难这句话,越想越不会……

lz,光用stack好像实现不了吧?如果max是被window请出去的,只能从前头走人,如果是被后来人比下去的,需要从后面走人,这么理解不知道对不对
回复 支持 反对

使用道具 举报

 楼主| liokumo 发表于 2015-4-6 20:02:06 | 显示全部楼层
miraclebingo 发表于 2015-4-6 02:12. 1point3acres.com/bbs
lz,光用stack好像实现不了吧?如果max是被window请出去的,只能从前头走人,如果是被后来人比下去的,需 ...

嗯,根据几位大神的说法,再加上我的研究,stack应该是不行,大概就是因为他给我提示错了才给了我二面机会吧……
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-9 01:05

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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