logo
Redian新闻
>未名空间
>Music - 天籁之音
>
【翻唱】fra -- 童话(光良)
avatar
【翻唱】fra -- 童话(光良)# Music - 天籁之音
t*2
1 楼
【 以下文字转载自 SanFrancisco 讨论区 】
发信人: 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以前也面世过很多bay area的公司，就没见过这么难的面试题。LG很难过，我该怎么劝他呢？
avatar
w*5
2 楼
avatar
f*a
3 楼
创作说明:
上次被批评了音准和气息。。 这次想稳住气息的， 希望稍微好点吧。。
这首歌熟悉度比身边高，最后的高音带了点情绪录了好几次才整好的。
欢迎拍砖，我会改的。。 后期就随便用了个混响。
歌曲链接:
曲作者:
光良
词作者:
光良
原唱:
光良
歌词:
忘了有多久再没听到你
对我说你最爱的故事
我想了很久我开始慌了
是不是我又做错了什么
你哭着对我说
童话里都是骗人的
我不可能是你的王子
也许你不会懂
从你说爱我以后
我的天空星星都亮了
我愿变成童话里
你爱的那个天使
张开双手
变成翅膀守护你
你要相信
相信我们会像童话故事里
幸福和快乐是结局
你哭着对我说
童话里都是骗人的
我不可能是你的王子
也许你不会懂
从你说爱我以后
我的天空星星都亮了
我愿变成童话里
你爱的那个天使
张开双手变成翅膀守护你
你要相信
相信我们会像童话故事里
幸福和快乐是结局
我要变成童话里
你爱的那个天使
张开双手
变成翅膀守护你
你要相信
相信我们会像童话故事里
幸福和快乐是结局
我会变成童话里
你爱的那个天使
张开双手
变成翅膀守护你
你要相信
相信我们会像童话故事里
幸福和快乐是结局
一起写我们的结局
avatar
r*o
4 楼
先cft一下,
硬币问题可以用Greedy算法吧。

然还要当场coding，并且一个字母一个字母的念给他听。没想到Google会在电话里问这
么难的题目。LG想出了一种recursive的解法，但是面试官不满意，一定要动态规划的
解法。LG后来没有code出
才会用到的么？实际工作中真的需要么？LG以前也面世过很多bay area的公司，就没见
过这么难的面试题。LG很难过，我该怎么劝他呢？

【在 t*********2 的大作中提到】
: 【 以下文字转载自 SanFrancisco 讨论区 】
: 发信人: 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以前也面世过很多bay area的公司，就没见过这么难的面试题。LG很难过，我该怎么劝他呢？
avatar
l*e
5 楼
这歌还真不好唱，我到最后的高音也盯得很，fra完成得很不错，节奏感也很好。
你本身得音质也不错。多奔。
avatar
d*8
6 楼
奇怪了，DP难道不就是Recursive吗？
这道题目一个小公司也留给我作业的，我写了DP发过去，那边一开始说我程序写错了。
我回信说程序没错我还有Testing例子的，然后那边又说我DP不是最优解..
我在想，妈呀，难道他还用贪婪做嘛，就没争论Move on了。

然还要当场coding，并且一个字母一个字母的念给他听。没想到Google会在电话里问这
么难的题目。LG想出了一种recursive的解法，但是面试官不满意，一定要动态规划的
解法。LG后来没有code出
才会用到的么？实际工作中真的需要么？LG以前也面世过很多bay area的公司，就没见
过这么难的面试题。LG很难过，我该怎么劝他呢？

【在 t*********2 的大作中提到】
: 【 以下文字转载自 SanFrancisco 讨论区 】
: 发信人: 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以前也面世过很多bay area的公司，就没见过这么难的面试题。LG很难过，我该怎么劝他呢？
avatar
t*n
7 楼
小盆友又来了，id带了没有~~
这个歌感觉熟多了，不错!个别音有点飘掉了，字和字之间显得不是特别连贯，觉得应
该是气息不足的原因？多唱多奔~~
avatar
d*8
8 楼
看面额组合的。
比如给你面额组合是24，10. 进来个数字 30，贪婪就挂了。

世过很多bay area的公司，就没见

【在 r****o 的大作中提到】
: 先cft一下,
: 硬币问题可以用Greedy算法吧。
:
: 然还要当场coding，并且一个字母一个字母的念给他听。没想到Google会在电话里问这
: 么难的题目。LG想出了一种recursive的解法，但是面试官不满意，一定要动态规划的
: 解法。LG后来没有code出
: 才会用到的么？实际工作中真的需要么？LG以前也面世过很多bay area的公司，就没见
: 过这么难的面试题。LG很难过，我该怎么劝他呢？
avatar
s*3
9 楼
lz的声线和光良还颇像呢。。。好听， 赞！

【在 f*a 的大作中提到】
: 创作说明:
: 上次被批评了音准和气息。。 这次想稳住气息的， 希望稍微好点吧。。
: 这首歌熟悉度比身边高，最后的高音带了点情绪录了好几次才整好的。
: 欢迎拍砖，我会改的。。 后期就随便用了个混响。
: 歌曲链接:
: 曲作者:
: 光良
: 词作者:
: 光良
: 原唱:
avatar
r*o
10 楼
贪婪先试最大的，不行再试小的嘛。
这题是不是用贪婪效率更高?

【在 d*******8 的大作中提到】
: 看面额组合的。
: 比如给你面额组合是24，10. 进来个数字 30，贪婪就挂了。
:
: 世过很多bay area的公司，就没见
avatar
f*a
11 楼
一开始最后一个“我们”都没找到掉，因为“我”是吸气，不太好唱。。
为了这个录了好多遍..

【在 l*****e 的大作中提到】
: 这歌还真不好唱，我到最后的高音也盯得很，fra完成得很不错，节奏感也很好。
: 你本身得音质也不错。多奔。
avatar
y*i
12 楼
问一下，这个问题用贪婪是不是用回溯的方法实现？

【在 r****o 的大作中提到】
: 贪婪先试最大的，不行再试小的嘛。
: 这题是不是用贪婪效率更高?
avatar
f*a
13 楼
接下来就该跑步去了。。 把打游戏的增重给减了。。

【在 t*******n 的大作中提到】
: 小盆友又来了，id带了没有~~
: 这个歌感觉熟多了，不错!个别音有点飘掉了，字和字之间显得不是特别连贯，觉得应
: 该是气息不足的原因？多唱多奔~~
avatar
d*8
14 楼
这样的话，每次要回溯上一个面值的一个，也对哦。
就是写起来比较麻烦..

【在 r****o 的大作中提到】
: 贪婪先试最大的，不行再试小的嘛。
: 这题是不是用贪婪效率更高?
avatar
s*o
15 楼
蛮不错，节奏音准基本上木问题～
avatar
c*n
16 楼
greedy有的时候不行的吧
比如硬币：24 10 1
要求30
那最优是 10 10 10
greedy的话是24 1 1 1 1 1 1

【在 r****o 的大作中提到】
: 贪婪先试最大的，不行再试小的嘛。
: 这题是不是用贪婪效率更高?
avatar
f*a
17 楼
谢谢超级猫猫的肯定啊～

【在 s*********3 的大作中提到】
: lz的声线和光良还颇像呢。。。好听， 赞！
avatar
w*e
18 楼
There is no need to feel bad about this.
Just prepare more carefully and your LD will be fine.
And remember: no matter how many offers you get,
you can only take one. So even if A/B/C/... don't
extend you an offer, it only matters when Z does!

然还要当场
coding，并且一个字母一个字母的念给他听。没想到Google会在电话里问这么难的题目
。LG想出了一
种recursive的解法，但是面试官不满意，一定要动态规划的解法。LG后来没有code出
来。过几天
Google来信就说fail了，一点机会都不给。
的需要么？
LG以前也面世过很多bay area的公司，就没见过这么难的面试题。LG很难过，我该怎么
劝他呢？

【在 t*********2 的大作中提到】
: 【 以下文字转载自 SanFrancisco 讨论区 】
: 发信人: 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以前也面世过很多bay area的公司，就没见过这么难的面试题。LG很难过，我该怎么劝他呢？
avatar
a*g
19 楼
深情温油的男声，鉴定完毕！
avatar
y*i
20 楼
好像greedy有时候确实不是最优的

【在 c*********n 的大作中提到】
: greedy有的时候不行的吧
: 比如硬币：24 10 1
: 要求30
: 那最优是 10 10 10
: greedy的话是24 1 1 1 1 1 1
avatar
f*a
21 楼
老师这次不提点意见么。。
avatar
g*y
22 楼
DP好好学习一两天多体会下思想，会发现其实这个题不难的
我以前觉得这题难是因为总觉得DP的性能还不够好...

然还要当场
coding，并且一个字母一个字母的念给他听。没想到Google会在电话里问这么难的题目
。LG想出了一种
recursive的解法，但是面试官不满意，一定要动态规划的解法。LG后来没有code出来
。过几天Google来
信就说fail了，一点机会都不给。
的需要么？LG以前
也面世过很多bay area的公司，就没见过这么难的面试题。LG很难过，我该怎么劝他呢？

【在 t*********2 的大作中提到】
: 【 以下文字转载自 SanFrancisco 讨论区 】
: 发信人: 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以前也面世过很多bay area的公司，就没见过这么难的面试题。LG很难过，我该怎么劝他呢？
avatar
L*n
23 楼
还真是挺像的！
楼主可以加强下对声音稳定度的控制

【在 s*********3 的大作中提到】
: lz的声线和光良还颇像呢。。。好听， 赞！
avatar
a*9
24 楼
的确不能永远用贪婪，试着抛砖引玉一个可以用贪婪的硬币面额情况：
首先注意到为了能表示任意整数，这些硬币面额的最低值必须是1；
记这些面额的为a1>a2>...>an=1,可以用贪婪求解的一个充分条件是：
对任意i( 1<= i <= n)，如果从ai到2ai-1之间的每一个数的最优解都可以包括一个
ai,
那么就可以用贪婪做。
求纠正，是不是必要条件没想好

【在 c*********n 的大作中提到】
: greedy有的时候不行的吧
: 比如硬币：24 10 1
: 要求30
: 那最优是 10 10 10
: greedy的话是24 1 1 1 1 1 1
avatar
b*f
25 楼
唱的比俺好多了～俺要狠狠跟你学习
前面慢歌部分有个别音和原谱可能不对。我当初也听不清，找了谱子来看的。然后倒数
两次副歌是从Fmajor上到Gmajor好象是。
avatar
l*o
26 楼
因为这道题本身就是NP-Hard的。所以没答出来不用难过。
第一句话是真的。第二句话是假的。

DP好好学习一两天多体会下思想，会发现其实这个题不难的
我以前觉得这题难是因为总觉得DP的性能还不够好...
然还要当场
coding，并且一个字母一个字母的念给他听。没想到Google会在电话里问这么难的题目
。LG想出了一种
recursive的解法，但是面试官不满意，一定要动态规划的解法。LG后来没有code出来
。过几天Google来
信就说fail了，一点机会都不给。
的需要么？LG以前
也面世过很多bay area的公司，就没见过这么难的面试题。LG很难过，我该怎么劝他呢？

【在 g*******y 的大作中提到】
: DP好好学习一两天多体会下思想，会发现其实这个题不难的
: 我以前觉得这题难是因为总觉得DP的性能还不够好...
:
: 然还要当场
: coding，并且一个字母一个字母的念给他听。没想到Google会在电话里问这么难的题目
: 。LG想出了一种
: recursive的解法，但是面试官不满意，一定要动态规划的解法。LG后来没有code出来
: 。过几天Google来
: 信就说fail了，一点机会都不给。
: 的需要么？LG以前
avatar
w*w
27 楼
如果每首歌都练上一百遍~~
听得出楼主的努力，变音的部分很难把握~~
avatar
d*8
28 楼
Nod，当时我就想Greedy是不行的嘛， 现在反而糊涂了。。

【在 c*********n 的大作中提到】
: greedy有的时候不行的吧
: 比如硬币：24 10 1
: 要求30
: 那最优是 10 10 10
: greedy的话是24 1 1 1 1 1 1
avatar
b*a
29 楼
声音非常好听！
如果说有啥问题的话，可能就是还是唱的虚了点，不够稳，加油
avatar
a*9
30 楼
NP-hard? 难道你认为动归解这题的复杂度是NP-hard级别的吗
而且如果条件合适，可以用greedy的话，基本就是linear的，除去预处理。

【在 l******o 的大作中提到】
: 因为这道题本身就是NP-Hard的。所以没答出来不用难过。
: 第一句话是真的。第二句话是假的。
:
: DP好好学习一两天多体会下思想，会发现其实这个题不难的
: 我以前觉得这题难是因为总觉得DP的性能还不够好...
: 然还要当场
: coding，并且一个字母一个字母的念给他听。没想到Google会在电话里问这么难的题目
: 。LG想出了一种
: recursive的解法，但是面试官不满意，一定要动态规划的解法。LG后来没有code出来
: 。过几天Google来
avatar
t*5
31 楼
很温柔的男声，我觉得你录音是不是靠话筒太近了？声音有些闷，嘶声也比较重。下次
离话筒至少10-15cm远，看看会不会好一点。
avatar
l*o
32 楼
是NP-hard的，你没有理解这个问题的input是什么。这个问题的input是(a1，a2，……
ak，N），所以input的size是log的，所以DP的算法其实是exponential的。
不要死读书。

NP-hard? 难道你认为动归的复杂度是NP-hard级别的吗
而且如果条件合适，可以用greedy的话，基本就是linear的，除去预处理。

【在 a***9 的大作中提到】
: NP-hard? 难道你认为动归解这题的复杂度是NP-hard级别的吗
: 而且如果条件合适，可以用greedy的话，基本就是linear的，除去预处理。
avatar
f*a
33 楼
版主太犀利了！ 的确有这个问题，现在就4-6cm. 动圈麦拿多了的后果。。
avatar
g*y
34 楼
对
DP只是解决问题的一种方法，跟问题的计算复杂度没有直接关系。
NP-hard的问题的DP解法多了去了，举个例子就是背包问题，还有什么subset sum
我以前纠结的是这个题到底有没有多项式解，总隐隐的感觉能通过一些数论的东西找到
漂亮的快速解。后来
尝试不成功所以感觉很难。如果这个题真是NP-hard，难怪我当时觉得这么难...
greedy in general处理这个问题是不能得到正确解的，heuristic搜索解或者剪枝的回
溯可能平均性能
好些。

【在 l******o 的大作中提到】
: 是NP-hard的，你没有理解这个问题的input是什么。这个问题的input是(a1，a2，……
: ak，N），所以input的size是log的，所以DP的算法其实是exponential的。
: 不要死读书。
:
: NP-hard? 难道你认为动归的复杂度是NP-hard级别的吗
: 而且如果条件合适，可以用greedy的话，基本就是linear的，除去预处理。
avatar
t*5
35 楼
呵呵，你不会是手持着话筒唱的吧。。。电容话筒比较敏感，最好用支架，落地的最好
，最差也要table top的。否则，你唱的时候手一动，就会有噪音出来，都收进干声里
了。
你话放的增益可以开得稍微大一些，嘴离话筒稍微远一些，没有近场效应，还会减少嘶
声和喷麦。

【在 f*a 的大作中提到】
: 版主太犀利了！ 的确有这个问题，现在就4-6cm. 动圈麦拿多了的后果。。
avatar
l*o
36 楼
嗯，TSP还能用DP做呢。

对
DP只有解决问题的一种方法，跟问题的计算复杂度没有直接关系。
NP-hard的问题的DP解法多了去了，举个例子就是背包问题，还有什么subset sum
我以前纠结的是这个题到底有没有多项式解，总隐隐的感觉能通过一些数论的东西找到
漂亮的快速解。后来
尝试不成功所以感觉很难。如果这个题真是NP-hard，难怪我当时觉得这么难...
greedy in general处理这个问题是不能得到正确解的，heuristic搜索解或者剪枝的回
溯可能平均性能
好些。

【在 g*******y 的大作中提到】
: 对
: DP只是解决问题的一种方法，跟问题的计算复杂度没有直接关系。
: NP-hard的问题的DP解法多了去了，举个例子就是背包问题，还有什么subset sum
: 我以前纠结的是这个题到底有没有多项式解，总隐隐的感觉能通过一些数论的东西找到
: 漂亮的快速解。后来
: 尝试不成功所以感觉很难。如果这个题真是NP-hard，难怪我当时觉得这么难...
: greedy in general处理这个问题是不能得到正确解的，heuristic搜索解或者剪枝的回
: 溯可能平均性能
: 好些。
avatar
f*a
37 楼
有支架和pop filter.. 当作动圈麦了，以为考得太近效果越好。 回头增益搞大点。
avatar
a*9
38 楼
有哪里有讲这题么？
为什么它的复杂度是exponential的？请帮我看一下这个方程，
D(i) = min{D(i-a_j)+1, 1<= j<= k}
这样复杂度不是O(N*k)吗？ 我mess up了，sorry

【在 g*******y 的大作中提到】
: 对
: DP只是解决问题的一种方法，跟问题的计算复杂度没有直接关系。
: NP-hard的问题的DP解法多了去了，举个例子就是背包问题，还有什么subset sum
: 我以前纠结的是这个题到底有没有多项式解，总隐隐的感觉能通过一些数论的东西找到
: 漂亮的快速解。后来
: 尝试不成功所以感觉很难。如果这个题真是NP-hard，难怪我当时觉得这么难...
: greedy in general处理这个问题是不能得到正确解的，heuristic搜索解或者剪枝的回
: 溯可能平均性能
: 好些。
avatar
a*e
39 楼
正太你好，这版上女王很多的。
avatar
a*9
40 楼
为啥你们都说这题是exponential的？就算google问一道NP-hard的问题
还是有点奇怪。
你是不是把这题看成其他题目了？ 也可能是我看错了

【在 l******o 的大作中提到】
: 是NP-hard的，你没有理解这个问题的input是什么。这个问题的input是(a1，a2，……
: ak，N），所以input的size是log的，所以DP的算法其实是exponential的。
: 不要死读书。
:
: NP-hard? 难道你认为动归的复杂度是NP-hard级别的吗
: 而且如果条件合适，可以用greedy的话，基本就是linear的，除去预处理。
avatar
n*a
41 楼
这个怯生生的口气还不错跟音色挺配的。从歌词上讲，可以稍微唱得壮一点，比如翅膀
守护你之类的，要有守护召唤的画面哦~~~加油
avatar
m*f
42 楼
DP 解决硬币面值问题是很基础的DP问题啊， 如果你老公有复习DP的话
还是要再复习的多一些把
avatar
f*a
43 楼
下次必须改风格了。。
avatar
h*6
44 楼

DP解法需要O(Nk)的时间和空间，这是伪多项式问题，因为k不是输入参数的一个，而是
输入参数a1, a2, ..., ak的个数。

【在 a***9 的大作中提到】
: 有哪里有讲这题么？
: 为什么它的复杂度是exponential的？请帮我看一下这个方程，
: D(i) = min{D(i-a_j)+1, 1<= j<= k}
: 这样复杂度不是O(N*k)吗？ 我mess up了，sorry
avatar
R*e
45 楼
有谁可以给个这道题的链接吗？
谢谢！

然还要当场coding，并且一个字母一个字母的念给他听。没想到Google会在电话里问这
么难的题目。LG想出了一种recursive的解法，但是面试官不满意，一定要动态规划的
解法。LG后来没有code出
才会用到的么？实际工作中真的需要么？LG以前也面世过很多bay area的公司，就没见
过这么难的面试题。LG很难过，我该怎么劝他呢？

【在 t*********2 的大作中提到】
: 【 以下文字转载自 SanFrancisco 讨论区 】
: 发信人: 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以前也面世过很多bay area的公司，就没见过这么难的面试题。LG很难过，我该怎么劝他呢？
avatar
k*e
46 楼
why dont you google by yourself?
it is easy to figure out the key words: coin, change

世过很多bay area的公司，就没见

【在 R**e 的大作中提到】
: 有谁可以给个这道题的链接吗？
: 谢谢！
:
: 然还要当场coding，并且一个字母一个字母的念给他听。没想到Google会在电话里问这
: 么难的题目。LG想出了一种recursive的解法，但是面试官不满意，一定要动态规划的
: 解法。LG后来没有code出
: 才会用到的么？实际工作中真的需要么？LG以前也面世过很多bay area的公司，就没见
: 过这么难的面试题。LG很难过，我该怎么劝他呢？
avatar
r*o
47 楼
sorry, 误导你了，呵呵。

【在 d*******8 的大作中提到】
: Nod，当时我就想Greedy是不行的嘛， 现在反而糊涂了。。
avatar
C*h
48 楼
1.greedy 不是最优的。
2.这题是CS本科生的DP家庭作业。很基础。
3.你LG准备的不好，但是被GOOGLE锯掉很正常。
avatar
x*3
49 楼
CLRS 2nd edition
习题16-1有详细讨论coin changing问题
avatar
p*j
50 楼
你劝他，amazon等着他呢，干嘛非要microsoft
avatar
l*o
51 楼
因为表示N只需要log(N)bit,所以输入的size不是N而是O(klogN)
所以O(kN)的时间复杂度是exponential的.

为啥你们都说这题是exponential的？就算google问一道NP-hard的问题
还是有点奇怪。
你是不是把这题看成其他题目了？ 也可能是我看错了

【在 a***9 的大作中提到】
: 为啥你们都说这题是exponential的？就算google问一道NP-hard的问题
: 还是有点奇怪。
: 你是不是把这题看成其他题目了？ 也可能是我看错了
avatar
m*u
52 楼
这题是标准DP啊，不过当场给coding是有点儿。。。

然还要当场
coding，并且一个字母一个字母的念给他听。没想到Google会在电话里问这么难的题目
。LG想出了一
种recursive的解法，但是面试官不满意，一定要动态规划的解法。LG后来没有code出
来。过几天
Google来信就说fail了，一点机会都不给。
的需要么？
LG以前也面世过很多bay area的公司，就没见过这么难的面试题。LG很难过，我该怎么
劝他呢？

【在 t*********2 的大作中提到】
: 【 以下文字转载自 SanFrancisco 讨论区 】
: 发信人: 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以前也面世过很多bay area的公司，就没见过这么难的面试题。LG很难过，我该怎么劝他呢？
avatar
w*l
53 楼
cmft.
没必要难过了，运气不太好，想要当场完整写出来，确实不是很容易.....
avatar
s*a
54 楼
汗一个
CLRS是什么书？

【在 x******3 的大作中提到】
: CLRS 2nd edition
: 习题16-1有详细讨论coin changing问题
avatar
r*w
55 楼
这题目是google面试里dynamic programming典型的试题。就在google推荐看的材料里
面的例题。你老公准备不充分。
avatar
a*9
56 楼
thanks!

【在 l******o 的大作中提到】
: 因为表示N只需要log(N)bit,所以输入的size不是N而是O(klogN)
: 所以O(kN)的时间复杂度是exponential的.
:
: 为啥你们都说这题是exponential的？就算google问一道NP-hard的问题
: 还是有点奇怪。
: 你是不是把这题看成其他题目了？ 也可能是我看错了
avatar
a*9
57 楼
嗯，我又绕了一下，是exp的，但这是因为N，不是因为k吧

【在 h**6 的大作中提到】
:
: DP解法需要O(Nk)的时间和空间，这是伪多项式问题，因为k不是输入参数的一个，而是
: 输入参数a1, a2, ..., ak的个数。
avatar
t*5
58 楼
好像之前看到版上有人讨论过这个题目
还有人写了一段代码呢
avatar
r*o
59 楼
我还是没弄明白，为啥这里N的input size看成比特数，所以复杂度是exponential，那
为啥别的题目的N就不用看成比特数呢？

【在 a***9 的大作中提到】
: 嗯，我又绕了一下，是exp的，但这是因为N，不是因为k吧
avatar
a*9
60 楼
直观上我是这么理解的:别的题目中，比如给n个ID，让找一个target的，
那么就是扫一遍就行，我们一看就是linear的，那是因为跟每个ID大小
没关系，只跟有多少个ID有关系。
但这题，复杂度是跟给的N的大小有关系。
所以，定义复杂度，是根据输入串长度的bits数来的，前一个的输入串
长是n*(log ID)，最后做到步骤跟n线性，但这里输入串只需要lgN，也
得做N步，就nb了

【在 r****o 的大作中提到】
: 我还是没弄明白，为啥这里N的input size看成比特数，所以复杂度是exponential，那
: 为啥别的题目的N就不用看成比特数呢？
avatar
D*h
61 楼
因为多项式时间的complexity是相对输入规模而言的,只需要lg n bit就行,但是这里得
到的是关于输入的具体值的多项式时间,相比输入规模,这个是输入规模的指数级.
http://en.wikipedia.org/wiki/Pseudo-polynomial_time

【在 r****o 的大作中提到】
: 我还是没弄明白，为啥这里N的input size看成比特数，所以复杂度是exponential，那
: 为啥别的题目的N就不用看成比特数呢？
avatar
t*t
62 楼
it depends on who is the interviewer. some new-cop is tough
avatar
e*e
63 楼
DP是iterative，不是recursive

世过很多bay area的公司，就没见

【在 d*******8 的大作中提到】
: 奇怪了，DP难道不就是Recursive吗？
: 这道题目一个小公司也留给我作业的，我写了DP发过去，那边一开始说我程序写错了。
: 我回信说程序没错我还有Testing例子的，然后那边又说我DP不是最优解..
: 我在想，妈呀，难道他还用贪婪做嘛，就没争论Move on了。
:
: 然还要当场coding，并且一个字母一个字母的念给他听。没想到Google会在电话里问这
: 么难的题目。LG想出了一种recursive的解法，但是面试官不满意，一定要动态规划的
: 解法。LG后来没有code出
: 才会用到的么？实际工作中真的需要么？LG以前也面世过很多bay area的公司，就没见
: 过这么难的面试题。LG很难过，我该怎么劝他呢？
avatar
r*o
64 楼
多谢，可不可以这么理解:
N个ID找target的那个题目的算法的机器运算的规模跟N的实际大小成线性增长关系，即
N增加1只会导致增加O(1)次运算。
而硬币问题/背包问题的算法的机器运算规模跟N的实际大小成指数增长关系，即N增加1
会导致增加O(#of可选硬币数)次运算(此处是否正确?)。
所以这两种情况的N不一样。

【在 a***9 的大作中提到】
: 直观上我是这么理解的:别的题目中，比如给n个ID，让找一个target的，
: 那么就是扫一遍就行，我们一看就是linear的，那是因为跟每个ID大小
: 没关系，只跟有多少个ID有关系。
: 但这题，复杂度是跟给的N的大小有关系。
: 所以，定义复杂度，是根据输入串长度的bits数来的，前一个的输入串
: 长是n*(log ID)，最后做到步骤跟n线性，但这里输入串只需要lgN，也
: 得做N步，就nb了
avatar
R*n
65 楼
难？
相关阅读
舞夜前奏Chinese Pop singer concerts in US转了再转：熟悉歌曲的外语原唱（上）【合唱活动】当爱已成往事 with cinnamon初奔，刘德华《爱不完》Popular songs陈楚生『一个人的冬天』MV翻唱:失踪--林忆莲有人对音箱有研究吗 (转载)夜深了推荐一个王菲的天下有情人 (转载)请教（见笑）：万利达如何更新歌？谢！【分享】Vitas（维塔斯）翻唱《青藏高原》MV★天天录歌秘籍大公开★【佳片介绍】Engelbert Humperdinck in opera lessons转载一下新近 MusicPlayer 版的一些作品通俗唱法教学录像（转）090131文海春晚有声集锦 (转载)Already Deleted 王力宏【花田错】女声翻唱
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章，不代表同意其说法或描述，仅为提供更多信息，也不构成任何建议。文章信息的合法性及真实性由其作者负责，与Redian.news及其运营公司无关。欢迎投稿，如发现稿件侵权，或作者不愿在本网发表文章，请版权拥有者通知本网处理。