zenefit 电面 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

zenefit 电面

zenefit 电面# JobHunting - 待字闺中

n*52015-04-07 07:04

1 楼

给一个矩阵，只含有1,0 。可以翻转一次。可以翻转任意两个index之间所有的值，翻
转就是
1 -->0 0 -- >1
要求只翻转一次，希望翻转之后的矩阵里面的1 的个数最多。求翻转一次，矩阵里面1
的数量的最大值。
比如矩阵 1 0 0 1 0 0 1 0
可以
翻转 [1, 5] ⇒ 1 1 1 0 1 1 1 0
或者
翻转 [1, 7] ⇒ 1 1 1 0 1 1 0 1
矩阵里面1的个数都是6，
这个是一次翻转之后，矩阵1的个数的最大值。
只用返回这个6就行了。
面试的人说他可以只用两个变量来完成。
我跪了之后想了很久。
可以只便利数组一次。
纪录 1出现的次数 n1
一个counter ，如果 0出现 counter 加加，如果1出现，counter 减减.counter小于0
就直接纪录为0。找到counter变化过程中的最大值。
返回n1 加 counter 最大值。
Q：
什么是 IoC
什么是 repository pattern
task-based model 与 threaded model 的区别
希望我的尸体能有点用...

y*e2015-04-07 07:04

2 楼

天，后面的Q完全不会啊。。。

a*52015-04-07 07:04

3 楼

比俩月之前的BAR提高了好多

z*e2015-04-07 07:04

4 楼

赞,继续加油.

e*72015-04-07 07:04

5 楼

确实……好难啊

T*u2015-04-07 07:04

6 楼

第一题dp吗？

z*e2015-04-07 07:04

7 楼

嗯,dp,我觉得是max sum 变种

p*82015-04-07 07:04

8 楼

什么是最大1的个数？

【在 n*****5 的大作中提到】

: 给一个矩阵，只含有1,0 。可以翻转一次。可以翻转任意两个index之间所有的值，翻
: 转就是
: 1 -->0 0 -- >1
: 要求只翻转一次，希望翻转之后的矩阵里面的1 的个数最多。求翻转一次，矩阵里面1
: 的数量的最大值。
: 比如矩阵 1 0 0 1 0 0 1 0
: 可以
: 翻转 [1, 5] ⇒ 1 1 1 0 1 1 1 0
: 或者
: 翻转 [1, 7] ⇒ 1 1 1 0 1 1 0 1

l*n2015-04-07 07:04

9 楼

楼主好人，bless楼主继续拿到大offer。
那个。。。能解释一下第一题求最大的1的个数是个神马意思吗。。。？

n*52015-04-07 07:04

10 楼

抱歉，更新了题目...

f*y2015-04-07 07:04

11 楼

多谢分享！
算法题的描述有点看不懂。
Q的问题，我都不知道啊。有大牛解释解释吗？
顺便问一下楼主面的职位是不是和这些问题有关？

p*g2015-04-07 07:04

12 楼

给你一个这个吧，两个变量的做不出。
public static int maxOnes3(int[] A) {
if (A == null || A.length == 0)
return 0;
int max = 0;
int last = (A[0] == 0 ? 1 : 0);
int cur;
int num = A[0];
for (int i = 1; i < A.length; i++) {
num += A[i];
cur = last + (A[i] == 0 ? 1 : -1);
if (cur < 0)
cur = 0;
if (cur > max) {
max = cur;
}
last = cur;
}
return num + max;
}

p*82015-04-07 07:04

13 楼

谢谢，你的方法是对的，就是加强版的max sum, 不过这要求太高了吧，电面就这么难

【在 n*****5 的大作中提到】

: 抱歉，更新了题目...

p*g2015-04-07 07:04

14 楼

大家努力刷题吧，以后bar会越来越高的。
都是中国人自己刷上去的，和高考一样，很快衡水一中模式就到北美了。
我自己哭会去了。

【在 p*******8 的大作中提到】

: 谢谢，你的方法是对的，就是加强版的max sum, 不过这要求太高了吧，电面就这么难

S*d2015-04-07 07:04

15 楼

int maxOneAfterFlip(vector & arr)
{
int n = arr.size();
int count = 0;
int maxLen = 0;
int one = 0;
int zero = 0;
int i = 0;
for (; i < n && arr[i] == 1; ++i, maxLen++);
--n;
for (; i <= n && arr[n] == 1; --n, maxLen++);
for (; i <= n; i++)
{
if (arr[i] == 1)
{
one++;
}
else
{
zero++;
}

if (zero <= one)
{
maxLen += one;
zero = 0;
one = 0;
}

}
maxLen += (zero >= one?zero: one);
return maxLen;
}

c*m2015-04-07 07:04

16 楼

可以想像成leetcode best time to buy and sell stock的变种
1翻转成0相当于股价下跌，0翻转成1相当于股价上升。最大化1的区间就是股票最大获
利区间
https://leetcode.com/problems/best-time-to-buy-and-sell-stock/