角度很重要 - 未名空间MITBBS历史存档

j*s2013-01-13 08:01

1 楼

一个小时时间，，一道也没做出来。。悲催。。
第一题
Given a set of integer, you could apply sign operation to the integer, find
the minimum sum that is close to but no less than 0;
eg.
input 3 5 7 11 13
output 1
第二题
given a set of pairs
find a set of pairs from the above set, so that a_j1, and w_j1+w_j2+w_j3.. is the max.
order should be maintained.
eg.
input <1,3> <2,2> <3,1>
output 6
input <3,3> <2,2> <1,1>
output 3
updated..
第一题2^n recursion 算法我做出来了，不过超时了。求dp的方法。
第二题。。估计是用recursion..最后没写出来，所以也不知道能不能过。
btw. pg要求还是很高的，求高效的算法。

p*g2013-01-13 08:01

2 楼

c*a2013-01-13 08:01

3 楼

第一题好像可以用dfs测试每个interger + - * / 的combination，不过好像是n!

a*e2013-01-13 08:01

4 楼

看到斑马照，笑了

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

r*e2013-01-13 08:01

5 楼

sign operation 应该只有正负号两种，2^n 吧

【在 c*****a 的大作中提到】

: 第一题好像可以用dfs测试每个interger + - * / 的combination，不过好像是n!

S*e2013-01-13 08:01

6 楼

猛赞

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

c*r2013-01-13 08:01

7 楼

first question:
For the initial solution, can use recursive to do it.
Because there are a lot of duplicated sums, we should use dynamic
programming to optimize it.

find
..

【在 j******s 的大作中提到】

: 一个小时时间，，一道也没做出来。。悲催。。
: 第一题
: Given a set of integer, you could apply sign operation to the integer, find
: the minimum sum that is close to but no less than 0;
: eg.
: input 3 5 7 11 13
: output 1
: 第二题
: given a set of pairs
: find a set of pairs from the above set, so that a_j1

r*e2013-01-13 08:01

8 楼

百看不厌

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

z*g2013-01-13 08:01

9 楼

第二题的话特别像那道人站人上，然后看最多站多高的题目。
方法也差不多，从第一个开始，然后把第一个不符合条件的标上记号，
继续一直到最后得到一个最大的sum，然后再从那个标了记号的开始。
用recursion可以做。

find
..

【在 j******s 的大作中提到】

: 一个小时时间，，一道也没做出来。。悲催。。
: 第一题
: Given a set of integer, you could apply sign operation to the integer, find
: the minimum sum that is close to but no less than 0;
: eg.
: input 3 5 7 11 13
: output 1
: 第二题
: given a set of pairs
: find a set of pairs from the above set, so that a_j1

a*r2013-01-13 08:01

10 楼

5有两个亮点，怎么凑上去的。

y*k2013-01-13 08:01

11 楼

第一题是partition problem, NP hard. 有近似算法

a*s2013-01-13 08:01

12 楼

第一题很简单，先从大到小排序，然后一个一个拿出来，分别放进两组，原则是哪组的
sum小，拿出来的就放进哪组。全放完后，sum大的组，其所有数给正号；sum小的组，
其所有数给负号。

a*s2013-01-13 08:01

13 楼

第二题更简单。检查每一个pair的a_i，并求sum+＝w_i。如果a_i+1如果sum大于sum_max，那么sum_max＝sum；否则，丢弃sum。然后sum清零，从a_i+1开
始继续检查。

e*i2013-01-13 08:01

14 楼

大侠，那第一题这麽结果是1

【在 a****s 的大作中提到】

: 第一题很简单，先从大到小排序，然后一个一个拿出来，分别放进两组，原则是哪组的
: sum小，拿出来的就放进哪组。全放完后，sum大的组，其所有数给正号；sum小的组，
: 其所有数给负号。

s*e2013-01-13 08:01

15 楼

Find a match or the closet bigger number of sum/2

s*e2013-01-13 08:01

16 楼

If the set doesn'tneed to be continuous, do to max on include next one or
not. If it must be continuous, scan from left to right

n*w2013-01-13 08:01

17 楼

第一题可以DP
其实本质上是把set分成两部分使得两部分的差的绝对值最接近0
google MIT balanced partition
第二题是longest increasing sequence的变形
先假设w_j全为非负数
假设L[j]表示ending position在 j 的时候找到的longest increasing sequence
DP[j]表示L[j]这个sequence里边所有元素对应的w之和。
递归式为
DP[j] = max {DP[i]} + w_j
i = [0, j-1] && A[i]返回结果 max { DP[j] } where j = [0, n-1]
如果所有w_j都等于1，那原题退化成求longest increasing sequence，因为递归式一
模一样。复杂度都是n^2
如果w_j可能为负数，那么上面的递归式里边的w_j 改成 max(0, w_j)

find
..

【在 j******s 的大作中提到】

: 一个小时时间，，一道也没做出来。。悲催。。
: 第一题
: Given a set of integer, you could apply sign operation to the integer, find
: the minimum sum that is close to but no less than 0;
: eg.
: input 3 5 7 11 13
: output 1
: 第二题
: given a set of pairs
: find a set of pairs from the above set, so that a_j1

H*r2013-01-13 08:01

18 楼

有online judge么？

find
..

【在 j******s 的大作中提到】

: 一个小时时间，，一道也没做出来。。悲催。。
: 第一题
: Given a set of integer, you could apply sign operation to the integer, find
: the minimum sum that is close to but no less than 0;
: eg.
: input 3 5 7 11 13
: output 1
: 第二题
: given a set of pairs
: find a set of pairs from the above set, so that a_j1

A*i2013-01-13 08:01

19 楼

PG发来的Online test连做的勇气都没的人路过，一看见interview street就特么跪了

c*l2013-01-13 08:01

20 楼

A DP algorithm based on the balance partition algorithm (can google find the
algorithm) for the first question.
大牛看看有什么问题.
#include
#include
#include
using namespace std;
extern int mindiff(int i, int A[]);
int main()
{
int A[5]={3, 5, 7, 11, 13};
int min;
min=mindiff(5,A);
cout<}
int mindiff(int n, int A[])
{
int i, j;
int max=0;
int jmin;
int result;
double min;
double sum=0;
for(i=0;i<=n-1;i++) { sum+=A[i]; if(A[i]>max) max=A[i]; }
sum=sum/2;
min=sum;
int pij[n+1][n*max+1];
for(i=0;i<=n;i++)
for(j=0;j<=n*max;j++) pij[i][j]=0;
for(i=1;i<=n;i++) pij[i][A[i-1]]=1;
for(i=2;i<=n;i++)
for(j=0;j<=n*max;j++)
if(pij[i-1][j]==1 || (j-A[i-1]>=0 && pij[i-1][j-A[i-1]]==1)) pij[i][j]=1;
for(i=1;i<=n;i++)
for(j=0;j<=n*max;j++)
if(pij[i][j]==1) {
if(fabs(sum-j)result=sum*2-2*jmin;
if(result>0) return result;
else return -result;
}

find
..

【在 j******s 的大作中提到】

: 一个小时时间，，一道也没做出来。。悲催。。
: 第一题
: Given a set of integer, you could apply sign operation to the integer, find
: the minimum sum that is close to but no less than 0;
: eg.
: input 3 5 7 11 13
: output 1
: 第二题
: given a set of pairs
: find a set of pairs from the above set, so that a_j1

H*r2013-01-13 08:01

21 楼

现在面试题都到这难度了？
1） 01背包（伪多项式服擦度）
2）dp + bst + augment data? （O(N*logN))
等大牛来讲讲标准解

find
..
★ 发自iPhone App: ChineseWeb 7.8

【在 j******s 的大作中提到】

: 一个小时时间，，一道也没做出来。。悲催。。
: 第一题
: Given a set of integer, you could apply sign operation to the integer, find
: the minimum sum that is close to but no less than 0;
: eg.
: input 3 5 7 11 13
: output 1
: 第二题
: given a set of pairs
: find a set of pairs from the above set, so that a_j1

A*u2013-01-13 08:01

22 楼

真难

x*w2013-01-13 08:01

23 楼

这种公司还没见有人报过offer吧，
什么pocket gem, 啥storm8的

x*w2013-01-13 08:01

24 楼

第一题有伪DP解法，不是很容易看出来啊
第二题和increasing sub sequence 差不多

G*A2013-01-13 08:01

25 楼

除非对这类题很熟，一小时做完有挑战。
第一道题可以上dp,但复杂度貌似还是exponential。

find
..

【在 j******s 的大作中提到】

: 一个小时时间，，一道也没做出来。。悲催。。
: 第一题
: Given a set of integer, you could apply sign operation to the integer, find
: the minimum sum that is close to but no less than 0;
: eg.
: input 3 5 7 11 13
: output 1
: 第二题
: given a set of pairs
: find a set of pairs from the above set, so that a_j1

M*72013-01-13 08:01

26 楼

和我做的一模一样，两题都是DP，写完了过了前两个test case，隐藏test case挂掉，
估计I/O exception没处理好，没时间改，直接被拒。。

l*e2013-01-13 08:01

27 楼

Code for 1:
public static int getMinDiff(int[] values) {
int sum = 0;

for (int i = 0; i < values.length; ++i) {
sum+=values[i];
}

int target = sum / 2 + 1;
int len = values.length;
boolean[][] table = new boolean[len][target];

table[0][0] = true;
int largest = 0;

for (int i = 1; i < len; i++)
for (int j = 0; j < target; j++)
if (table[i-1][j] == true || (j - values[i-1] >= 0 &&
table[i-1][j-values[i-1]] == true )) {
table[i][j] = true;
largest = j;
}

return (largest > sum - largest) ? 2 * largest -sum : sum - 2 * largest;
}

A*u2013-01-13 08:01

28 楼

第1题咋做
完全没思路

【在 x*********w 的大作中提到】

: 第一题有伪DP解法，不是很容易看出来啊
: 第二题和increasing sub sequence 差不多

c*32013-01-13 08:01

29 楼

这公司最近才加了做题环节今年年初还直接面试呢而且做的题极其难不知道这公司
抽了什么风

一个小时时间，，一道也没做出来。。悲催。。第一题Given a set of integer, you
could apply sign operation to the in........

【在 j******s 的大作中提到】

: 一个小时时间，，一道也没做出来。。悲催。。
: 第一题
: Given a set of integer, you could apply sign operation to the integer, find
: the minimum sum that is close to but no less than 0;
: eg.
: input 3 5 7 11 13
: output 1
: 第二题
: given a set of pairs
: find a set of pairs from the above set, so that a_j1

c*32013-01-13 08:01

30 楼

握手一模一样现在这些小破公司都把test往死里难

和我做的一模一样，两题都是DP，写完了过了前两个test case，隐藏test case挂掉，
估计I/O exception没处理好，没时间改，直接被拒。。

【在 M******7 的大作中提到】

: 和我做的一模一样，两题都是DP，写完了过了前两个test case，隐藏test case挂掉，
: 估计I/O exception没处理好，没时间改，直接被拒。。

A*u2013-01-13 08:01

31 楼

lol
storm8好像也是，以前蛮简单，现在好难

you

【在 c*******3 的大作中提到】

: 这公司最近才加了做题环节今年年初还直接面试呢而且做的题极其难不知道这公司
: 抽了什么风
:
: 一个小时时间，，一道也没做出来。。悲催。。第一题Given a set of integer, you
: could apply sign operation to the in........

x*w2013-01-13 08:01

32 楼

参考
http://en.wikipedia.org/wiki/Subset_sum_problem

【在 A**u 的大作中提到】

: 第1题咋做
: 完全没思路

c*32013-01-13 08:01

33 楼

嗯可不一对小公司现在都走这个路线 test出难点是能抬高身价还是怎么的？我怀疑
这些公司现在压根不招人只是维持招人的假象以显示自己还在发展其实说不定已经是
半死不活的了没啥技术含量的小破公司

【在 A**u 的大作中提到】

: lol
: storm8好像也是，以前蛮简单，现在好难
:
: you

A*u2013-01-13 08:01

34 楼

多谢明天看看

【在 x*********w 的大作中提到】

:
: 参考
: http://en.wikipedia.org/wiki/Subset_sum_problem

x*w2013-01-13 08:01

35 楼

第一题：
这里假设都是正数并且打印了需要变为负数的数字
/*
* Given a set of integer, you could apply sign operation to the integer,
find
the minimum sum that is close to but no less than 0;
eg.
input 3 5 7 11 13

output 1
* */
public class SubSetSum
{
static int getNegOnes(int a[])
{
int sum = 0;
for (int i = 0; i < a.length; i++)
sum += a[i];

int half = sum/2;
boolean[][] rec = new boolean [a.length][half+1];
for (int i = 0; i < a.length; i++)
rec[i][0] = true;
rec[0][a[0]] = true;

for (int i = 1; i < a.length; i++)
{
for (int j = 1; j <= half; j++)
{
if (rec[i-1][j] || (j - a[i] >= 0 && rec[i-1][j - a[i]]))
rec[i][j] = true;
}
}

int k = sum;
for (int i = half; i >= 0; i--)
{
if (rec[a.length-1][i])
{
k = i;
break;
}
}

int ret = sum - k - k;

for (int i = a.length-1; i > 0; i--)
{
if (k - a[i] >= 0 && rec[i-1][k - a[i]])
{
k -= a[i];
System.out.print(a[i]);
System.out.print(" ");
}
}

if (k == a[0])
{
System.out.print(a[0]);
System.out.print(" ");
}

System.out.println("");

return ret;
}

public static void main(String[] strs)
{
int a[] = { 3, 5, 7, 11, 13 };
getNegOnes(a);
}
}

t*a2013-01-13 08:01

36 楼

第一题 in haskell 逻辑很简单，结果虽然对，但相当怀疑自己做错了。
import Data.Function.Memoize
signSum :: [Int] -> Int -> Int
signSum (x:[]) z = y - z
where y = abs x
signSum (x:xs) z
| d1 < 0 && d2 < 0 = d1
| d2 < 0 = d1
| d1 < 0 = d2
| otherwise = min d1 d2
where d1 = m_signSum xs z-x
d2 = m_signSum xs z+x
m_signSum = memoize signSum
main = print $ signSum [3,5,7,11,13] 0 -- return 1

t*a2013-01-13 08:01

37 楼

第二题
import Data.Function.Memoize
orderPair0 :: [(Int, Int)] -> Int
orderPair0 s = orderPair 0 s
where orderPair :: Int -> [(Int, Int)] -> Int
orderPair _ ([]) = 0
orderPair z ((a,w):xs)
| a <= z = wsum1
| a > z = max wsum1 wsum2
where wsum1 = m_orderPair z xs
wsum2 = w + m_orderPair a xs
m_orderPair = memoize orderPair
main = putStrLn ("No 1. " ++ (show $ orderPair0 [(1,3),(2,2),(3,1)]) ++ "\n"
++
"No 2. " ++ (show $ orderPair0 [(3,3),(2,2),(1,1)]))
results:
No 1. 6
No 2. 3

A*u2013-01-13 08:01

38 楼

大牛