一亩三分地论坛

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

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

Zenefits OA4 + skype + onsite 已挂

[复制链接] |试试Instant~ |关注本帖
jokebill 发表于 2015-5-14 11:05:41 | 显示全部楼层 |阅读模式

2015(4-6月) 码农类 博士 全职@Zenefits - 网上海投 - 技术电面 Onsite 在线笔试 |Failfresh grad应届毕业生

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

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

x
找工作以来拿到的第一个面试,投的时候都还不知道Z家是不错的公司,结果准备不足,on-site挂了,也是比较遗憾。面经留在这边造福后人吧,顺便求米:)
OA是 test 4,难度还是很大的,事先在地里找到题的情况下,还用满了三个小时,最终倒是全case通过,顺利拿到电面

题目见 Zenefits Test 4
-google 1point3acres
说下思路吧,第一题要想全test通过,有两点要注意的,第一是,读数据的时候,要用ordered map存,map的key是票的张数,map的value是有这么多张票的窗口出现的次数。第二是读数据的时候,要先把票数最多的窗口的票取到和第二多的一样,然后与票数第二多的窗口合并,取到与第三多的窗口票数一样,至到取的票超过需要的票数,再一层一层的退回去. 鍥磋鎴戜滑@1point 3 acres

第二题 用next permutation做,肯定挂,正确的思路是,cbcaadd这样的string,先看第一个字符,所有以a和b开始的字串都比他index小,数量是 6! / 2! (因为有两个d一样) + 6! / 2! / 2! (两个a,两个d),然后ca开始的字串都比他index小,数量是 5! / 2!,依此类推,就可以算出当前串的permutation index了。这题还牵涉到大数的模运算,我是自己定义了一个进行两个数带模加减乘除计算的类,其中最复杂的模除算法,OA里面会给,直接用就好了,我当时是想了很久为什么 6 / 4 (under mod 9) = 6 这种无脑问题,所以一直耗到最后一分钟才做完的……

skype开始就全是小印面了,z家小印还真是多

skype题是给一个adjacency matrix表示的图,求图里有多少个unique triangle。先给了个O(n^3)算法,小印说得化简,化吧,化到O(n^2),化不下去了,磨到时间到,小印很欢乐的说你可以hashmap,然后blabla一堆,结束后我一想,他给的还是个O(n^2)算法啊,也不知他怎么想的,不过好歹给了on-site了
. Waral 鍗氬鏈夋洿澶氭枃绔,
on-site两轮技术面都是小印,第一轮先和我闲侃了会儿hadoop和spark(简历写了),不code聊了下mapreduce怎么找大数据的mean和median,然后出题,valid BST那道,地里面有的,我也编过了,谁知说了想法,小印觉得听不懂,非要按他的方法来,搞的我一头雾水,实际上他的方法,worst case是O(n^2),而我写过的是guranteed O(n)的,无语写完,一堆bug也来不及fix了,唉
. visit 1point3acres.com for more.
第二轮另一个小印,上来直接问coding题,vector of unsigned int,求两两之间hamming distance之和,要求O(n)时间。想了半天,后来小印提示说,如果这些int只是0和1呢,才终于想出了按位求和的解法。第二题,给一个tree,有一些node被label成failed了,要写一个算法,对tree中每一个node,求到这些failed node的距离之和,也是想了很久,后来提示了递归公式才写出来,估计就是挂在这两题了。. From 1point 3acres bbs

两轮之后来了一白哥,闲聊问问题半小时,结束。回来一天之后就接到电话被拒了……




评分

7

查看全部评分

本帖被以下淘专辑推荐:

 楼主| jokebill 发表于 2015-6-30 00:39:58 | 显示全部楼层
辉哥哥 发表于 2015-6-27 07:17. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
第二轮另一个小印,上来直接问coding题,vector of unsigned int,求两两之间hamming distance之和,要求O( ...

走一遍,存每一个位上0的个数和1的个数,把每一位上0的个数和1的个数相乘,就是这一位上的hamming distance和,把所有位上的hamming distance和加在一起,就是总的hamming distance之和
回复 支持 1 反对 0

使用道具 举报

huahuazhu 发表于 2015-5-15 13:48:37 | 显示全部楼层
多谢楼主分享,能再展开讲讲么? 我很多看不明白的 😓

permutation那题,“先看第一个字符,所有以a和b开始的字串都比他index小,数量是 6! / 2! (因为有两个d一样) + 6! / 2! / 2! (两个a,两个d)” 为什么不用考虑两个c? 按照我的理解,还都要再处以2!
"大数的模运算,我是自己定义了一个进行两个数带模加减乘除计算的类" 这个更是一头雾水了,这是什么情况需要的? 是因为“!”阶乘运算么?没想通这部分是要处理什么/怎么处理. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴


第二轮小印的问题,也是没看明白思路。楼主能具体讲一下解法么?

回复 支持 反对

使用道具 举报

 楼主| jokebill 发表于 2015-5-16 04:51:48 | 显示全部楼层
huahuazhu 发表于 2015-5-15 13:48
多谢楼主分享,能再展开讲讲么? 我很多看不明白的 😓

permutation那题,“先看第一个字符,所有 ...

不好意思,写的example自己看漏了,是要考虑两个c多除一次2!的. Waral 鍗氬鏈夋洿澶氭枃绔,
-google 1point3acres
大数模运算是因为如果不这样,即使用long long存数据,也无法处理接近100个字符的permutation index,而题目最终要求是输出permutation index相对于某个很大质数的模,所以要在所有计算中使用模乘和模除.1point3acres缃

小印的题,我写的是O(n^3)算法,就是所有node任选三个,在adjacency matrix里找他们是否相连。简化成O(n^2)是因为找两个node之后,第三个node只需要查其adjacency matrix的相应行与第一个node相应列是否为1即可
回复 支持 反对

使用道具 举报

huahuazhu 发表于 2015-5-16 05:19:15 | 显示全部楼层
jokebill 发表于 2015-5-16 04:51
不好意思,写的example自己看漏了,是要考虑两个c多除一次2!的
. Waral 鍗氬鏈夋洿澶氭枃绔,
大数模运算是因为如果不这样,即使用lo ...

多谢分享! 你这么厉害竟然onsite也栽了,我都有点不敢去面了。 找了朋友帮忙内推, 今天跟recruiter打电话,说可以让我选择做OA还是skype interview,我想了想觉得还是skype interview有可能好过点 😓
回复 支持 反对

使用道具 举报

 楼主| jokebill 发表于 2015-5-16 05:38:19 | 显示全部楼层
huahuazhu 发表于 2015-5-16 05:19. 鍥磋鎴戜滑@1point 3 acres
多谢分享! 你这么厉害竟然onsite也栽了,我都有点不敢去面了。 找了朋友帮忙内推, 今天跟recruiter打电 ...

我倒觉得OA容易,反正都知道题目,提前写好,自己设计点test case就是了,skype就不知道会不会遇杀手了。
回复 支持 反对

使用道具 举报

huahuazhu 发表于 2015-5-16 06:13:29 | 显示全部楼层
ai  不晓得了, 我看了OA的题目,感觉都是不会做的,除非提前练过的。 但是test 4这个,我到现在都还想不明白第二题要怎么写,虽然数学上终于想通了。而且很怕遇到OA换题库
回复 支持 反对

使用道具 举报

huahuazhu 发表于 2015-5-18 14:05:54 | 显示全部楼层
jokebill 发表于 2015-5-16 04:51
不好意思,写的example自己看漏了,是要考虑两个c多除一次2!的

大数模运算是因为如果不这样,即使用lo ...

今天写了permutation这个题目, 带模的乘法还是不懂什么意思。 现在我算factorial还是最土的不考虑溢出的算法。

带模的加减乘除,有什么wiki可以看看介绍之类的么? 数学上还没想明白。我不理解的地方是,如果现在‘乘法’的输出,是对某个大质数P求模的余数结果,这种等价性啥的咋处理的?譬如n1*n2的结果,跟(n1%P)模乘(n2%P) 的结果,怎么等价起来的? 这个地方很晕
回复 支持 反对

使用道具 举报

 楼主| jokebill 发表于 2015-5-19 04:05:57 | 显示全部楼层
回复 支持 反对

使用道具 举报

Wannuc1 发表于 2015-5-21 23:02:38 | 显示全部楼层
huahuazhu 发表于 2015-5-15 13:48
多谢楼主分享,能再展开讲讲么? 我很多看不明白的 😓

permutation那题,“先看第一个字符,所有 ...

找三角形的算法不太明白,你的算法能找到所有的三角形吗,能举个例子说具体点吗?
回复 支持 反对

使用道具 举报

 楼主| jokebill 发表于 2015-5-22 00:21:22 | 显示全部楼层
Wannuc1 发表于 2015-5-21 23:02
找三角形的算法不太明白,你的算法能找到所有的三角形吗,能举个例子说具体点吗?

其实所谓图里面的三角型,就是只含三个顶点的环,比如下面这个邻接矩阵.鏈枃鍘熷垱鑷1point3acres璁哄潧

0 1 1 0 0. From 1point 3acres bbs
1 0 1 0 0. more info on 1point3acres.com
1 1 0 1 1. from: 1point3acres.com/bbs
0 0 1 0 1. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
0 0 1 1 0. more info on 1point3acres.com

就应该找到两个三角型
回复 支持 反对

使用道具 举报

Wannuc1 发表于 2015-5-22 01:29:10 | 显示全部楼层
Wannuc1 发表于 2015-5-21 23:02
找三角形的算法不太明白,你的算法能找到所有的三角形吗,能举个例子说具体点吗?

你的题意我理解了,不过你的算法为什么是N^2的呢?比如你举的例子,找到点1,它与点2,3相连,那么我要check点2,3是否有边,有,所以这是一个类型。以此类推,以点2,3,4,5分别作基点查找可能的三角形,最后总数除以3,得到unique的三角形。不过我的这个办法应该是N^3的,你的N^2的方法是什么呢?你在上面提了一下,可是我没看懂,能具体说说嘛?. 1point 3acres 璁哄潧
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
补充内容 (2015-5-22 01:31):. 1point3acres.com/bbs
所以这是一个类型 --->>> 所以这是一个三角形
回复 支持 反对

使用道具 举报

d1987115w 发表于 2015-5-26 04:08:26 | 显示全部楼层
请教lz triangle那题 能不能解释下O(N方)的方法,还有用hashmap存的是什么呢?非常感谢
回复 支持 反对

使用道具 举报

volcano 发表于 2015-6-11 16:12:00 | 显示全部楼层
楼主能解释下  6 / 4 (under mod 9) = 6  吗? 没太懂
回复 支持 反对

使用道具 举报

zihunlei 发表于 2015-6-17 22:47:38 | 显示全部楼层
楼主你好,可以分享下第一题的算法和输入输出的例子吗?. visit 1point3acres.com for more.
以及第二题题目开始我就没看懂 可以解释一下吗?
我写了一个第一题的code 估计跟你们的思路都不大一样,因为我不太懂算法,本来是投前端的,不知道怎么就弄到了第四个测试,要死人的。
我的算法大概是先吧输入快拍一下,
然后一个切入点x, 一个剩余票数作参数, 例如切入点是x, 把这个array分成了两段,[f(n)----f(x)][f(x+1)----f(0)]. Waral 鍗氬鏈夋洿澶氭枃绔,
然后[x--n]这几个窗口当前售票,直到他们全部票数都跟f(x+1)一样的时候,切入点就变成了x+1。
然后出递归的口当然就是票没了, 加上各种边缘判断。
楼主的code应该没有了,能把思路和陷阱再详细给我说下嘛? 原谅我是个小白. Waral 鍗氬鏈夋洿澶氭枃绔,

回复 支持 反对

使用道具 举报

 楼主| jokebill 发表于 2015-6-19 01:22:26 | 显示全部楼层
前阵子太忙都没回来看,统一回复下楼上各位吧

三角型的算法我又看了下,好像我后来给的也还是N^3的,我觉得这个题最少也要N^2,因为至少得遍历所有可能的edge吧,但是想了很久也没想出真的N^2的算法
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
6 / 4 (under mod 9) = 6 是因为 (4*6) mod 9 = 6,模除运算实际上是找一个数和除数模乘,结果是被除数,就对了. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴

OA 第一题,输入是一个数一个数读的,直接按票数存到一个map里面,key是票数,value是有这么多票的。c++里面map是递增排序的,记得取票的时候要用reverse iterator。你的方法还是一张一张取,这样大数据集是过不了的,你得一次性把票数最多的窗口取到和票数第二多的窗口一样,然后把这些窗口合并在一起,再一次性取到和票数第三多的窗口一样,依此类推

OA 第二题 看这个吧,写的比较详细 http://www.geeksforgeeks.org/lexicographic-rank-of-a-string/ 思路一样的,但是要想过大数据集,需要自己定义模加减乘除运算,其中模除算法题目里面会给,直接用就行
回复 支持 反对

使用道具 举报

volcano 发表于 2015-6-22 10:48:19 | 显示全部楼层
jokebill 发表于 2015-6-19 01:22
前阵子太忙都没回来看,统一回复下楼上各位吧

三角型的算法我又看了下,好像我后来给的也还是N^3的,我 ...

多谢LZ回复!
三角形的算法我google了一下,应该是不可能做到O(N^2),  目前看到的子最优解有两种, 一种是O(V*E), V is the number of vertces E the number of edges, 还一种是 O(E^1.5), 因为E最大可能是V^2, 所以worse case怎么来说都是O(N^2). Waral 鍗氬鏈夋洿澶氭枃绔,

补充内容 (2015-6-22 10:49):
说错。应该是Worst case怎么来说都是O(N^3)
回复 支持 反对

使用道具 举报

小桶 发表于 2015-6-26 05:29:29 | 显示全部楼层
请教下LZ,hamming distance那道题,每一个unsigned int是不是也是看做binary number比较啊?还是说看成十进制数字?网上搜了搜,似乎hamming distance都是字符串或者二进制形式的。
回复 支持 反对

使用道具 举报

辉哥哥 发表于 2015-6-27 07:17:44 | 显示全部楼层
第二轮另一个小印,上来直接问coding题,vector of unsigned int,求两两之间hamming distance之和,要求O(n)时间。

这一题怎么做到O(n) 呢, 求俩俩之间的距离不是至少要O(n^2) * dist(a, b)吗
回复 支持 反对

使用道具 举报

 楼主| jokebill 发表于 2015-6-30 00:35:38 | 显示全部楼层
小桶 发表于 2015-6-26 05:29
请教下LZ,hamming distance那道题,每一个unsigned int是不是也是看做binary number比较啊?还是说看成十 ...

对,看成binary number
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-6 19:01

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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