logo
Redian新闻
>未名空间
>JobHunting - 待字闺中
>
发个刚面完的rocket fuel的面经吧
avatar
发个刚面完的rocket fuel的面经吧# JobHunting - 待字闺中
j*s
1 楼
刚面完的，两道题。
（1）给一个unsigned int数组，size为n，数组的sum = a，计算一个k的值，将数组中
所有大于k的数改为k之后，数组的sum变为b。Ex, [1,2,5,7,7,8] = a = 30, b = 26,
那么k = 6，因为[1,2,5,6,6,6] = 26。
要求时间复杂度是n*logn.
(2)给一张L*W的纸，给一堆 l(i)* w(i)的模板，每个size的模板有各自的price p(i)
，求这张纸所能剪出的最大值。
应该是挂了，我一面阿三就发怵，光弄清楚他的问题描述就得每道题5分钟。
第一题思路：
for example:
[4,6,87,93,46,8] = 244
50 = k
target [4,6,50,50,46,8] = 164
after sort [4,6,8,46,87,93]
4 * 6 = 24
[2,4,42,83,89]
2 * 5 = 10 + 24 = 34
[2,40,81,87]
2 * 4 = 8 + 34 = 42
[38,79,85]
38 * 3 = 114 + 42 = 156
[41, 47]
we don't keep going because 156 + 41 > 164
there are 2 numbers left in the array.
so, 164 - 156 = 8
46 + 8/2 = 50, this is the k we want
第二题思路：
DP。
状态转移方程：
value[i][j] = max{
max{value[k][j] + value[i-k][j]},
max{value[i][m] + value[i][j - m]}
}
0< k < i, 0< m < j
avatar
c*m
2 楼
我觉得这家的面试题真不容易啊，比google的都难啊
avatar
j*s
3 楼
嗯，我也这么觉得

【在 c*********m 的大作中提到】
: 我觉得这家的面试题真不容易啊，比google的都难啊
avatar
c*m
4 楼
你这两题程序写得如何啊？感觉30分钟时间不够，写不完啊。。

【在 j*****s 的大作中提到】
: 嗯，我也这么觉得
avatar
f*e
5 楼
第二题应该是NP吧？可以剪成小块再粘起来吗？想微积分那样的。

26,

【在 j*****s 的大作中提到】
: 刚面完的，两道题。
: （1）给一个unsigned int数组，size为n，数组的sum = a，计算一个k的值，将数组中
: 所有大于k的数改为k之后，数组的sum变为b。Ex, [1,2,5,7,7,8] = a = 30, b = 26,
: 那么k = 6，因为[1,2,5,6,6,6] = 26。
: 要求时间复杂度是n*logn.
: (2)给一张L*W的纸，给一堆 l(i)* w(i)的模板，每个size的模板有各自的price p(i)
: ，求这张纸所能剪出的最大值。
: 应该是挂了，我一面阿三就发怵，光弄清楚他的问题描述就得每道题5分钟。
: 第一题思路：
: for example:
avatar
G*A
6 楼
这两道题onsite肯定拿不下来啊
1. 算是binary search的一个应用。2分法找pivot，对于每个pivot计算相应的
expected k. 如果expected k和当前pivot的位置吻合(i.e., k >= A[pivot] && k <=
A[pivot + 1])，则返回k
2. 他应该不是想求最优解吧？！能不能给个heuristic？ 排序 p(i) / (l(i) * w(i))
,然后顺序选取。

26,

【在 j*****s 的大作中提到】
: 刚面完的，两道题。
: （1）给一个unsigned int数组，size为n，数组的sum = a，计算一个k的值，将数组中
: 所有大于k的数改为k之后，数组的sum变为b。Ex, [1,2,5,7,7,8] = a = 30, b = 26,
: 那么k = 6，因为[1,2,5,6,6,6] = 26。
: 要求时间复杂度是n*logn.
: (2)给一张L*W的纸，给一堆 l(i)* w(i)的模板，每个size的模板有各自的price p(i)
: ，求这张纸所能剪出的最大值。
: 应该是挂了，我一面阿三就发怵，光弄清楚他的问题描述就得每道题5分钟。
: 第一题思路：
: for example:
avatar
k*2
7 楼
第一题能否展开说说？我觉得毫无思路啊。。

=
))

【在 G****A 的大作中提到】
: 这两道题onsite肯定拿不下来啊
: 1. 算是binary search的一个应用。2分法找pivot，对于每个pivot计算相应的
: expected k. 如果expected k和当前pivot的位置吻合(i.e., k >= A[pivot] && k <=
: A[pivot + 1])，则返回k
: 2. 他应该不是想求最优解吧？！能不能给个heuristic？ 排序 p(i) / (l(i) * w(i))
: ,然后顺序选取。
:
: 26,
avatar
a*a
8 楼
这个解法如何，是nlogn 的吧。
第一题
const int b=26;
const int a[6]={1,2,5,7,7,8};
int l=a[0],m=a[5],k,sum=0;
while(l{
k=(l+m)/2;
sum=0;
for(int i=0;i<6;i++)
{
if(a[i]else sum+=k;
}
if(sum>b)
{
m=k;
}
else if (sum{
l=k;
}
else
return k;

}
avatar
e*s
9 楼
请问第一题就是 0 ～ max 之间 二叉查找吗？
avatar
e*s
10 楼
b = 0 怎么办？

【在 a******a 的大作中提到】
: 这个解法如何，是nlogn 的吧。
: 第一题
: const int b=26;
: const int a[6]={1,2,5,7,7,8};
: int l=a[0],m=a[5],k,sum=0;
: while(l: {
: k=(l+m)/2;
: sum=0;
: for(int i=0;i<6;i++)
avatar
a*a
11 楼
不懂

【在 e***s 的大作中提到】
: b = 0 怎么办？
avatar
j*s
12 楼
这个解法我面试的时候说了，但他说不是n*lgn的，你看，你这个依赖于数组中最大和
最小的值，所以，实际上是Lg(max(a)) * n

【在 a******a 的大作中提到】
: 这个解法如何，是nlogn 的吧。
: 第一题
: const int b=26;
: const int a[6]={1,2,5,7,7,8};
: int l=a[0],m=a[5],k,sum=0;
: while(l: {
: k=(l+m)/2;
: sum=0;
: for(int i=0;i<6;i++)
avatar
r*h
13 楼
第一题排序之后从后往前扫应该可以
第二题好难
这题目是电面？30分钟写两题bug free也太牛了

26,

【在 j*****s 的大作中提到】
: 刚面完的，两道题。
: （1）给一个unsigned int数组，size为n，数组的sum = a，计算一个k的值，将数组中
: 所有大于k的数改为k之后，数组的sum变为b。Ex, [1,2,5,7,7,8] = a = 30, b = 26,
: 那么k = 6，因为[1,2,5,6,6,6] = 26。
: 要求时间复杂度是n*logn.
: (2)给一张L*W的纸，给一堆 l(i)* w(i)的模板，每个size的模板有各自的price p(i)
: ，求这张纸所能剪出的最大值。
: 应该是挂了，我一面阿三就发怵，光弄清楚他的问题描述就得每道题5分钟。
: 第一题思路：
: for example:
avatar
j*s
14 楼
是的，是NP，但是不能粘起来。

【在 f*****e 的大作中提到】
: 第二题应该是NP吧？可以剪成小块再粘起来吗？想微积分那样的。
:
: 26,
avatar
j*s
15 楼
第一题，你说扫，怎么扫？假设数组是a[1,2,3,4,5,6,999999],你是从a[6]往a[0]扫，
还是9999999往1扫？但是不管怎样，两种方法都达不到要求。
我面了45分钟吧，第二题只给出了DP的方程，没来得及写代码。那个阿三好烦，在我想
问题的时候也一直在那边打字，搞得我想不进去。

【在 r**h 的大作中提到】
: 第一题排序之后从后往前扫应该可以
: 第二题好难
: 这题目是电面？30分钟写两题bug free也太牛了
:
: 26,
avatar
c*9
16 楼
第一题先sort，然后从前往后扫，直到遇到target - current_sum 除以剩余数的个数
等于某个整数，并且这个整数大于等于当前数并且小于等于下一个数字，返回这个整数
，可以么？
avatar
r*h
17 楼
楼上的方法更简单，还是用那个吧
求第二题解法
第一题本来就不能保证有解吧
你的例子里面b=25怎么办
我想到的解法是，从最后一个元素往数组开头扫，每次找到一个a[i]使得a[i-1]，以及这些元素可以减少到的最小值（也就是a[i-1]）。然后判断将当前所有元素在规
定范围内减小值能否达到要求
比如说你的例子
1,2,5,7,7,8
第一次找到8，总共有n=1个元素，最少可以减少到7，此时a=29>b，继续
第二次找到7，总共n=3个元素，最少可以减少到5、不过减少到5的时候a=23于(b-a)/n = 1，(b-a)%n=0，因此将这三个元素都减少到6即可
时间复杂度O(n log n)也就是排序的时间

【在 j*****s 的大作中提到】
: 第一题，你说扫，怎么扫？假设数组是a[1,2,3,4,5,6,999999],你是从a[6]往a[0]扫，
: 还是9999999往1扫？但是不管怎样，两种方法都达不到要求。
: 我面了45分钟吧，第二题只给出了DP的方程，没来得及写代码。那个阿三好烦，在我想
: 问题的时候也一直在那边打字，搞得我想不进去。
avatar
j*s
18 楼
没太明白你的意思，举个例子？

【在 c****9 的大作中提到】
: 第一题先sort，然后从前往后扫，直到遇到target - current_sum 除以剩余数的个数
: 等于某个整数，并且这个整数大于等于当前数并且小于等于下一个数字，返回这个整数
: ，可以么？
avatar
c*9
19 楼
我也不确定有没有bug
125778
1 (26-1)/5 = 5 大于1 但不小于2 不符合
2 (26-3)/4 非整数
5 (26-8)/3 = 6 大于5 小于等于6 符合 return

【在 j*****s 的大作中提到】
: 没太明白你的意思，举个例子？
avatar
s*r
20 楼
第一题不要这么复杂吧
不考虑溢出
1.先排序 nlog(n)
2.
int sum = a[0];
for (i=1;iif((b-sum)%(n-i-1)==0){
int tmp = (b-sum)/(n-i-1);
if(tmp>=a[i-1]&&tmpreturn tmp;
}
sum+=a[i];
}
return NOT_FIND;

=
))

【在 G****A 的大作中提到】
: 这两道题onsite肯定拿不下来啊
: 1. 算是binary search的一个应用。2分法找pivot，对于每个pivot计算相应的
: expected k. 如果expected k和当前pivot的位置吻合(i.e., k >= A[pivot] && k <=
: A[pivot + 1])，则返回k
: 2. 他应该不是想求最优解吧？！能不能给个heuristic？ 排序 p(i) / (l(i) * w(i))
: ,然后顺序选取。
:
: 26,
avatar
r*h
21 楼
有一个小bug
每次扫描的时候要一次减掉所有连续且有相同值的元素
因为值相同的元素，要么不改变值，要么全改

【在 c****9 的大作中提到】
: 我也不确定有没有bug
: 125778
: 1 (26-1)/5 = 5 大于1 但不小于2 不符合
: 2 (26-3)/4 非整数
: 5 (26-8)/3 = 6 大于5 小于等于6 符合 return
avatar
c*9
22 楼
因为会小于等于下一个元素和大于等于当前元素，似乎不会存在没有减掉所有连续相同
元素的情况。

【在 r**h 的大作中提到】
: 有一个小bug
: 每次扫描的时候要一次减掉所有连续且有相同值的元素
: 因为值相同的元素，要么不改变值，要么全改
avatar
r*h
23 楼
哦，对的
我考虑复杂了

【在 c****9 的大作中提到】
: 因为会小于等于下一个元素和大于等于当前元素，似乎不会存在没有减掉所有连续相同
: 元素的情况。
avatar
h*o
24 楼
嗯，一样的想法。
应该就这样吧。

【在 s*******r 的大作中提到】
: 第一题不要这么复杂吧
: 不考虑溢出
: 1.先排序 nlog(n)
: 2.
: int sum = a[0];
: for (i=1;i: if((b-sum)%(n-i-1)==0){
: int tmp = (b-sum)/(n-i-1);
: if(tmp>=a[i-1]&&tmp: return tmp;
avatar
u*g
25 楼
第二题是个NP。。跟二维背包不一样。。。
avatar
s*s
26 楼
这个方法好！

【在 c****9 的大作中提到】
: 第一题先sort，然后从前往后扫，直到遇到target - current_sum 除以剩余数的个数
: 等于某个整数，并且这个整数大于等于当前数并且小于等于下一个数字，返回这个整数
: ，可以么？
avatar
b*7
27 楼
在[0,n-1]间查找，再减去多余的部分
int adjust(int A[],int n, int b)
{
if(n <= 0 || b < 0) return -1;
sort(A,A+n);
int index = -1;
int cursum = -1;
int low = 0, high = n-1;
while(low <= high)
{
int mid = low + (high - low)/2;
int sum = 0;
for(int i = 0; i < n; i++)
{
sum += min(A[i],A[mid]);
}
if(sum == b) return A[mid];
else if(sum > b)
{
index = mid;
cursum = sum;
high = mid - 1;
}
else
{
low = mid + 1;
}
}//while
if(index == -1) return b % n == 0 ? b/n : -1;
if((cursum - b)%(n-index) != 0) return -1;
return A[index] - (cursum -b)/(n-index);
}
[0,maxvalue]之间二分查找
int adjust(int A[], int n, int b)
{
if(n <= 0 || b < 0) return -1;
int low = 0;
int high = *max_element(A,A+n);
while(low <= high)
{
int mid = low + (high - low)/2;
int sum = 0;
for(int i = 0; i < n; i++)
{
if(A[i] > mid) sum += mid;
else sum += A[i];
}
if(sum == b) return mid;
else if(sum < b)
low = mid + 1;
else
high = mid - 1;
}
return -1;
}
avatar
t*3
28 楼
第二题的思路好像有问题。 比如L*W的纸，正好能被一张模版填满。 这种情况下你就
不能把纸分成两块，每块求最大。

26,

【在 j*****s 的大作中提到】
: 刚面完的，两道题。
: （1）给一个unsigned int数组，size为n，数组的sum = a，计算一个k的值，将数组中
: 所有大于k的数改为k之后，数组的sum变为b。Ex, [1,2,5,7,7,8] = a = 30, b = 26,
: 那么k = 6，因为[1,2,5,6,6,6] = 26。
: 要求时间复杂度是n*logn.
: (2)给一张L*W的纸，给一堆 l(i)* w(i)的模板，每个size的模板有各自的price p(i)
: ，求这张纸所能剪出的最大值。
: 应该是挂了，我一面阿三就发怵，光弄清楚他的问题描述就得每道题5分钟。
: 第一题思路：
: for example:
avatar
t*3
29 楼
第二题，如果是这种情况怎么办？

26,

【在 j*****s 的大作中提到】
: 刚面完的，两道题。
: （1）给一个unsigned int数组，size为n，数组的sum = a，计算一个k的值，将数组中
: 所有大于k的数改为k之后，数组的sum变为b。Ex, [1,2,5,7,7,8] = a = 30, b = 26,
: 那么k = 6，因为[1,2,5,6,6,6] = 26。
: 要求时间复杂度是n*logn.
: (2)给一张L*W的纸，给一堆 l(i)* w(i)的模板，每个size的模板有各自的price p(i)
: ，求这张纸所能剪出的最大值。
: 应该是挂了，我一面阿三就发怵，光弄清楚他的问题描述就得每道题5分钟。
: 第一题思路：
: for example:
avatar
f*m
30 楼
谁能给个第二题的解？
要是一维就好办了
avatar
f*m
31 楼
这题好像是Introduction to algorithms DP那章的课后题
avatar
Y*f
32 楼
这个阿三也太狠了吧，第二题就是二维的背包问题吧。

26,

【在 j*****s 的大作中提到】
: 刚面完的，两道题。
: （1）给一个unsigned int数组，size为n，数组的sum = a，计算一个k的值，将数组中
: 所有大于k的数改为k之后，数组的sum变为b。Ex, [1,2,5,7,7,8] = a = 30, b = 26,
: 那么k = 6，因为[1,2,5,6,6,6] = 26。
: 要求时间复杂度是n*logn.
: (2)给一张L*W的纸，给一堆 l(i)* w(i)的模板，每个size的模板有各自的price p(i)
: ，求这张纸所能剪出的最大值。
: 应该是挂了，我一面阿三就发怵，光弄清楚他的问题描述就得每道题5分钟。
: 第一题思路：
: for example:
avatar
s*r
33 楼
为什么石油公司也考算法？
也要写代码？
avatar
r*e
34 楼
晕，这个rocket fuel是个热门的big data startup，做ads的

【在 s**********r 的大作中提到】
: 为什么石油公司也考算法？
: 也要写代码？
avatar
s*r
35 楼
我2了。。

【在 r*******e 的大作中提到】
: 晕，这个rocket fuel是个热门的big data startup，做ads的
avatar
s*r
36 楼
big data考你machine learning了么？
avatar
x*0
37 楼
mark
avatar
f*m
38 楼
谁能给个第二题的解法？这题和二位背包类似，但是更复杂。
avatar
y*c
39 楼
mark
avatar
e*8
40 楼
rocket fuel第二题可以用linear programming解不？
avatar
H*S
41 楼
一遍排序加一遍顺序遍历
public int solution(int[] array, int b) {
Arrays.sort(array);
int sum = 0;
int n = array.length;
for (int i = 0; i < n; i++) {
if ((b - sum) % (n - i) == 0) {
int m = (b - sum) / (n - i);
if (i == 0 && m >= array[i]) return m;
else if (m >= array[i - 1] && m < array[i]) return m;
}
sum += array[i];
}
return -1;
}
avatar
v*n
42 楼
mark nn【在 houqingniao (候情鸟)的大作中提到：】n：嗯，一样的想法。n：应该就
这样吧。n：【 在 sunfaquir (非礼勿言) 的大作中提到: 】n：: 第一题不要这么复
杂吧n：: 不考虑溢出n：: 1.先排序 nlog(n)n：: 2.n……nn--n[发自未名空间
Android客户端]
avatar
l*s
43 楼
public static int changeArray(int[] n, int a, int b) {
int len = n.length;
Arrays.sort(n);
int sumSoFar = 0;
int test = 0;
int diff = a-b;
boolean done = false;
for (int i = len-1; i>=0; i--) {
sumSoFar += n[i];
test = (sumSoFar - diff) / (len - i);
if (test > n[i-1] && test <= n[i]) {
done = true;
break;
}
}
if (done)
return test;
return Integer.MIN_VALUE;
}
avatar
l*s
44 楼
For 第二题, 随便写了一下，
public static int maxValue(int[] l, int[] w, int[] p, int L, int W) {
int len = l.length;
assert(l.length == w.length && l.length == p.length);
int[] v = new int[len+1];
for (int i=len-1; i>=0; i--) {
if (i == 0) {
if (l[i] > L || w[i] > W) {
v[i] = v[i+1];
} else {
v[i] = v[i+1]+p[i];
}
continue;
}
int[] l1 = Arrays.copyOfRange(l, 0, i-1);
int[] w1 = Arrays.copyOfRange(w, 0, i-1);
int[] p1 = Arrays.copyOfRange(p, 0, i-1);
int opt1 = v[i+1]+ maxValue(l1, w1, p1, L, W); // not using this one
if (l[i] > L || w[i] > W) {
v[i] = opt1;
continue;
}
int opt2 = v[i+1]+ p[i] + Math.max(maxValue(l1, w1, p1, L-l[i], W)+
maxValue(l1, w1, p1, l[i], W-w[i]),
maxValue(l1, w1, p1, L-l[i], w[i]) + maxValue(l1, w1, p1, L, W-w[i]));
v[i] = Math.max(opt1, opt2);
}
return v[0];
}
avatar
l*s
45 楼
2nd question
public static int maxValue(int[] l, int[] w, int[] p, int L, int W) {
assert(l.length == w.length && l.length == p.length);
if (l.length == 0) return Integer.MIN_VALUE;
return maxValueRecur(l, w, p, L, W, 0);
}
public static int maxValueRecur(int[] l, int[] w, int[] p, int L, int W,
int value) {
int len = l.length;
assert(l.length == w.length && l.length == p.length);
if (len == 1) {
if (l[0] > L || w[0] > W)
return value;

return value + p[0];
}
int len1 = len-1;
int[] l1 = Arrays.copyOf(l, len1);
int[] w1 = Arrays.copyOf(w, len1);
int[] p1 = Arrays.copyOf(p, len1);
int opt1 = maxValueRecur(l1, w1, p1, L, W, value); // not using
i
if (l[len1] > L || w[len1] > W) {
return opt1;
}
int opt2 = value + p[len-1] +
Math.max(
maxValue(l1, w1, p1, L-l[len1], W) + maxValue(l1, w1, p1, l[len1], W-
w[len1]),
maxValue(l1, w1, p1, L-l[len1], w[len1]) + maxValue(l1, w1, p1, L, W-
w[len1]));

return Math.max(opt1, opt2);
}
avatar
S*w
46 楼
第一题python解法：
def getK(numList, b):
numList.sort()
print numList
sumNumList = sum(numList)
if (sumNumList<=b):
print "Does not exist such K!"
return -1
currentSum = 0
n = len(numList)
for m in range(0, n):
if (b-currentSum)>0 and (b-currentSum)%(n-m)==0:
K = (b-currentSum )//(n-m)
if K < numList[m]:
return K
currentSum += numList[m]
print "Does not exist such K!"
return -1
def main():
numList = [1,2,5,7,7,8]
b = 26
print getK(numList, b)
numList = [4,6,87,93,46,8]
b = 164
print getK(numList, b)


if __name__ == '__main__':
main()
avatar
j*s
47 楼
刚面完的，两道题。
（1）给一个unsigned int数组，size为n，数组的sum = a，计算一个k的值，将数组中
所有大于k的数改为k之后，数组的sum变为b。Ex, [1,2,5,7,7,8] = a = 30, b = 26,
那么k = 6，因为[1,2,5,6,6,6] = 26。
要求时间复杂度是n*logn.
(2)给一张L*W的纸，给一堆 l(i)* w(i)的模板，每个size的模板有各自的price p(i)
，求这张纸所能剪出的最大值。
应该是挂了，我一面阿三就发怵，光弄清楚他的问题描述就得每道题5分钟。
第一题思路：
for example:
[4,6,87,93,46,8] = 244
50 = k
target [4,6,50,50,46,8] = 164
after sort [4,6,8,46,87,93]
4 * 6 = 24
[2,4,42,83,89]
2 * 5 = 10 + 24 = 34
[2,40,81,87]
2 * 4 = 8 + 34 = 42
[38,79,85]
38 * 3 = 114 + 42 = 156
[41, 47]
we don't keep going because 156 + 41 > 164
there are 2 numbers left in the array.
so, 164 - 156 = 8
46 + 8/2 = 50, this is the k we want
第二题思路：
DP。
状态转移方程：
value[i][j] = max{
max{value[k][j] + value[i-k][j]},
max{value[i][m] + value[i][j - m]}
}
0< k < i, 0< m < j
avatar
c*m
48 楼
我觉得这家的面试题真不容易啊，比google的都难啊
avatar
j*s
49 楼
嗯，我也这么觉得

【在 c*********m 的大作中提到】
: 我觉得这家的面试题真不容易啊，比google的都难啊
avatar
c*m
50 楼
你这两题程序写得如何啊？感觉30分钟时间不够，写不完啊。。

【在 j*****s 的大作中提到】
: 嗯，我也这么觉得
avatar
f*e
51 楼
第二题应该是NP吧？可以剪成小块再粘起来吗？想微积分那样的。

26,

【在 j*****s 的大作中提到】
: 刚面完的，两道题。
: （1）给一个unsigned int数组，size为n，数组的sum = a，计算一个k的值，将数组中
: 所有大于k的数改为k之后，数组的sum变为b。Ex, [1,2,5,7,7,8] = a = 30, b = 26,
: 那么k = 6，因为[1,2,5,6,6,6] = 26。
: 要求时间复杂度是n*logn.
: (2)给一张L*W的纸，给一堆 l(i)* w(i)的模板，每个size的模板有各自的price p(i)
: ，求这张纸所能剪出的最大值。
: 应该是挂了，我一面阿三就发怵，光弄清楚他的问题描述就得每道题5分钟。
: 第一题思路：
: for example:
avatar
G*A
52 楼
这两道题onsite肯定拿不下来啊
1. 算是binary search的一个应用。2分法找pivot，对于每个pivot计算相应的
expected k. 如果expected k和当前pivot的位置吻合(i.e., k >= A[pivot] && k <=
A[pivot + 1])，则返回k
2. 他应该不是想求最优解吧？！能不能给个heuristic？ 排序 p(i) / (l(i) * w(i))
,然后顺序选取。

26,

【在 j*****s 的大作中提到】
: 刚面完的，两道题。
: （1）给一个unsigned int数组，size为n，数组的sum = a，计算一个k的值，将数组中
: 所有大于k的数改为k之后，数组的sum变为b。Ex, [1,2,5,7,7,8] = a = 30, b = 26,
: 那么k = 6，因为[1,2,5,6,6,6] = 26。
: 要求时间复杂度是n*logn.
: (2)给一张L*W的纸，给一堆 l(i)* w(i)的模板，每个size的模板有各自的price p(i)
: ，求这张纸所能剪出的最大值。
: 应该是挂了，我一面阿三就发怵，光弄清楚他的问题描述就得每道题5分钟。
: 第一题思路：
: for example:
avatar
k*2
53 楼
第一题能否展开说说？我觉得毫无思路啊。。

=
))

【在 G****A 的大作中提到】
: 这两道题onsite肯定拿不下来啊
: 1. 算是binary search的一个应用。2分法找pivot，对于每个pivot计算相应的
: expected k. 如果expected k和当前pivot的位置吻合(i.e., k >= A[pivot] && k <=
: A[pivot + 1])，则返回k
: 2. 他应该不是想求最优解吧？！能不能给个heuristic？ 排序 p(i) / (l(i) * w(i))
: ,然后顺序选取。
:
: 26,
avatar
a*a
54 楼
这个解法如何，是nlogn 的吧。
第一题
const int b=26;
const int a[6]={1,2,5,7,7,8};
int l=a[0],m=a[5],k,sum=0;
while(l{
k=(l+m)/2;
sum=0;
for(int i=0;i<6;i++)
{
if(a[i]else sum+=k;
}
if(sum>b)
{
m=k;
}
else if (sum{
l=k;
}
else
return k;

}
avatar
e*s
55 楼
请问第一题就是 0 ～ max 之间 二叉查找吗？
avatar
e*s
56 楼
b = 0 怎么办？

【在 a******a 的大作中提到】
: 这个解法如何，是nlogn 的吧。
: 第一题
: const int b=26;
: const int a[6]={1,2,5,7,7,8};
: int l=a[0],m=a[5],k,sum=0;
: while(l: {
: k=(l+m)/2;
: sum=0;
: for(int i=0;i<6;i++)
avatar
a*a
57 楼
不懂

【在 e***s 的大作中提到】
: b = 0 怎么办？
avatar
j*s
58 楼
这个解法我面试的时候说了，但他说不是n*lgn的，你看，你这个依赖于数组中最大和
最小的值，所以，实际上是Lg(max(a)) * n

【在 a******a 的大作中提到】
: 这个解法如何，是nlogn 的吧。
: 第一题
: const int b=26;
: const int a[6]={1,2,5,7,7,8};
: int l=a[0],m=a[5],k,sum=0;
: while(l: {
: k=(l+m)/2;
: sum=0;
: for(int i=0;i<6;i++)
avatar
r*h
59 楼
第一题排序之后从后往前扫应该可以
第二题好难
这题目是电面？30分钟写两题bug free也太牛了

26,

【在 j*****s 的大作中提到】
: 刚面完的，两道题。
: （1）给一个unsigned int数组，size为n，数组的sum = a，计算一个k的值，将数组中
: 所有大于k的数改为k之后，数组的sum变为b。Ex, [1,2,5,7,7,8] = a = 30, b = 26,
: 那么k = 6，因为[1,2,5,6,6,6] = 26。
: 要求时间复杂度是n*logn.
: (2)给一张L*W的纸，给一堆 l(i)* w(i)的模板，每个size的模板有各自的price p(i)
: ，求这张纸所能剪出的最大值。
: 应该是挂了，我一面阿三就发怵，光弄清楚他的问题描述就得每道题5分钟。
: 第一题思路：
: for example:
avatar
j*s
60 楼
是的，是NP，但是不能粘起来。

【在 f*****e 的大作中提到】
: 第二题应该是NP吧？可以剪成小块再粘起来吗？想微积分那样的。
:
: 26,
avatar
j*s
61 楼
第一题，你说扫，怎么扫？假设数组是a[1,2,3,4,5,6,999999],你是从a[6]往a[0]扫，
还是9999999往1扫？但是不管怎样，两种方法都达不到要求。
我面了45分钟吧，第二题只给出了DP的方程，没来得及写代码。那个阿三好烦，在我想
问题的时候也一直在那边打字，搞得我想不进去。

【在 r**h 的大作中提到】
: 第一题排序之后从后往前扫应该可以
: 第二题好难
: 这题目是电面？30分钟写两题bug free也太牛了
:
: 26,
avatar
c*9
62 楼
第一题先sort，然后从前往后扫，直到遇到target - current_sum 除以剩余数的个数
等于某个整数，并且这个整数大于等于当前数并且小于等于下一个数字，返回这个整数
，可以么？
avatar
r*h
63 楼
楼上的方法更简单，还是用那个吧
求第二题解法
第一题本来就不能保证有解吧
你的例子里面b=25怎么办
我想到的解法是，从最后一个元素往数组开头扫，每次找到一个a[i]使得a[i-1]，以及这些元素可以减少到的最小值（也就是a[i-1]）。然后判断将当前所有元素在规
定范围内减小值能否达到要求
比如说你的例子
1,2,5,7,7,8
第一次找到8，总共有n=1个元素，最少可以减少到7，此时a=29>b，继续
第二次找到7，总共n=3个元素，最少可以减少到5、不过减少到5的时候a=23于(b-a)/n = 1，(b-a)%n=0，因此将这三个元素都减少到6即可
时间复杂度O(n log n)也就是排序的时间

【在 j*****s 的大作中提到】
: 第一题，你说扫，怎么扫？假设数组是a[1,2,3,4,5,6,999999],你是从a[6]往a[0]扫，
: 还是9999999往1扫？但是不管怎样，两种方法都达不到要求。
: 我面了45分钟吧，第二题只给出了DP的方程，没来得及写代码。那个阿三好烦，在我想
: 问题的时候也一直在那边打字，搞得我想不进去。
avatar
j*s
64 楼
没太明白你的意思，举个例子？

【在 c****9 的大作中提到】
: 第一题先sort，然后从前往后扫，直到遇到target - current_sum 除以剩余数的个数
: 等于某个整数，并且这个整数大于等于当前数并且小于等于下一个数字，返回这个整数
: ，可以么？
avatar
c*9
65 楼
我也不确定有没有bug
125778
1 (26-1)/5 = 5 大于1 但不小于2 不符合
2 (26-3)/4 非整数
5 (26-8)/3 = 6 大于5 小于等于6 符合 return

【在 j*****s 的大作中提到】
: 没太明白你的意思，举个例子？
avatar
s*r
66 楼
第一题不要这么复杂吧
不考虑溢出
1.先排序 nlog(n)
2.
int sum = a[0];
for (i=1;iif((b-sum)%(n-i-1)==0){
int tmp = (b-sum)/(n-i-1);
if(tmp>=a[i-1]&&tmpreturn tmp;
}
sum+=a[i];
}
return NOT_FIND;

=
))

【在 G****A 的大作中提到】
: 这两道题onsite肯定拿不下来啊
: 1. 算是binary search的一个应用。2分法找pivot，对于每个pivot计算相应的
: expected k. 如果expected k和当前pivot的位置吻合(i.e., k >= A[pivot] && k <=
: A[pivot + 1])，则返回k
: 2. 他应该不是想求最优解吧？！能不能给个heuristic？ 排序 p(i) / (l(i) * w(i))
: ,然后顺序选取。
:
: 26,
avatar
r*h
67 楼
有一个小bug
每次扫描的时候要一次减掉所有连续且有相同值的元素
因为值相同的元素，要么不改变值，要么全改

【在 c****9 的大作中提到】
: 我也不确定有没有bug
: 125778
: 1 (26-1)/5 = 5 大于1 但不小于2 不符合
: 2 (26-3)/4 非整数
: 5 (26-8)/3 = 6 大于5 小于等于6 符合 return
avatar
c*9
68 楼
因为会小于等于下一个元素和大于等于当前元素，似乎不会存在没有减掉所有连续相同
元素的情况。

【在 r**h 的大作中提到】
: 有一个小bug
: 每次扫描的时候要一次减掉所有连续且有相同值的元素
: 因为值相同的元素，要么不改变值，要么全改
avatar
r*h
69 楼
哦，对的
我考虑复杂了

【在 c****9 的大作中提到】
: 因为会小于等于下一个元素和大于等于当前元素，似乎不会存在没有减掉所有连续相同
: 元素的情况。
avatar
h*o
70 楼
嗯，一样的想法。
应该就这样吧。

【在 s*******r 的大作中提到】
: 第一题不要这么复杂吧
: 不考虑溢出
: 1.先排序 nlog(n)
: 2.
: int sum = a[0];
: for (i=1;i: if((b-sum)%(n-i-1)==0){
: int tmp = (b-sum)/(n-i-1);
: if(tmp>=a[i-1]&&tmp: return tmp;
avatar
u*g
71 楼
第二题是个NP。。跟二维背包不一样。。。
avatar
s*s
72 楼
这个方法好！

【在 c****9 的大作中提到】
: 第一题先sort，然后从前往后扫，直到遇到target - current_sum 除以剩余数的个数
: 等于某个整数，并且这个整数大于等于当前数并且小于等于下一个数字，返回这个整数
: ，可以么？
avatar
b*7
73 楼
在[0,n-1]间查找，再减去多余的部分
int adjust(int A[],int n, int b)
{
if(n <= 0 || b < 0) return -1;
sort(A,A+n);
int index = -1;
int cursum = -1;
int low = 0, high = n-1;
while(low <= high)
{
int mid = low + (high - low)/2;
int sum = 0;
for(int i = 0; i < n; i++)
{
sum += min(A[i],A[mid]);
}
if(sum == b) return A[mid];
else if(sum > b)
{
index = mid;
cursum = sum;
high = mid - 1;
}
else
{
low = mid + 1;
}
}//while
if(index == -1) return b % n == 0 ? b/n : -1;
if((cursum - b)%(n-index) != 0) return -1;
return A[index] - (cursum -b)/(n-index);
}
[0,maxvalue]之间二分查找
int adjust(int A[], int n, int b)
{
if(n <= 0 || b < 0) return -1;
int low = 0;
int high = *max_element(A,A+n);
while(low <= high)
{
int mid = low + (high - low)/2;
int sum = 0;
for(int i = 0; i < n; i++)
{
if(A[i] > mid) sum += mid;
else sum += A[i];
}
if(sum == b) return mid;
else if(sum < b)
low = mid + 1;
else
high = mid - 1;
}
return -1;
}
avatar
t*3
74 楼
第二题的思路好像有问题。 比如L*W的纸，正好能被一张模版填满。 这种情况下你就
不能把纸分成两块，每块求最大。

26,

【在 j*****s 的大作中提到】
: 刚面完的，两道题。
: （1）给一个unsigned int数组，size为n，数组的sum = a，计算一个k的值，将数组中
: 所有大于k的数改为k之后，数组的sum变为b。Ex, [1,2,5,7,7,8] = a = 30, b = 26,
: 那么k = 6，因为[1,2,5,6,6,6] = 26。
: 要求时间复杂度是n*logn.
: (2)给一张L*W的纸，给一堆 l(i)* w(i)的模板，每个size的模板有各自的price p(i)
: ，求这张纸所能剪出的最大值。
: 应该是挂了，我一面阿三就发怵，光弄清楚他的问题描述就得每道题5分钟。
: 第一题思路：
: for example:
avatar
t*3
75 楼
第二题，如果是这种情况怎么办？

26,

【在 j*****s 的大作中提到】
: 刚面完的，两道题。
: （1）给一个unsigned int数组，size为n，数组的sum = a，计算一个k的值，将数组中
: 所有大于k的数改为k之后，数组的sum变为b。Ex, [1,2,5,7,7,8] = a = 30, b = 26,
: 那么k = 6，因为[1,2,5,6,6,6] = 26。
: 要求时间复杂度是n*logn.
: (2)给一张L*W的纸，给一堆 l(i)* w(i)的模板，每个size的模板有各自的price p(i)
: ，求这张纸所能剪出的最大值。
: 应该是挂了，我一面阿三就发怵，光弄清楚他的问题描述就得每道题5分钟。
: 第一题思路：
: for example:
avatar
f*m
76 楼
谁能给个第二题的解？
要是一维就好办了
avatar
f*m
77 楼
这题好像是Introduction to algorithms DP那章的课后题
avatar
Y*f
78 楼
这个阿三也太狠了吧，第二题就是二维的背包问题吧。

26,

【在 j*****s 的大作中提到】
: 刚面完的，两道题。
: （1）给一个unsigned int数组，size为n，数组的sum = a，计算一个k的值，将数组中
: 所有大于k的数改为k之后，数组的sum变为b。Ex, [1,2,5,7,7,8] = a = 30, b = 26,
: 那么k = 6，因为[1,2,5,6,6,6] = 26。
: 要求时间复杂度是n*logn.
: (2)给一张L*W的纸，给一堆 l(i)* w(i)的模板，每个size的模板有各自的price p(i)
: ，求这张纸所能剪出的最大值。
: 应该是挂了，我一面阿三就发怵，光弄清楚他的问题描述就得每道题5分钟。
: 第一题思路：
: for example:
avatar
s*r
79 楼
为什么石油公司也考算法？
也要写代码？
avatar
r*e
80 楼
晕，这个rocket fuel是个热门的big data startup，做ads的

【在 s**********r 的大作中提到】
: 为什么石油公司也考算法？
: 也要写代码？
avatar
s*r
81 楼
我2了。。

【在 r*******e 的大作中提到】
: 晕，这个rocket fuel是个热门的big data startup，做ads的
avatar
s*r
82 楼
big data考你machine learning了么？
avatar
x*0
83 楼
mark
avatar
f*m
84 楼
谁能给个第二题的解法？这题和二位背包类似，但是更复杂。
avatar
y*c
85 楼
mark
avatar
e*8
86 楼
rocket fuel第二题可以用linear programming解不？
avatar
H*S
87 楼
一遍排序加一遍顺序遍历
public int solution(int[] array, int b) {
Arrays.sort(array);
int sum = 0;
int n = array.length;
for (int i = 0; i < n; i++) {
if ((b - sum) % (n - i) == 0) {
int m = (b - sum) / (n - i);
if (i == 0 && m >= array[i]) return m;
else if (m >= array[i - 1] && m < array[i]) return m;
}
sum += array[i];
}
return -1;
}
avatar
v*n
88 楼
mark nn【在 houqingniao (候情鸟)的大作中提到：】n：嗯，一样的想法。n：应该就
这样吧。n：【 在 sunfaquir (非礼勿言) 的大作中提到: 】n：: 第一题不要这么复
杂吧n：: 不考虑溢出n：: 1.先排序 nlog(n)n：: 2.n……nn--n[发自未名空间
Android客户端]
avatar
l*s
89 楼
public static int changeArray(int[] n, int a, int b) {
int len = n.length;
Arrays.sort(n);
int sumSoFar = 0;
int test = 0;
int diff = a-b;
boolean done = false;
for (int i = len-1; i>=0; i--) {
sumSoFar += n[i];
test = (sumSoFar - diff) / (len - i);
if (test > n[i-1] && test <= n[i]) {
done = true;
break;
}
}
if (done)
return test;
return Integer.MIN_VALUE;
}
avatar
l*s
90 楼
2nd question
public static int maxValue(int[] l, int[] w, int[] p, int L, int W) {
assert(l.length == w.length && l.length == p.length);
if (l.length == 0) return Integer.MIN_VALUE;
return maxValueRecur(l, w, p, L, W, 0);
}
public static int maxValueRecur(int[] l, int[] w, int[] p, int L, int W,
int value) {
int len = l.length;
assert(l.length == w.length && l.length == p.length);
if (len == 1) {
if (l[0] > L || w[0] > W)
return value;

return value + p[0];
}
int len1 = len-1;
int[] l1 = Arrays.copyOf(l, len1);
int[] w1 = Arrays.copyOf(w, len1);
int[] p1 = Arrays.copyOf(p, len1);
int opt1 = maxValueRecur(l1, w1, p1, L, W, value); // not using
i
if (l[len1] > L || w[len1] > W) {
return opt1;
}
int opt2 = value + p[len-1] +
Math.max(
maxValue(l1, w1, p1, L-l[len1], W) + maxValue(l1, w1, p1, l[len1], W-
w[len1]),
maxValue(l1, w1, p1, L-l[len1], w[len1]) + maxValue(l1, w1, p1, L, W-
w[len1]));

return Math.max(opt1, opt2);
}
avatar
k*o
91 楼
mark
avatar
c*0
92 楼
这两题版上都有讨论啊

26,

【在 j*****s 的大作中提到】
: 刚面完的，两道题。
: （1）给一个unsigned int数组，size为n，数组的sum = a，计算一个k的值，将数组中
: 所有大于k的数改为k之后，数组的sum变为b。Ex, [1,2,5,7,7,8] = a = 30, b = 26,
: 那么k = 6，因为[1,2,5,6,6,6] = 26。
: 要求时间复杂度是n*logn.
: (2)给一张L*W的纸，给一堆 l(i)* w(i)的模板，每个size的模板有各自的price p(i)
: ，求这张纸所能剪出的最大值。
: 应该是挂了，我一面阿三就发怵，光弄清楚他的问题描述就得每道题5分钟。
: 第一题思路：
: for example:
相关阅读
夏天啦！FB长期内推+面试准备(NY地区为主)g家股票每年refresh大概多少HireTeamMate上面refer可以拿钱是不是真的？OPT八月底结束，H1B十月一号生效，7月份可以离开美国吗？我可以有自己的路么？要不要开始找工作了？ (转载)Quality Assurance Engineer前途 (转载)有了解juniper的么？帮看下offer烙印至少到senior manager 或vp以上才开始互掐看了jobhunting， 现在年轻人不得了。 (转载)请推荐一个支持多用户的无线备份硬盘，谢谢！开贴说说SDET/STE/QA的区别和工资Uber 电面面经举例给NYT说烙印占领的技术公司 (转载)生物专业，通过EB1A拿到绿卡，以后能转cs吗？ 因为cs和生物不同领域，绿卡会取消掉吗？How to Start the Career as Data Scientist硅谷大数据公司估值第一的Palantir招人啦求个Uber内推非码工职位ADP跟Zenefits掐起来了大学生出来找不到工作，读书有用？
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章，不代表同意其说法或描述，仅为提供更多信息，也不构成任何建议。文章信息的合法性及真实性由其作者负责，与Redian.news及其运营公司无关。欢迎投稿，如发现稿件侵权，或作者不愿在本网发表文章，请版权拥有者通知本网处理。