近期论坛无法登录的解决方案


一亩三分地论坛

 找回密码
 获取更多干活,快来注册

一亩三分地官方iOS手机应用下载
查看: 4189|回复: 37
收起左侧

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

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

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

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

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

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

1, strstr
2, Kth most frequent number.鐣欏璁哄潧-涓浜-涓夊垎鍦
. from: 1point3acres.com/bbs
可能是有准备,写的太顺了,中间出了一两个不是啥大问题的小bug。他都给我指出来了,弄得我非常害怕😨。半个小时就写完了这两道题, 然后,又出一道:

Max Array
Input : An array of n numbers, and a number k
Output : An array of n numbers. more info on 1point3acres.com
where
output = MAX(input, input[i + 1]...... input[i + k - 1])

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

不是啥难题,不过当时被新题这个想法吓住了……憋了半个小时没憋出来。期间提到各种解法,从O(nk)到O(nlgk), 然后他非要我弄到O(n), 然后我要提示,他提示过我才想起得用Stack,但是Stack我也没想出解法来(楼主很菜,被你们发现了)。最后就这么草草结束了。
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
颓废了两天,今天居然接到2nd interview,不知道是不是他们内部系统出错了。.鏈枃鍘熷垱鑷1point3acres璁哄潧

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

另,求米啊,都快没有米搜索了……. 1point 3acres 璁哄潧

.鐣欏璁哄潧-涓浜-涓夊垎鍦


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

评分

2

查看全部评分

shinichish 发表于 2015-3-14 08:23:19 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
Max Array这题用deque解,楼主加油!
回复 支持 1 反对 0

使用道具 举报

 楼主| liokumo 发表于 2015-3-14 08:45:07 | 显示全部楼层
关注一亩三分地微博:
Warald
shinichish 发表于 2015-3-14 08:23
Max Array这题用deque解,楼主加油!

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

使用道具 举报

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

我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解,楼主加油!
. visit 1point3acres.com for more.
deque的话,如果弹出的是最大值,再弹入一个新值以后,不是还要遍历整个queue来找新的最大值?
回复 支持 反对

使用道具 举报

 楼主| liokumo 发表于 2015-3-14 09:02:32 | 显示全部楼层
shinichish 发表于 2015-3-14 08:52
我onsite过了。。。很不幸最后没能拿到offer,就是这题deque的题没解出来,真的很巧妙!. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
两轮电面面筋: ...

晕啊,这是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). more info on 1point3acres.com
回复 支持 反对

使用道具 举报

 楼主| 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). visit 1point3acres.com for more.
...

你把算法写出来就知道了,每个元素被遍历一次,被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. 鍥磋鎴戜滑@1point 3 acres
lz,光用stack好像实现不了吧?如果max是被window请出去的,只能从前头走人,如果是被后来人比下去的,需 ...
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
嗯,根据几位大神的说法,再加上我的研究,stack应该是不行,大概就是因为他给我提示错了才给了我二面机会吧……
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-6-25 17:21

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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