一亩三分地论坛

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

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

Zenefits OA test2

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

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

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

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

x
第一题 .鏈枃鍘熷垱鑷1point3acres璁哄潧

You are given a binary array with N elements: d[0], d[1], ... d[N - 1].
You can perform AT MOST one move on the array: choose any two integers [L, R], and flip all the elements between (and including) the L-th and R-th bits. L and R represent the left-most and right-most index of the bits marking the boundaries of the segment which you have decided to flip.  

What is the maximum number of '1'-bits (indicated by S) which you can obtain in the final bit-string?

'Flipping' a bit means, that a 0 is transformed to a 1 and a 1 is transformed to a 0 Input Format
An integer N
Next line contains the N bits, separated by spaces: d[0] d[1] ... d[N - 1]

Output:
S

Sample Input:
8
1 0 0 1 0 0 1 0
.鐣欏璁哄潧-涓浜-涓夊垎鍦
Sample Output:
6
说白了就是一个包含1和0的数组 翻转其中连续的一部分 求一次翻转后1最多有多少个。此题一开始超时,后来用滑动窗口过了。
附代码:
def  bitFlip(arr):.1point3acres缃
    maxcount = 0.鏈枃鍘熷垱鑷1point3acres璁哄潧
    count = 0
    for i in range(len(arr)): 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
        count = max(0, count)
        count += 1 if arr == 0 else -1
        maxcount = max(maxcount, count)
    return arr.count(1) + maxcount. visit 1point3acres.com for more.
 楼主| ijk5554234 发表于 2015-5-4 06:43:12 | 显示全部楼层
第二题就是虫吃叶子的题 给定一个int作为叶子的数量,再给一个数组,其中每个数代表一个虫行走的步数, 求没有被吃掉的叶子数量。 比如n = 100, bug = {2,5}, 那么一百片叶子中号码是2或者5的倍数的叶子全部被吃掉了。

此题一开始用暴力法超时,后来用最小公因数最大公倍数的方法还是有几个case超时, 最后实在不想写就直接提交了。自己觉得这题代码写得很烂
        public static int eat2(int n, int[] b) {
                HashSet<Integer> set = new HashSet<Integer>();
                for (int x : b) {
                        boolean test = false;
                        for (int y : set) {
                                if (x % y == 0){
                                        test = true;
                                        break;
                                }
                                if (y % x == 0){
                                        test = true;
                                        set.remove(y);
                                        set.add(x);
                                        break;
                                }
                        }
                        if (!test) set.add(x);. 1point 3acres 璁哄潧
                }
               
                int cm = 1;
                while (true) {
                        boolean test = true;
                        for (int x : set) {
                                if (x > cm || cm % x != 0) {
                                        test = false;
                                        break;
                                }
                        }
                        if (test) break;
                        cm++;
                }
                int count = 0;
                for (int i = 1; i <= cm; i++) {
                        boolean test = false;
                        for (int x : set) {. 1point 3acres 璁哄潧
                                if (i >= x && (i % x == 0)) {
                                        test = true;
                                        break;. Waral 鍗氬鏈夋洿澶氭枃绔,
                                }               
                        }
                        if (test) count++;
                }. from: 1point3acres.com/bbs
                int time = n / cm;
                int rest = n % cm;
                int sum = time * count;
               
                for (int i = 1; i <= rest; i++) {
                        boolean test = false;
                        for (int x : set) {. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
                                if (i >= x && i % x == 0) {
                                        test = true;
                                        break;. Waral 鍗氬鏈夋洿澶氭枃绔,
                                }

                        }. From 1point 3acres bbs
                        if (test) sum++;
                }-google 1point3acres
                return n - sum;
        }
回复 支持 反对

使用道具 举报

丸小西 发表于 2015-5-5 13:36:15 | 显示全部楼层
我也刚做完,题目一模一样。
感觉第一题有点想lc上面 maximum subarray的改变。
第二题如果用inclusive exclusive principle, 可以分解成lc上面subset + LCM
回复 支持 反对

使用道具 举报

d1987115w 发表于 2015-5-10 16:08:32 | 显示全部楼层
丸小西 发表于 2015-5-5 13:36.鐣欏璁哄潧-涓浜-涓夊垎鍦
我也刚做完,题目一模一样。
感觉第一题有点想lc上面 maximum subarray的改变。. from: 1point3acres.com/bbs
第二题如果用inclusive e ...
. from: 1point3acres.com/bbs
想问问 用subset+lcm的解法 能通过所有test case不超时吗?多谢!
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-3 11:03

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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