一亩三分地论坛

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

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

zenefits OA#2

[复制链接] |试试Instant~ |关注本帖
gzwenyue 发表于 2015-4-5 06:01:50 | 显示全部楼层 |阅读模式

2015(1-3月) 码农类 硕士 全职@zenefits - 网上海投 - 在线笔试 |Otherfresh grad应届毕业生

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

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

x
刚做完的#2 OA, 看地里没有,就发上来吧
1. bits flip. 大意就是有一串0,1的数组,然后可以取中间任意一段,把0置换为1,1置换为0. 问这样一次置换之后,这组数组最多还有多少个1
2. uneaten leaves. 可以谷歌找到。大意就是给你一个数N,以及一个数组,让你统计在1到N之间,不能被这个数组里的数 整除的数的个数。

大家好运,顺便求大米

评分

4

查看全部评分

本帖被以下淘专辑推荐:

 楼主| gzwenyue 发表于 2015-4-24 23:11:49 | 显示全部楼层
mstc123 发表于 2015-4-24 23:03
这个要用二维数组DP把?第一存开始index,第二个存结束index?

不用啊,其实连数组都不用
def sol(word):. From 1point 3acres bbs
      l=len(word)
      count=word.count('1') # 初始的‘1’的个数
      temp=0
      res=0
      for i in range(l):
           if word=='0':
               temp+=1
           else:
               temp-=1. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
           temp=max(0,temp) # 结尾为i的substring 所能含有最多的 ‘0’ overcome ‘1’的值。 为负时就取0
           res=max(res,temp) # 到i为止, 之前所有substring 所能含有 最多的 ‘0’ overcome ‘1’的值
     return count+res # 返回初始值 加上 overcome的值
回复 支持 2 反对 0

使用道具 举报

averillzheng 发表于 2015-4-7 09:51:05 | 显示全部楼层
为什么第二题总有两个test case是time out 过不去呢?
回复 支持 反对

使用道具 举报

 楼主| gzwenyue 发表于 2015-4-7 11:22:20 | 显示全部楼层
averillzheng 发表于 2015-4-7 09:51
为什么第二题总有两个test case是time out 过不去呢?
. from: 1point3acres.com/bbs
因为N在极限条件下太大了,所以memory size不够,或者就是纯粹的时间太长了。这里考虑k<=15,可以利用几个数之间的最小公倍数来接这个问题,大意就是N1=sum(int(N/c1i)),这里c1i是array里的元素 N2=N1-sum(int(N/c2i)),c2i是两两元素的最小公倍数。 N3=N2+sum(int(N/c3i)), c3i是每三个元素的最小公倍数....一直算Nk就是答案了 http://www.careercup.com/question?id=5288825291014144
回复 支持 反对

使用道具 举报

averillzheng 发表于 2015-4-7 11:33:47 | 显示全部楼层
gzwenyue 发表于 2015-4-7 11:22
因为N在极限条件下太大了,所以memory size不够,或者就是纯粹的时间太长了。这里考虑k

没有用。我try了。过不了
回复 支持 反对

使用道具 举报

averillzheng 发表于 2015-4-7 11:35:50 | 显示全部楼层
不知道你是怎么搞的。我用的inclusion-exclusion principle做了。写了一个找最小公倍数的方法。然后用dfs的方法去找所有的组合,然后算他们的最小公倍数。还是过不了。
回复 支持 反对

使用道具 举报

averillzheng 发表于 2015-4-7 11:36:01 | 显示全部楼层
不知道你是怎么搞的。我用的inclusion-exclusion principle做了。写了一个找最小公倍数的方法。然后用dfs的方法去找所有的组合,然后算他们的最小公倍数。还是过不了。
回复 支持 反对

使用道具 举报

averillzheng 发表于 2015-4-7 11:36:09 | 显示全部楼层
不知道你是怎么搞的。我用的inclusion-exclusion principle做了。写了一个找最小公倍数的方法。然后用dfs的方法去找所有的组合,然后算他们的最小公倍数。还是过不了。
回复 支持 反对

使用道具 举报

averillzheng 发表于 2015-4-7 11:38:51 | 显示全部楼层
最后搞到有一个case过不了。test case 10 没有过。
回复 支持 反对

使用道具 举报

 楼主| gzwenyue 发表于 2015-4-7 12:08:43 | 显示全部楼层
averillzheng 发表于 2015-4-7 11:38
最后搞到有一个case过不了。test case 10 没有过。

其实我也没全通过。不过昨天hr反馈过来的情况说是挺好的,所以也别太担心啦
回复 支持 反对

使用道具 举报

averillzheng 发表于 2015-4-7 16:53:37 | 显示全部楼层
gzwenyue 发表于 2015-4-7 12:08. 1point3acres.com/bbs
其实我也没全通过。不过昨天hr反馈过来的情况说是挺好的,所以也别太担心啦

你有几个没有通过?
回复 支持 反对

使用道具 举报

 楼主| gzwenyue 发表于 2015-4-7 20:06:48 | 显示全部楼层
averillzheng 发表于 2015-4-7 16:53 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
你有几个没有通过?

一开始试了两种简单的方法,case 6 和 10 时间太长过不了。后来换了这个方法,变成4个case过不了了。编的程序里面可能有bug吧,但他们的case又不给数据,debug半天也没找到问题在哪。随缘吧
回复 支持 反对

使用道具 举报

zhh1991 发表于 2015-4-8 09:11:17 | 显示全部楼层
averillzheng 发表于 2015-4-7 16:53. from: 1point3acres.com/bbs
你有几个没有通过?
. Waral 鍗氬鏈夋洿澶氭枃绔,
我开始最后一个也没过 最后一个test case应该是几条虫子的LCM太大 overflow了Int的最大值 改成long就过了
回复 支持 反对

使用道具 举报

nelson16 发表于 2015-4-14 13:06:01 | 显示全部楼层
晕 我一次就过了.... 也是inclusive exclusive做得 不过没有dfs, 直接遍历1 到 2^m 种可能
回复 支持 反对

使用道具 举报

summerjx 发表于 2015-4-24 02:38:43 | 显示全部楼层
第一题能仔细讲讲吗 不是很理解题意
回复 支持 反对

使用道具 举报

 楼主| gzwenyue 发表于 2015-4-24 03:17:06 | 显示全部楼层
summerjx 发表于 2015-4-24 02:38
第一题能仔细讲讲吗 不是很理解题意

哪一块不理解啊?
回复 支持 反对

使用道具 举报

summerjx 发表于 2015-4-24 03:44:44 | 显示全部楼层
gzwenyue 发表于 2015-4-24 03:17
哪一块不理解啊?

所以其实就是找包含最多0的子串吗
回复 支持 反对

使用道具 举报

 楼主| gzwenyue 发表于 2015-4-24 04:04:07 | 显示全部楼层
summerjx 发表于 2015-4-24 03:44
所以其实就是找包含最多0的子串吗

其实是要找 0的数量减去1的数量最多的子串。 1要变成0的
回复 支持 反对

使用道具 举报

summerjx 发表于 2015-4-24 04:50:47 | 显示全部楼层
gzwenyue 发表于 2015-4-24 04:04. 鍥磋鎴戜滑@1point 3 acres
其实是要找 0的数量减去1的数量最多的子串。 1要变成0的

哦 对哦 所以你是怎么做的? DP?
回复 支持 反对

使用道具 举报

 楼主| gzwenyue 发表于 2015-4-24 07:33:43 | 显示全部楼层
summerjx 发表于 2015-4-24 04:50
哦 对哦 所以你是怎么做的? DP?

恩。 就是dp, 取到0就+1, 取到1就-1, o(n)的时间复杂度
回复 支持 反对

使用道具 举报

头像被屏蔽
mstc123 发表于 2015-4-24 23:03:18 | 显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-9 08:23

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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