一亩三分地论坛

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

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

Zenefits电面

[复制链接] |试试Instant~ |关注本帖
solowelkin 发表于 2015-10-6 06:19:52 | 显示全部楼层 |阅读模式

2015(7-9月) 码农类 硕士 全职@Zenefits - 网上海投 - 技术电面 |Passfresh grad应届毕业生

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

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

x
上星期面了Zenefits,做完oa就联系电面了。面试官是年轻印度小哥。
题目:
// Find the largest K such that A^K is a subsequence of B, where A, B are two strings. |A| << |B|.

// Power of a string:
// Let A = xyxz
// Then,
// A^1 = A = xyxz
// A^2 = xxyyxxzz
// A^3 = xxxyyyxxxzzz

// Example:
// A = xyxz
// B = xabyzxz

// B xaybyxzxxxzz

// A xxyyxxzz
一开始思路就是k从1一个个试,不行就返回。找subsequence用dp。但是面试官说复杂度太高,就想到用双指针遍历。然后问了时间复杂度。
写好后他还要improve.想到用二分查找k.因为最小是1,最大是B.length()/A.length();

已拿到onsite邀请。

问问地里小伙伴,有没有最近onsite Zenefits的,是remotely skype 还是去总部?

评分

2

查看全部评分

本帖被以下淘专辑推荐:

 楼主| solowelkin 发表于 2015-10-13 22:23:26 | 显示全部楼层
returning 发表于 2015-10-13 10:39
这题怎么能用二分查找k呢,如果x^(K+1)是y的自字符串,不代表x^(K)是y的子字符串啊,或者我理解错了?

subsequence是不需要连续的。如果x^(K+1)是y的subsequence,x^(K)一定是y的subsequence
回复 支持 1 反对 0

使用道具 举报

hanchen999 发表于 2015-10-6 06:34:42 | 显示全部楼层
想问下二分查找是指的每次都做dp, 然后用dp出来的结果是true和false来判断应该向哪边跳?
回复 支持 反对

使用道具 举报

 楼主| solowelkin 发表于 2015-10-6 06:40:25 | 显示全部楼层
hanchen999 发表于 2015-10-6 06:34
想问下二分查找是指的每次都做dp, 然后用dp出来的结果是true和false来判断应该向哪边跳?

对,你的理解是对的,但是这题不用dp,简单地双指针返回true或false.
回复 支持 反对

使用道具 举报

ChrisGates23 发表于 2015-10-6 07:15:33 | 显示全部楼层
请问lz   // A^1 = A = xyxz // A^2 = xxyyxxzz // A^3 = xxxyyyxxxzzz  这是什么意思   字符串异或数字得到新的字符串?
回复 支持 反对

使用道具 举报

breaking 发表于 2015-10-6 07:26:39 | 显示全部楼层
楼主, 请问zenefit 的 OA 还是1-4四套吗?
回复 支持 反对

使用道具 举报

 楼主| solowelkin 发表于 2015-10-6 22:08:59 | 显示全部楼层
ChrisGates23 发表于 2015-10-6 07:15
请问lz   // A^1 = A = xyxz // A^2 = xxyyxxzz // A^3 = xxxyyyxxxzzz  这是什么意思   字符串异或数字得 ...

power of string, 就是每个character重复几次
回复 支持 反对

使用道具 举报

 楼主| solowelkin 发表于 2015-10-6 22:09:13 | 显示全部楼层
breaking 发表于 2015-10-6 07:26. From 1point 3acres bbs
楼主, 请问zenefit 的 OA 还是1-4四套吗?

对。我做的2
回复 支持 反对

使用道具 举报

majiamajia 发表于 2015-10-6 23:50:10 | 显示全部楼层
双指针遍历能详细点说么= =
回复 支持 反对

使用道具 举报

 楼主| solowelkin 发表于 2015-10-7 00:04:18 | 显示全部楼层
majiamajia 发表于 2015-10-6 23:50
双指针遍历能详细点说么= =

比如找a是否在b里出现。 就是两个指针 一个i从a开始 一个j从b开始 如果a==b[j] 那就 i++; j++, 否则 j++. 最后i到头了说明a在b里。 j到头了说明a不在b里。。
回复 支持 反对

使用道具 举报

majiamajia 发表于 2015-10-7 00:05:57 | 显示全部楼层
solowelkin 发表于 2015-10-7 00:04-google 1point3acres
比如找a是否在b里出现。 就是两个指针 一个i从a开始 一个j从b开始 如果a==b[j] 那就 i++; j++, 否则 j++. ...

那怎么算K咧……如果a连续出现了几次就算K等于多少么。。。所以感觉纯暴力。。?
回复 支持 反对

使用道具 举报

majiamajia 发表于 2015-10-7 00:41:58 | 显示全部楼层
solowelkin 发表于 2015-10-7 00:04. Waral 鍗氬鏈夋洿澶氭枃绔,
比如找a是否在b里出现。 就是两个指针 一个i从a开始 一个j从b开始 如果a==b[j] 那就 i++; j++, 否则 j++. ...

或者您是对每一种K,都暴力双指针找的吗~
回复 支持 反对

使用道具 举报

breaking 发表于 2015-10-7 03:43:34 | 显示全部楼层

oa系统支持python吗?
回复 支持 反对

使用道具 举报

 楼主| solowelkin 发表于 2015-10-7 04:01:54 | 显示全部楼层
majiamajia 发表于 2015-10-7 00:41
或者您是对每一种K,都暴力双指针找的吗~

我写的第一种解法是对每一个k都要进行双指针。后来又写了对k二分查找,当然还是双指针。
回复 支持 反对

使用道具 举报

 楼主| solowelkin 发表于 2015-10-7 04:03:23 | 显示全部楼层
breaking 发表于 2015-10-7 03:43
oa系统支持python吗?

我不太记得了。。用的hackerrank
回复 支持 反对

使用道具 举报

1064no1carry 发表于 2015-10-7 07:22:46 | 显示全部楼层
想问下楼主一小时就一题吗?
回复 支持 反对

使用道具 举报

 楼主| solowelkin 发表于 2015-10-7 10:18:25 | 显示全部楼层
1064no1carry 发表于 2015-10-7 07:22
想问下楼主一小时就一题吗?

3个小时两题。。时间很宽裕
回复 支持 反对

使用道具 举报

1064no1carry 发表于 2015-10-10 06:01:51 | 显示全部楼层
solowelkin 发表于 2015-10-7 10:18
3个小时两题。。时间很宽裕

. 鍥磋鎴戜滑@1point 3 acres这是OA吧?电面呢?
回复 支持 反对

使用道具 举报

 楼主| solowelkin 发表于 2015-10-11 01:12:16 | 显示全部楼层
1064no1carry 发表于 2015-10-10 06:01
这是OA吧?电面呢?
. more info on 1point3acres.com
嗯 就这一题。做题之前问一下简历,之后问有啥问题。
回复 支持 反对

使用道具 举报

sc.77885 发表于 2015-10-13 08:58:50 | 显示全部楼层
求问电面的时候skype要开webcam吗?
回复 支持 反对

使用道具 举报

lukeken 发表于 2015-10-13 10:00:12 | 显示全部楼层
solowelkin 发表于 2015-10-7 00:04
比如找a是否在b里出现。 就是两个指针 一个i从a开始 一个j从b开始 如果a==b[j] 那就 i++; j++, 否则 j++. ...

这题是不是不要求a是b的连续子序列?并问楼主是怎么拿到zenefits面试的
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-9 04:30

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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