发个刚面完的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
(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