y****n
发帖数: 192 | 1 是现场写code的面试。
第一道是写一个函数，两个参数（String prefix, String s）, 返回true如果s有
prefix
第二道是写一个函数，两个参数（int[] a, int sum), 找出数组里加起来是sum的几个数
我第一题算是答出来了，第二题没做完，没有好的思路。。。
大人指教一下 |
j*t
发帖数: 184 | 2 >>找出数组里加起来是sum的几个数
是几个？如果是两个，已经讨论N遍了。
个数
【在 y****n 的大作中提到】
: 是现场写code的面试。
: 第一道是写一个函数，两个参数（String prefix, String s）, 返回true如果s有
: prefix
: 第二道是写一个函数，两个参数（int[] a, int sum), 找出数组里加起来是sum的几个数
: 我第一题算是答出来了，第二题没做完，没有好的思路。。。
: 大人指教一下
|
y****n
发帖数: 192 | 3 两个的话我早就搞定了。。。
呵呵
【在 j*t 的大作中提到】
: >>找出数组里加起来是sum的几个数
: 是几个？如果是两个，已经讨论N遍了。
:
: 个数
|
w******l
发帖数: 58 | 4 google knapsack problem
个数
【在 y****n 的大作中提到】
: 是现场写code的面试。
: 第一道是写一个函数，两个参数（String prefix, String s）, 返回true如果s有
: prefix
: 第二道是写一个函数，两个参数（int[] a, int sum), 找出数组里加起来是sum的几个数
: 我第一题算是答出来了，第二题没做完，没有好的思路。。。
: 大人指教一下
|
y****n
发帖数: 192 | 5 谢谢！能讲得更具体点吗？
我当时是要我把code写出来啊
【在 w******l 的大作中提到】
: google knapsack problem
:
: 个数
|
p*********9
发帖数: 30 | 6 bool calculateSum(int[] A, int s, int sum)
{
if( sum < 0 || s < 0 ) return false;
if( A[s] == sum )
{
printf(" %d ", A[s]);
return true;
}
if( calculateSum(A, s-1, sum) ) return true;
if( calculateSum(A, s-1, sum-A[s] )
{
printf(" %d ", A[s]);
return true;
}
return false;
}
【在 y****n 的大作中提到】
: 谢谢！能讲得更具体点吗？
: 我当时是要我把code写出来啊
|
t**e
发帖数: 208 | 7 dynamic programming, matrix sum[i][j] = 1 indicate there is a subset of a0..
ai which sum up to j, then update like:
sum[i][j] = sum[i-1][j] || sum[i-1][j-vi]
until j==expected sum |
y****n
发帖数: 192 | 8 这个貌似是return true or false ， 不是具体的哪几个数
【在 p*********9 的大作中提到】
: bool calculateSum(int[] A, int s, int sum)
: {
: if( sum < 0 || s < 0 ) return false;
: if( A[s] == sum )
: {
: printf(" %d ", A[s]);
: return true;
: }
: if( calculateSum(A, s-1, sum) ) return true;
: if( calculateSum(A, s-1, sum-A[s] )
|
y****n
发帖数: 192 | 9 没看懂。。。
..
【在 t**e 的大作中提到】
: dynamic programming, matrix sum[i][j] = 1 indicate there is a subset of a0..
: ai which sum up to j, then update like:
: sum[i][j] = sum[i-1][j] || sum[i-1][j-vi]
: until j==expected sum
|
s****r
发帖数: 11 | 10 printf打印的就是你要的数
【在 y****n 的大作中提到】
: 这个貌似是return true or false ， 不是具体的哪几个数
|
|
|
s*******e
发帖数: 174 | 11 貌似这个 printf 只打印出一种可能性，
实际情况有多种可能性。。
【在 s****r 的大作中提到】
: printf打印的就是你要的数
|
p*********9
发帖数: 30 | 12 Yes. There should be another solution which doesn't use recusive function. I
haven't figured it out.
【在 s*******e 的大作中提到】
: 貌似这个 printf 只打印出一种可能性，
: 实际情况有多种可能性。。
|
c*****z
发帖数: 182 | 13 第一题你写的什么算法,最简单得n^2算法?
个数
【在 y****n 的大作中提到】
: 是现场写code的面试。
: 第一道是写一个函数，两个参数（String prefix, String s）, 返回true如果s有
: prefix
: 第二道是写一个函数，两个参数（int[] a, int sum), 找出数组里加起来是sum的几个数
: 我第一题算是答出来了，第二题没做完，没有好的思路。。。
: 大人指教一下
|
g*******y
发帖数: 1930 | 14 don't you think it's exponential solution?
Any way, I myself doubt if there's exist a polynomial solution.
【在 p*********9 的大作中提到】
: bool calculateSum(int[] A, int s, int sum)
: {
: if( sum < 0 || s < 0 ) return false;
: if( A[s] == sum )
: {
: printf(" %d ", A[s]);
: return true;
: }
: if( calculateSum(A, s-1, sum) ) return true;
: if( calculateSum(A, s-1, sum-A[s] )
|
i********r
发帖数: 12113 | 15 this is a 0-1 knapsack problem which has been proved a NP problem. even with
the same unit price.
【在 g*******y 的大作中提到】
: don't you think it's exponential solution?
: Any way, I myself doubt if there's exist a polynomial solution.
|
y****n
发帖数: 192 | 16 有那么夸张吗？
private static Boolean isPrefix(String prefix, String s1) {
if(prefix.length()>s1.length())
return false;
for(int i=0; i
boolean t = prefix.charAt(i)==s1.charAt(i);
if (false==t)
return false;
else if (true==t&& i == prefix.length()-1)
return true;
}
return false;
}
【在 c*****z 的大作中提到】
: 第一题你写的什么算法,最简单得n^2算法?
:
: 个数
|
y****n
发帖数: 192 | 17 有那么夸张吗？
private static Boolean isPrefix(String prefix, String s1) {
if(prefix.length()>s1.length())
return false;
for(int i=0; i
boolean t = prefix.charAt(i)==s1.charAt(i);
if (false==t)
return false;
else if (true==t&& i == prefix.length()-1)
return true;
}
return false;
}
【在 c*****z 的大作中提到】
: 第一题你写的什么算法,最简单得n^2算法?
:
: 个数
|
p*********9
发帖数: 30 | 18 don't know how to output those found numbers. But, all combination can be
found in the arrya B. BTW, it is the 0-1 knapsack problem. The time should
be O(n*sum).
void calculateSum(int[] A, int sum)
{
arrary B[n+1,sum+1];//suppose B has been defined.
for(i=1;i<=n;i++) B[i][0] = 0;
for(i=0;i<=sum;i++) B[0][i] = 0;
for(i=1..n)
{
for(w=0;w<=sum;w++)
{
if( A[i] > w ) B[i,w] = B[i-1, w];
else B[i,w] = max( A[i]+B[i-1,w-A[i]), B[i-1,w]);
}
}
}
with
【在 i********r 的大作中提到】
: this is a 0-1 knapsack problem which has been proved a NP problem. even with
: the same unit price.
|
g*******y
发帖数: 1930 | 19 ha, there you go!
How can an interviewer ask a NP problem! Can I just use brute force?!
with
【在 i********r 的大作中提到】
: this is a 0-1 knapsack problem which has been proved a NP problem. even with
: the same unit price.
|
s********y
发帖数: 3811 | 20 bruce force is 2^n.. too high.
【在 g*******y 的大作中提到】
: ha, there you go!
: How can an interviewer ask a NP problem! Can I just use brute force?!
:
: with
|
|
|
g*******y
发帖数: 1930 | 21 if the result is false, the previous algorithm will also run 2^n.
plus, if you just enumerate 1 ~ 2^n, you are guaranteed to find all answers.
【在 s********y 的大作中提到】
: bruce force is 2^n.. too high.
|
t**e
发帖数: 208 | 22 the complexity should be (number of element)*(expected sum), just fill in a
matrix, did I miss anything?
【在 s********y 的大作中提到】
: bruce force is 2^n.. too high.
|
o******e
发帖数: 1001 | 23 感觉到不是knapsack problem。knapsack problem 是在满足背包容量的情况下求最大
的utility。knapsack problem能转化成graph用动态规划来解。但是把它转化成graph
的时候用的是枚举法。而这个问题只是求满足条件的所有数组。
另外，我觉得这个问题不是一般的动态规划能解得。动态规划的目的是求一个最优解，
而这个问题只是问满足条件的解。如果这个问题时求在sum一定的情况下，找一个组成
这个sum的数的积最大，那么这个问题可能可以用constrained dynamic programming来
解。但是显然，对于面试写code，这是太难了。
【在 w******l 的大作中提到】
: google knapsack problem
:
: 个数
|
Q******e
发帖数: 85 | 24 This is Subset sum problem, NP-complete |
x***y
发帖数: 633 | 25 Your program is to check whether the prefix of s1 is the string "prefix",
but what that guy said is to check whether the string "prefix" is in the
string "s1".
For the second problem, it's the subset sum problem, a special case of 0-1
knapsack problem and you can find the subset by tracing back the table...
It's pseudo-polynomial algorithm, which runs as O(n*Sum), where n is the length of
a...Tracing back table cost O(n) time...
//below just my program, probably not the best
//the key part of it
【在 y****n 的大作中提到】
: 有那么夸张吗？
: private static Boolean isPrefix(String prefix, String s1) {
: if(prefix.length()>s1.length())
: return false;
: for(int i=0; i:
: boolean t = prefix.charAt(i)==s1.charAt(i);
: if (false==t)
: return false;
: else if (true==t&& i == prefix.length()-1)
|
a*****g
发帖数: 19398 | 26 太復雜了
length of
【在 x***y 的大作中提到】
: Your program is to check whether the prefix of s1 is the string "prefix",
: but what that guy said is to check whether the string "prefix" is in the
: string "s1".
: For the second problem, it's the subset sum problem, a special case of 0-1
: knapsack problem and you can find the subset by tracing back the table...
: It's pseudo-polynomial algorithm, which runs as O(n*Sum), where n is the length of
: a...Tracing back table cost O(n) time...
: //below just my program, probably not the best
: //the key part of it
|
y****e
发帖数: 158 | 27 你这个明显不对。
【在 y****n 的大作中提到】
: 有那么夸张吗？
: private static Boolean isPrefix(String prefix, String s1) {
: if(prefix.length()>s1.length())
: return false;
: for(int i=0; i:
: boolean t = prefix.charAt(i)==s1.charAt(i);
: if (false==t)
: return false;
: else if (true==t&& i == prefix.length()-1)
|
g*******y
发帖数: 1930 | 28 算法导论，章节35.5。
NPC。
Case settled。
a
【在 t**e 的大作中提到】
: the complexity should be (number of element)*(expected sum), just fill in a
: matrix, did I miss anything?
|
g*******y
发帖数: 1930 | 29 第一题不是很清楚题意，不过应该不难，什么叫做s“有”prefix？这个“有”可以很
模糊啊。
个数
【在 y****n 的大作中提到】
: 是现场写code的面试。
: 第一道是写一个函数，两个参数（String prefix, String s）, 返回true如果s有
: prefix
: 第二道是写一个函数，两个参数（int[] a, int sum), 找出数组里加起来是sum的几个数
: 我第一题算是答出来了，第二题没做完，没有好的思路。。。
: 大人指教一下
|
g******i
发帖数: 354 | 30 如果只是说Prefix, 也就是说一定要从Soure String's 0 poition 开始， 这个是对的
。It's different from String.indexof(target), which is more difficult
because the 'target' can begin from any place of the source String. Taking a
look the source code of String.idnexof really helps. As below:
/**
* Code shared by String and StringBuffer to do searches. The source is
the character array being searched, and the target is
* the string being searched for.
*
* @param source the characters being searched.
【在 y****e 的大作中提到】
: 你这个明显不对。
|
|
|
a******h
发帖数: 19 | 31 I use dynamic programming to solve Q2. My solution required a sorted
integer array as input. The boolean array is the solution.
public static void main (String [] args) {
int [] intList = {1, 3, 5, 6, 8, 9, 11, 12};
boolean [] boolList = subsetSum(intList, 10);
System.out.println(Arrays.toString(intList));
System.out.println(Arrays.toString(boolList));
}
public static boolean [] subsetSum(int [] intList, int sum) {
if (su |
