j******s
发帖数: 48 | 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要求还是很高的，求高效的算法。 |
c*****a
发帖数: 808 | 2 第一题好像可以用dfs测试每个interger + - * / 的combination，不过好像是n! |
r*******e
发帖数: 7583 | 3 sign operation 应该只有正负号两种，2^n 吧
【在 c*****a 的大作中提到】
: 第一题好像可以用dfs测试每个interger + - * / 的combination，不过好像是n!
|
c*********r
发帖数: 77 | 4 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
|
z*******g
发帖数: 18 | 5 第二题的话特别像那道人站人上，然后看最多站多高的题目。
方法也差不多，从第一个开始，然后把第一个不符合条件的标上记号，
继续一直到最后得到一个最大的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
|
y**k
发帖数: 222 | 6 第一题是partition problem, NP hard. 有近似算法 |
a****s
发帖数: 559 | 7 第一题很简单，先从大到小排序，然后一个一个拿出来，分别放进两组，原则是哪组的
sum小，拿出来的就放进哪组。全放完后，sum大的组，其所有数给正号；sum小的组，
其所有数给负号。 |
a****s
发帖数: 559 | 8 第二题更简单。检查每一个pair的a_i，并求sum+＝w_i。如果a_i+1
如果sum大于sum_max，那么sum_max＝sum；否则，丢弃sum。然后sum清零，从a_i+1开
始继续检查。 |
e*******i
发帖数: 56 | 9
大侠，那第一题这麽结果是1
【在 a****s 的大作中提到】
: 第一题很简单，先从大到小排序，然后一个一个拿出来，分别放进两组，原则是哪组的
: sum小，拿出来的就放进哪组。全放完后，sum大的组，其所有数给正号；sum小的组，
: 其所有数给负号。
|
s******e
发帖数: 493 | 10 Find a match or the closet bigger number of sum/2 |
|
|
s******e
发帖数: 493 | 11 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*******w
发帖数: 687 | 12 第一题可以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****r
发帖数: 2801 | 13 有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*****i
发帖数: 3587 | 14 PG发来的Online test连做的勇气都没的人路过，一看见interview street就特么跪了 |
c***l
发帖数: 8 | 15 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****r
发帖数: 2801 | 16 现在面试题都到这难度了？
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**u
发帖数: 2458 | |
x*********w
发帖数: 533 | 18 这种公司还没见有人报过offer吧，
什么pocket gem, 啥storm8的 |
x*********w
发帖数: 533 | 19 第一题有伪DP解法，不是很容易看出来啊
第二题和increasing sub sequence 差不多 |
G****A
发帖数: 4160 | 20 除非对这类题很熟，一小时做完有挑战。
第一道题可以上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******7
发帖数: 30 | 21 和我做的一模一样，两题都是DP，写完了过了前两个test case，隐藏test case挂掉，
估计I/O exception没处理好，没时间改，直接被拒。。 |
l*****e
发帖数: 3 | 22 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**u
发帖数: 2458 | 23 第1题咋做
完全没思路
【在 x*********w 的大作中提到】
: 第一题有伪DP解法，不是很容易看出来啊
: 第二题和increasing sub sequence 差不多
|
c*******3
发帖数: 28 | 24 这公司最近才加了做题环节 今年年初还直接面试呢 而且做的题极其难 不知道这公司
抽了什么风
一个小时时间，，一道也没做出来。。悲催。。第一题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*******3
发帖数: 28 | 25 握手 一模一样 现在这些小破公司都把test往死里难
和我做的一模一样，两题都是DP，写完了过了前两个test case，隐藏test case挂掉，
估计I/O exception没处理好，没时间改，直接被拒。。
【在 M******7 的大作中提到】
: 和我做的一模一样，两题都是DP，写完了过了前两个test case，隐藏test case挂掉，
: 估计I/O exception没处理好，没时间改，直接被拒。。
|
A**u
发帖数: 2458 | 26 lol
storm8好像也是，以前蛮简单，现在好难
you
【在 c*******3 的大作中提到】
: 这公司最近才加了做题环节 今年年初还直接面试呢 而且做的题极其难 不知道这公司
: 抽了什么风
:
: 一个小时时间，，一道也没做出来。。悲催。。第一题Given a set of integer, you
: could apply sign operation to the in........
|
x*********w
发帖数: 533 | |
c*******3
发帖数: 28 | 28 嗯 可不 一对小公司现在都走这个路线 test出难点是能抬高身价还是怎么的？我怀疑
这些公司现在压根不招人 只是维持招人的假象以显示自己还在发展 其实说不定已经是
半死不活的了 没啥技术含量的小破公司
【在 A**u 的大作中提到】
: lol
: storm8好像也是，以前蛮简单，现在好难
:
: you
|
A**u
发帖数: 2458 | |
x*********w
发帖数: 533 | 30 第一题：
这里假设都是正数并且打印了需要变为负数的数字
/*
* 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****a
发帖数: 1212 | 31 第一题 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****a
发帖数: 1212 | 32 第二题
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**u
发帖数: 2458 | |
