t*********2
发帖数: 32 | 1 【 以下文字转载自 JobHunting 讨论区 】
发信人: tianyagirl2 (呢喃), 信区: JobHunting
标 题: Google面试怎么这么难啊，LG很难过，我该怎么劝他呢？ (转载)
发信站: BBS 未名空间站 (Tue Apr 6 02:05:31 2010, 美东)
发信人: tianyagirl2 (呢喃), 信区: SanFrancisco
标 题: Google面试怎么这么难啊，LG很难过，我该怎么劝他呢？
发信站: BBS 未名空间站 (Tue Apr 6 02:02:54 2010, 美东)
LG很不容易拿到Google的面试，对方上来问他如何用最少的硬币凑出给出的面额。居然还要当场coding，并且一个字母一个字母的念给他听。没想到Google会在电话里问这么难的题目。LG想出了一种recursive的解法，但是面试官不满意，一定要动态规划的解法。LG后来没有code出来。过几天Google来信就说fail了，一点机会都不给。
Google的面试怎么这么难啊？动态规划不是做research才会用到的么？实际工作中真的需要么？LG以前也 |
w***g
发帖数: 5958 | 2 恕我直言，这题不能更简单了。标准的动态规划啊--对初中生讲动态规划用的就是这种
题目。再简单就没什么技术性了。
按说动态规划也可以用recursive解法，只要保存状态就可以。但显然对方care的是你
LG有没有受过算法方面的训连，有没有编过这样的练习题。而不是真的让他现场想这个
算法。
然还要当场coding，并且一个字母一个字母的念给他听。没想到Google会在电话里问这
么难的题目。LG想出了一种recursive的解法，但是面试官不满意，一定要动态规划的
解法。LG后来没有code出
才会用到的么？实际工作中真的需要么？LG以前也面世过很多bay area的公司，就没见
过这么难的面试题。LG很难过，我该怎么劝他呢？
【在 t*********2 的大作中提到】
: 【 以下文字转载自 JobHunting 讨论区 】
: 发信人: tianyagirl2 (呢喃), 信区: JobHunting
: 标 题: Google面试怎么这么难啊，LG很难过，我该怎么劝他呢？ (转载)
: 发信站: BBS 未名空间站 (Tue Apr 6 02:05:31 2010, 美东)
: 发信人: tianyagirl2 (呢喃), 信区: SanFrancisco
: 标 题: Google面试怎么这么难啊，LG很难过，我该怎么劝他呢？
: 发信站: BBS 未名空间站 (Tue Apr 6 02:02:54 2010, 美东)
: LG很不容易拿到Google的面试，对方上来问他如何用最少的硬币凑出给出的面额。居然还要当场coding，并且一个字母一个字母的念给他听。没想到Google会在电话里问这么难的题目。LG想出了一种recursive的解法，但是面试官不满意，一定要动态规划的解法。LG后来没有code出来。过几天Google来信就说fail了，一点机会都不给。
: Google的面试怎么这么难啊？动态规划不是做research才会用到的么？实际工作中真的需要么？LG以前也
|
n*s
发帖数: 599 | 3 这个。。。。subset sum是np hard的啊。。。。。初中生怎么会做？
世过很多bay area的公司，就没见
【在 w***g 的大作中提到】
: 恕我直言，这题不能更简单了。标准的动态规划啊--对初中生讲动态规划用的就是这种
: 题目。再简单就没什么技术性了。
: 按说动态规划也可以用recursive解法，只要保存状态就可以。但显然对方care的是你
: LG有没有受过算法方面的训连，有没有编过这样的练习题。而不是真的让他现场想这个
: 算法。
:
: 然还要当场coding，并且一个字母一个字母的念给他听。没想到Google会在电话里问这
: 么难的题目。LG想出了一种recursive的解法，但是面试官不满意，一定要动态规划的
: 解法。LG后来没有code出
: 才会用到的么？实际工作中真的需要么？LG以前也面世过很多bay area的公司，就没见
|
w***g
发帖数: 5958 | 4 这个显然不是subset sum。假设没种面值都有足够多的情况下，用最少的张数凑出需要
的总和。
【在 n*s 的大作中提到】
: 这个。。。。subset sum是np hard的啊。。。。。初中生怎么会做？
:
: 世过很多bay area的公司，就没见
|
f*****w
发帖数: 2602 | 5
这样子岂不是贪心就可以了 也不用动规吧
【在 w***g 的大作中提到】
: 这个显然不是subset sum。假设没种面值都有足够多的情况下，用最少的张数凑出需要
: 的总和。
|
o****e
发帖数: 92 | 6 典型面值{1,2,5,10,...}的话Greedy是正确的
但可以人为构造出面值使得Greedy的结果不正确而必须用DP
需要
【在 f*****w 的大作中提到】
:
: 这样子岂不是贪心就可以了 也不用动规吧
|
a****9
发帖数: 418 | 7 我小学时候参加计算机竞赛碰到过这道题, 凑硬币
我用了greedy 其他同学用了搜索
结果结果居然被我蒙对了
站:
research
【在 w***g 的大作中提到】
: 这个显然不是subset sum。假设没种面值都有足够多的情况下，用最少的张数凑出需要
: 的总和。
|
w***g
发帖数: 5958 | 8 我觉得小学的计算机竞赛和大学的计算机竞赛在题目难度上没什么本质的区别。大学生
竞赛用的测试数据更加变态而已。
【在 a****9 的大作中提到】
: 我小学时候参加计算机竞赛碰到过这道题, 凑硬币
: 我用了greedy 其他同学用了搜索
: 结果结果居然被我蒙对了
:
: 站:
: research
|
a****9
发帖数: 418 | 9 我想了想
对于通用的硬币面值, 50cent 25cent 10cent 5cent 1cent
其实greedy是足够的
【在 w***g 的大作中提到】
: 我觉得小学的计算机竞赛和大学的计算机竞赛在题目难度上没什么本质的区别。大学生
: 竞赛用的测试数据更加变态而已。
|
f*****w
发帖数: 2602 | 10 嗯 好像确实是 从来没细想过
是不是所有面额全互质的情况？ 能不能展开讨论一下
【在 o****e 的大作中提到】
: 典型面值{1,2,5,10,...}的话Greedy是正确的
: 但可以人为构造出面值使得Greedy的结果不正确而必须用DP
:
: 需要
|
|
|
d******7
发帖数: 673 | 11 展开说说~
【在 o****e 的大作中提到】
: 典型面值{1,2,5,10,...}的话Greedy是正确的
: 但可以人为构造出面值使得Greedy的结果不正确而必须用DP
:
: 需要
|
m*****7
发帖数: 67 | 12 1,7,10三种硬币，
凑14
展开说说~
【在 d******7 的大作中提到】
: 展开说说~
|
p*******r
发帖数: 475 | 13 NP-hard的问题照样可以用动规做，动规和递归没有任何本质区别
【在 n*s 的大作中提到】
: 这个。。。。subset sum是np hard的啊。。。。。初中生怎么会做？
:
: 世过很多bay area的公司，就没见
|
d*****u
发帖数: 17243 | 14 这个好像是算法课的基础题目啊，如果学过的应该都知道。
Greedy算法对某些数值不能保证得到最优解，但是大部分情况下可以蒙对。 |
x**y
发帖数: 10012 | 15 recursion是个方法
dp是个解决问题的思路
dp use recursion
【在 p*******r 的大作中提到】
: NP-hard的问题照样可以用动规做，动规和递归没有任何本质区别
|
p***d
发帖数: 2171 | 16 实现不用recursion, 否则就不叫DP了
【在 x**y 的大作中提到】
: recursion是个方法
: dp是个解决问题的思路
: dp use recursion
|
D****A
发帖数: 360 | 17 动态规划太可以递归了
【在 p***d 的大作中提到】
: 实现不用recursion, 否则就不叫DP了
|
x**y
发帖数: 10012 | 18 有top down and bottom up 两种。。。
【在 D****A 的大作中提到】
: 动态规划太可以递归了
|
r****o
发帖数: 1950 | 19 top down就是递归吧。
【在 x**y 的大作中提到】
: 有top down and bottom up 两种。。。
|
b******t
发帖数: 965 | 20 不过要加memorization
【在 D****A 的大作中提到】
: 动态规划太可以递归了
|
|
|
b******t
发帖数: 965 | 21 http://en.wikipedia.org/wiki/Dynamic_programming
This can be achieved in either of two ways:[citation needed]
Top-down approach: This is the direct fall-out of the recursive formulation
of any problem. If the solution to any problem can be formulated recursively
using the solution to its subproblems, and if its subproblems are
overlapping, then one can easily memoize or store the solutions to the
subproblems in a table. Whenever we attempt to solve a new subproblem, we
first check the table to s
【在 p***d 的大作中提到】
: 实现不用recursion, 否则就不叫DP了
|
D****A
发帖数: 360 | 22 注意拼写噢 ;)
是memoization
【在 b******t 的大作中提到】
: 不过要加memorization
|
b******t
发帖数: 965 | 23 thanks
原来这个词是从memo来的
我一直以为是从memory来的呢
【在 D****A 的大作中提到】
: 注意拼写噢 ;)
: 是memoization
|
D****A
发帖数: 360 | 24 是我自己犯过的错误，当初写东西时被改过来的 :)
【在 b******t 的大作中提到】
: thanks
: 原来这个词是从memo来的
: 我一直以为是从memory来的呢
|
k*******d
发帖数: 701 | 25 这个是算法的最基础的题了吧？
没受过训练如果去了google也难受，想想人家都能做出来自己做不出来多郁闷啊。又不
是自己笨，其实就是没受过相关的训练而已。 |
k*******d
发帖数: 701 | 26 这个是算法的最基础的题了吧？
没受过训练如果去了google也难受，想想人家都能做出来自己做不出来多郁闷啊。又不
是自己笨，其实就是没受过相关的训练而已。 |
k**0
发帖数: 19737 | 27 这种烂题就是考考刚出校门的人用的, 脑筋急转弯之类. 和正式工作有P个关系.
最烦遇到这种面世的人. |
c********e
发帖数: 215 | 28 学计算机的这个是很一般的题吧，只能说你老公能力还差了一些 |
b******t
发帖数: 965 | 29 en 做出来后 会问如果有负的硬币面值怎么办
【在 c********e 的大作中提到】
: 学计算机的这个是很一般的题吧，只能说你老公能力还差了一些
|
n*s
发帖数: 599 | 30 咋办？
【在 b******t 的大作中提到】
: en 做出来后 会问如果有负的硬币面值怎么办
|
|
|
b******t
发帖数: 965 | 31 那就不能DP啦
【在 n*s 的大作中提到】
: 咋办？
|
n*****g
发帖数: 82 | 32 如果所有的面值都是整数的话，这个问题就是subset sum问题的optimization version
, 是np-hard。
动态规划算法的时间复杂度是O(nk),k是需要凑的面值的总和，n是所给的不同面值的个
数。
【在 w***g 的大作中提到】
: 这个显然不是subset sum。假设没种面值都有足够多的情况下，用最少的张数凑出需要
: 的总和。
|
b******t
发帖数: 965 | 33 看同样base的硬币能不能用多个了
version
【在 n*****g 的大作中提到】
: 如果所有的面值都是整数的话，这个问题就是subset sum问题的optimization version
: , 是np-hard。
: 动态规划算法的时间复杂度是O(nk),k是需要凑的面值的总和，n是所给的不同面值的个
: 数。
|
n*****g
发帖数: 82 | 34 可以用多个！
【在 b******t 的大作中提到】
: 看同样base的硬币能不能用多个了
:
: version
|
i******t
发帖数: 370 | 35 还是可以用DP的，因为最优解negative coin的数目是bounded（假设面值都是整数）。
【在 b******t 的大作中提到】
: 那就不能DP啦
|
i******t
发帖数: 370 | 36 bike兄，你怎么想出这么无厘头的extension...
【在 b******t 的大作中提到】
: en 做出来后 会问如果有负的硬币面值怎么办
|
b******t
发帖数: 965 | 37 话说数轴上 负2000到正2000之间有两个数 a 和 b
一匹马在数轴上可以+-12, +-7, +-3的跳动
从a到b最少需要跳动多少次
【在 i******t 的大作中提到】
: bike兄，你怎么想出这么无厘头的extension...
|
i******t
发帖数: 370 | 38 话说一个bt的parking machine，上面有三个button，可以+1,+10,-3min问至少要按多
少次才能print一张59min的ticket
【在 b******t 的大作中提到】
: 话说数轴上 负2000到正2000之间有两个数 a 和 b
: 一匹马在数轴上可以+-12, +-7, +-3的跳动
: 从a到b最少需要跳动多少次
|
n*****g
发帖数: 82 | 39 335?
【在 b******t 的大作中提到】
: 话说数轴上 负2000到正2000之间有两个数 a 和 b
: 一匹马在数轴上可以+-12, +-7, +-3的跳动
: 从a到b最少需要跳动多少次
|
O*******d
发帖数: 20343 | 40 面试成功的机会是，你的知识和对方的知识的交集越大就越容易成功。 不要以为考你
的人有多牛比，你出一道题照样可以把他考趴。 |
|
|
z****e
发帖数: 2024 | 41 every one is talking about nonsense.
if this is sooooo easy, could any one be so nice as to spend 10 mins to
write a piece of code?
I wrote one, use recursive + greedy.(c++)
the core function is about 25 lines or less.
including the headers, main() test, and a homemade printstack function, the
total is about 45 lines to complete everything and with IO. |
z****e
发帖数: 2024 | 42 greedy can find one solution, but not necessarily the optimal.
a quick and dirty way is to unleash the code to find all possible
combinations and save only the stack which has the smallest size.
i use stack to save the coin combinations, so pop() is easy to perform when
moving to next smaller coin.
i guess there should be better solution. |
b******t
发帖数: 965 | 43 #include
#include
#include
using namespace std;
int main(int argc, char* argv[])
{
int numCoinType=atoi(argv[1]);
vector CoinType;
int i,j,k;
for(i=0;i
CoinType.push_back(atoi(argv[2+i]));
int testVal=atoi(argv[2+i]);
vector testVector;
testVector.resize(testVal+1);
for(i=0;i
testVector[i]=INT_MAX-1;
testVector[0]=0;
【在 z****e 的大作中提到】
: greedy can find one solution, but not necessarily the optimal.
: a quick and dirty way is to unleash the code to find all possible
: combinations and save only the stack which has the smallest size.
: i use stack to save the coin combinations, so pop() is easy to perform when
: moving to next smaller coin.
: i guess there should be better solution.
|
z****e
发帖数: 2024 | 44 this is nice DP.
if face values can be saved as well, that's wonderful.
btw, to reserve the size of a vector, resize() is usually not as efficient as reserve().
【在 b******t 的大作中提到】
: #include
: #include
: #include
: using namespace std;
: int main(int argc, char* argv[])
: {
: int numCoinType=atoi(argv[1]);
: vector CoinType;
: int i,j,k;
: for(i=0;i
|
T*****9
发帖数: 2484 | 45 这么简单的DP都不会。。。只能去research部门了。。。
然还要当场coding，并且一个字母一个字母的念给他听。没想到Google会在电话里问这
么难的题目。LG想出了一种recursive的解法，但是面试官不满意，一定要动态规划的
解法。LG后来没有code出来。过几:
的需要么？LG以前也面世过很多bay area的公司，就没见过这么难的面试题。LG很难过
，我该怎么劝他呢？
【在 t*********2 的大作中提到】
: 【 以下文字转载自 JobHunting 讨论区 】
: 发信人: tianyagirl2 (呢喃), 信区: JobHunting
: 标 题: Google面试怎么这么难啊，LG很难过，我该怎么劝他呢？ (转载)
: 发信站: BBS 未名空间站 (Tue Apr 6 02:05:31 2010, 美东)
: 发信人: tianyagirl2 (呢喃), 信区: SanFrancisco
: 标 题: Google面试怎么这么难啊，LG很难过，我该怎么劝他呢？
: 发信站: BBS 未名空间站 (Tue Apr 6 02:02:54 2010, 美东)
: LG很不容易拿到Google的面试，对方上来问他如何用最少的硬币凑出给出的面额。居然还要当场coding，并且一个字母一个字母的念给他听。没想到Google会在电话里问这么难的题目。LG想出了一种recursive的解法，但是面试官不满意，一定要动态规划的解法。LG后来没有code出来。过几天Google来信就说fail了，一点机会都不给。
: Google的面试怎么这么难啊？动态规划不是做research才会用到的么？实际工作中真的需要么？LG以前也
|
o****e
发帖数: 92 | 46 假设各面值储备充足，那么找零问题不是 Subset Sum
如果所有的面值都是整数的话，这个问题就是subset sum问题的optimization version
, 是np-hard。
动态规划算法的时间复杂度是O(nk),k是需要凑的面值的总和，n是所给的不同面值的个
数。
【在 n*****g 的大作中提到】
: 如果所有的面值都是整数的话，这个问题就是subset sum问题的optimization version
: , 是np-hard。
: 动态规划算法的时间复杂度是O(nk),k是需要凑的面值的总和，n是所给的不同面值的个
: 数。
|
r****o
发帖数: 1950 | 47 多谢，这个算法是针对每种硬币无穷多的情况吧，
如果各种硬币只有有限多个，如1分10个，2分8个，5分4个，10分3个，25分2个。
还可以用DP吗?
【在 b******t 的大作中提到】
: #include
: #include
: #include
: using namespace std;
: int main(int argc, char* argv[])
: {
: int numCoinType=atoi(argv[1]);
: vector CoinType;
: int i,j,k;
: for(i=0;i
|
f******2
发帖数: 1027 | 48 同意，Greedy算法对某些数值不能保证得到最优解。
greedy和DP还是有区别的，比如0-1背包问题和背包问题。
【在 d*****u 的大作中提到】
: 这个好像是算法课的基础题目啊，如果学过的应该都知道。
: Greedy算法对某些数值不能保证得到最优解，但是大部分情况下可以蒙对。
|
n*****g
发帖数: 82 | 49 对，是不一样，一个是有限集，一个是无限集。
而且这个问题不比Subset Sum难，不过我觉得似乎也是NP-hard的。
就算法来讲，这2个问题都可以用DP在O(nk)的时间内解决！
version
【在 o****e 的大作中提到】
: 假设各面值储备充足，那么找零问题不是 Subset Sum
:
: 如果所有的面值都是整数的话，这个问题就是subset sum问题的optimization version
: , 是np-hard。
: 动态规划算法的时间复杂度是O(nk),k是需要凑的面值的总和，n是所给的不同面值的个
: 数。
|
r****o
发帖数: 1950 | 50 嫩不能说说各种硬币数有限的情况下用DP怎么解？多谢。
【在 n*****g 的大作中提到】
: 对，是不一样，一个是有限集，一个是无限集。
: 而且这个问题不比Subset Sum难，不过我觉得似乎也是NP-hard的。
: 就算法来讲，这2个问题都可以用DP在O(nk)的时间内解决！
:
: version
|
|
|
T**********n
发帖数: 480 | 51 闲
【在 b******t 的大作中提到】
: #include
: #include
: #include
: using namespace std;
: int main(int argc, char* argv[])
: {
: int numCoinType=atoi(argv[1]);
: vector CoinType;
: int i,j,k;
: for(i=0;i
|
T**********n
发帖数: 480 | 52 一样还是dp
你把这个想像成无向图求从0节点到任意节点间最短路就行了
就是Dijkstra，也算一种DP吧
【在 r****o 的大作中提到】
: 嫩不能说说各种硬币数有限的情况下用DP怎么解？多谢。
|
r****o
发帖数: 1950 | 53 这怎么想象阿，呵呵。
能不能说详细点。
【在 T**********n 的大作中提到】
: 一样还是dp
: 你把这个想像成无向图求从0节点到任意节点间最短路就行了
: 就是Dijkstra，也算一种DP吧
|
T**********n
发帖数: 480 | 54 最开始就一个节点0，一个硬币都不用
然后构建图，在已有n个节点上加n条边，每边的权重都是1
比如已经有节点x1,x2,x3...加一个五分硬币进来
那(x1,x1+5) (x2,x2+5) (x3,x3+5) ...就多了这么多条边
要凑x就找一条从0到x的最短路
【在 r****o 的大作中提到】
: 这怎么想象阿，呵呵。
: 能不能说详细点。
|
d****l
发帖数: 40 | |
n*****g
发帖数: 82 | 56 这种情况下，用DP解的时间复杂度也是O(nk), 算法如下，方便起见，把其它2个种情况
也一起说了。
Input:
1.n种不同的面值,数组a[1,2...n], 每个a[i]是第i个面值的value
2.每种面值限定的个数，数组b[1,2,...n]，每个b[i]是第i个面值限定的个数
3.需要组成的目标值，k
要求以上所有的数都是正整数
Output:
最小数目的硬币，使得他们的面值和是K, 要求第i个面值的硬币不能超过b[i]
1.先定义DP的sub problem
sub(t,m): 表示用前m种面值的所有硬币（即a[1,2...m]）来组成面值和为t所需要的最
小数目的硬币的个数，要求第i个面值的硬币不能超过b[i]
所以我们的最终目标是求sub(k,n)
2.定义DP的dependency relation
Version (1): 要求每种面值只用一次，即b[i]=1, for each i, then
sub(t,m) = min{sub(t-a[m],m-1)+1, sub(t,m-1)}
即：为了求sub(t,m)，我们有2种选择：或者用面值m的硬币，或者不用
Ve
【在 r****o 的大作中提到】
: 嫩不能说说各种硬币数有限的情况下用DP怎么解？多谢。
|
r****o
发帖数: 1950 | 57 非常感谢。
【在 n*****g 的大作中提到】
: 这种情况下，用DP解的时间复杂度也是O(nk), 算法如下，方便起见，把其它2个种情况
: 也一起说了。
: Input:
: 1.n种不同的面值,数组a[1,2...n], 每个a[i]是第i个面值的value
: 2.每种面值限定的个数，数组b[1,2,...n]，每个b[i]是第i个面值限定的个数
: 3.需要组成的目标值，k
: 要求以上所有的数都是正整数
: Output:
: 最小数目的硬币，使得他们的面值和是K, 要求第i个面值的硬币不能超过b[i]
: 1.先定义DP的sub problem
|
l******e
发帖数: 470 | 58 这个版上能10分钟写出来的真不是少数
the
【在 z****e 的大作中提到】
: every one is talking about nonsense.
: if this is sooooo easy, could any one be so nice as to spend 10 mins to
: write a piece of code?
: I wrote one, use recursive + greedy.(c++)
: the core function is about 25 lines or less.
: including the headers, main() test, and a homemade printstack function, the
: total is about 45 lines to complete everything and with IO.
|
l******e
发帖数: 470 | 59 sumset sum里数可以用一次，可以用无数次，2个版本都是nphard
【在 n*****g 的大作中提到】
: 对，是不一样，一个是有限集，一个是无限集。
: 而且这个问题不比Subset Sum难，不过我觉得似乎也是NP-hard的。
: 就算法来讲，这2个问题都可以用DP在O(nk)的时间内解决！
:
: version
|
