一亩三分地论坛

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

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

最新Zenefits电面题,滚烫的新题啊!

[复制链接] |试试Instant~ |关注本帖
M_Jason 发表于 2015-8-27 04:38:36 | 显示全部楼层 |阅读模式

2015(7-9月) 码农类 本科 全职@Zenefits - 内推 - 技术电面 |Failfresh grad应届毕业生

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

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

x
昨天下午刚刚电面了Zenefits,真是面的史无前例的烂啊!!!. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
题是新题,虽然没想着靠刷面经来碰到原题,但是这新题也着实有点儿让我摸不着头脑。先不废话,上完干货再说:. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
规定一个小时的面试,上来先问了15分钟的简历和behavioral question,然后紧接着就开始编程。给了我一个正方形的矩阵,左上角的位置保证是0,其他的每个坐标位置上都有一个大于等于0的数。一个人最初携带着的钱数为K,然后要从左上角走到右下角,每次只能向右或者向下走,每到一个位置上就需要花掉该位置上对应的钱数,要求编程看看这个人能不能走到右下角(到这儿的时候我还在窃喜,因为我以为他已经说完了呢,shit!),如果不能,就返回-1,如果能,那就要找到一个解法,使得这个人剩余的钱数尽可能少,也就是最终剩余的钱数要大于等于0,并且尽可能接近于0.听到最后我就出了一身冷汗,这题有点儿向leetcode的那个地牢游戏,但是却比那个还要复杂。想了几分钟想不出好的解决办法,只好先说了下brute force的解法,肯定知道得继续改进。不过面试官竟然不紧不慢的让我先说一下复杂度,我去,我想了想是不是2^n呢,但是面试官说不是。。。。靠,又分析了半天还是没想到,就先继续想更有效的解决方案了。然后想是不是可以用DP,然后同时保存走到每个坐标的时候剩余的钱数的最大最小值呢?说了一下之后,面试官就让我先把算法模拟走一遍,然后又开始分析复杂度,这个好分析,分析完之后,又让我证明正确性。。。。(我勒个去,哥哥,已经没多少时间让我写代码了诶,就不能先写代码吗?)然后说着说着发现,诶?这个方法有遗漏啊!面试官就有让我继续改进,但是实在想不出来高效的解法,就开始要求给提示,结果他说就按着你刚才的那个思路再想想,快接近正确答案了。想了半天还是想不到,就直接说能不能有那种暴力破解+剪枝呢?就是每次遇见已经小于0的情况的时候,这条路前面的结果就舍弃,只保存那些大于等于0的结果。他又让我分析时间复杂度和证明正确性,我去,看来这是没有时间写代码的节奏了,我已经觉得自己99%得挂了。然后又思考了半天,实在分析不出来时间复杂度,虽然知道正确,但是不敢确定这就是最优解啊!最后还是他告诉了我这个解法的时间复杂度,而且说这已经说最优解了,没有办法更快了。。。。我去,好吧!最后只有不到10分钟的时间写代码,只写了一点就到时间了!
. 鍥磋鎴戜滑@1point 3 acres

解法已经说出来了,你们可以试着分析一下暴力破解的时间复杂度以及最后那个最优解的时间复杂度!


反正我是已经彻底跪了,都已经不用等recruiter的电话了!哎,这种火的不行的startup真是傲娇啊,电面就给这种恶心题。。。。


补充内容 (2015-8-29 00:24): 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
筒子们~别光顾着回复啊,觉得有用的话适当的赏赐点儿分数呗,楼主也需要积分啊~多谢多谢!!祝你们个个offer拿到手软!!

评分

9

查看全部评分

本帖被以下淘专辑推荐:

discoveryi 发表于 2015-8-27 04:45:39 | 显示全部楼层
我拒了这公司的电面。
实在不想浪费时间在这么难的题目上。
回复 支持 反对

使用道具 举报

 楼主| M_Jason 发表于 2015-8-27 11:57:42 | 显示全部楼层
discoveryi 发表于 2015-8-27 04:45
我拒了这公司的电面。
实在不想浪费时间在这么难的题目上。

额,其实没有必要拒掉的,可以试试水嘛!也是一种锻炼,我本来也没把筹码压在这家身上。不过这些个hot startups面试都不会轻松的,所以无所谓了!!
回复 支持 反对

使用道具 举报

chenwoo 发表于 2015-8-27 14:01:07 | 显示全部楼层
加油!等着秋季大招!! ceo
回复 支持 反对

使用道具 举报

mmliu 发表于 2015-8-27 16:35:32 | 显示全部楼层
DP可以么?
. 1point3acres.com/bbs
就是在每个节点上保存所有到达这儿的路径,然后在右下角那儿统计最接近k的走法。
回复 支持 反对

使用道具 举报

Augustus 发表于 2015-8-27 16:56:11 | 显示全部楼层
mmliu 发表于 2015-8-27 16:35
DP可以么?

就是在每个节点上保存所有到达这儿的路径,然后在右下角那儿统计最接近k的走法。

空间复杂度爆表。。。
回复 支持 反对

使用道具 举报

Augustus 发表于 2015-8-27 17:00:21 | 显示全部楼层
暴力破解复杂度:一个2n位的二进制数,其中有n位为1,n位为0,复杂度是C(2n,n)吧。。。楼主你那个最优解小弟听得不是很懂,只保存最大最小值是怎么保证能求出最优解的呢?

补充内容 (2015-8-28 11:10):
不好意思前面算错了,暴力法的时间复杂度是2n*(C(2n,n)),然后那个保存过程的方法时间复杂度是(C(2n,n))
回复 支持 反对

使用道具 举报

mkcing 发表于 2015-8-27 22:48:59 | 显示全部楼层
Augustus 发表于 2015-8-27 16:56
空间复杂度爆表。。。

(1) 只用存最近两行的列表
(2)每个列表删掉大于k的数. From 1point 3acres bbs

但是这个空间复杂度还是大
回复 支持 反对

使用道具 举报

Augustus 发表于 2015-8-28 00:59:10 | 显示全部楼层
mkcing 发表于 2015-8-27 22:48
(1) 只用存最近两行的列表
(2)每个列表删掉大于k的数
. 1point3acres.com/bbs
而且我觉得存这个也很烦,还不如用暴力省事。。。但是面试这么说会不会被刷。。。。
回复 支持 反对

使用道具 举报

 楼主| M_Jason 发表于 2015-8-28 01:40:13 | 显示全部楼层
mmliu 发表于 2015-8-27 16:35
DP可以么?

就是在每个节点上保存所有到达这儿的路径,然后在右下角那儿统计最接近k的走法。

对啊。。。其实我最初的解法就是这个,因为实在想不起来怎么有效的解答,只能下给这种BF的方法,但是的确,这种方法的时间复杂度是最高的,根本无法接受。。。。。
回复 支持 反对

使用道具 举报

spiritrhy 发表于 2015-8-28 01:42:09 | 显示全部楼层
请问楼主是在地里找人内推的还是自己投的呢?
回复 支持 反对

使用道具 举报

 楼主| M_Jason 发表于 2015-8-28 01:42:50 | 显示全部楼层
Augustus 发表于 2015-8-27 17:00
暴力破解复杂度:一个2n位的二进制数,其中有n位为1,n位为0,复杂度是C(2n,n)吧。。。楼主你那个最优解小 ...

不是只保存最大值最小值,那个是错误解,有漏洞,我说的那个已经可以接受的解答方案是指,只保存当前剩余钱数中大于等于0的所有解答方案,如果有方案使得当前剩余钱数小于0了,就舍弃,也就是一种BF+剪枝的办法。到最后的时候面试官说这个复杂已经可以接受了,并且他给我分析了一遍为什么已经基本是最优了,哎!!
回复 支持 反对

使用道具 举报

 楼主| M_Jason 发表于 2015-8-28 01:44:12 | 显示全部楼层
Augustus 发表于 2015-8-28 00:59. 1point 3acres 璁哄潧
而且我觉得存这个也很烦,还不如用暴力省事。。。但是面试这么说会不会被刷。。。。
. From 1point 3acres bbs
哈哈,你肯定不能抱着这就是最优解的心态去跟面试官说的,要不然会被鄙视的,不过没关系,这种公司的面试题变态也正常,别把赌注压到这种公司就行!
回复 支持 反对

使用道具 举报

 楼主| M_Jason 发表于 2015-8-28 01:45:55 | 显示全部楼层
坐等大家分析那个暴力破解+剪枝的复杂度,反正我当时面的时候,愣是没想出来,最后面试官一给我说出来,我就豁然开朗了,自己分析的方式不对啊!!
回复 支持 反对

使用道具 举报

 楼主| M_Jason 发表于 2015-8-28 01:48:57 | 显示全部楼层
spiritrhy 发表于 2015-8-28 01:42
请问楼主是在地里找人内推的还是自己投的呢?

找人推的!这些公司自己投的话,反应太慢,而且不容易拿面试!
回复 支持 反对

使用道具 举报

spiritrhy 发表于 2015-8-28 01:51:08 | 显示全部楼层
M_Jason 发表于 2015-8-28 01:48 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
找人推的!这些公司自己投的话,反应太慢,而且不容易拿面试!

是在地里找吗?还是?
回复 支持 反对

使用道具 举报

夜行码农耗子 发表于 2015-8-28 01:55:32 | 显示全部楼层
顶一记,我也刚刚面完,一样是新题,但是没你的这么难。。。
回复 支持 反对

使用道具 举报

wenqiang88 发表于 2015-8-28 02:43:46 | 显示全部楼层
请问这样可以不可以?
先从左上角往右下角开始DP, 算到该点时所有可能出现的钱数
然后再从右下角往左上角DP, 算从该点到终点,所有路径可能需要的钱数
然后遍历每个点,求这2个list的最小差

补充内容 (2015-8-28 02:48):
其实从左上往右下的DP好像都可以不做。只需要从右下往左上算,最后在起点里找到比K小的最大的数就行。不知道这样对不对?求指点
回复 支持 反对

使用道具 举报

 楼主| M_Jason 发表于 2015-8-28 04:36:05 | 显示全部楼层
夜行码农耗子 发表于 2015-8-28 01:55
顶一记,我也刚刚面完,一样是新题,但是没你的这么难。。。

喔~那不错,那就等好消息吧!
回复 支持 反对

使用道具 举报

夜行码农耗子 发表于 2015-8-28 04:54:51 | 显示全部楼层
M_Jason 发表于 2015-8-28 04:36
喔~那不错,那就等好消息吧!

估计没戏,发挥不好~
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-10 09:13

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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