t*********2
发帖数: 32 | 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很难过，我该怎么劝他呢？ |
r****o
发帖数: 1950 | 2 先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很难过，我该怎么劝他呢？
|
d*******8
发帖数: 785 | 3 奇怪了，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很难过，我该怎么劝他呢？
|
d*******8
发帖数: 785 | 4 看面额组合的。
比如给你面额组合是24，10. 进来个数字 30，贪婪就挂了。
世过很多bay area的公司，就没见
【在 r****o 的大作中提到】
: 先cft一下,
: 硬币问题可以用Greedy算法吧。
:
: 然还要当场coding，并且一个字母一个字母的念给他听。没想到Google会在电话里问这
: 么难的题目。LG想出了一种recursive的解法，但是面试官不满意，一定要动态规划的
: 解法。LG后来没有code出
: 才会用到的么？实际工作中真的需要么？LG以前也面世过很多bay area的公司，就没见
: 过这么难的面试题。LG很难过，我该怎么劝他呢？
|
r****o
发帖数: 1950 | 5 贪婪先试最大的，不行再试小的嘛。
这题是不是用贪婪效率更高?
【在 d*******8 的大作中提到】
: 看面额组合的。
: 比如给你面额组合是24，10. 进来个数字 30，贪婪就挂了。
:
: 世过很多bay area的公司，就没见
|
y**i
发帖数: 1112 | 6 问一下，这个问题用贪婪是不是用回溯的方法实现？
【在 r****o 的大作中提到】
: 贪婪先试最大的，不行再试小的嘛。
: 这题是不是用贪婪效率更高?
|
d*******8
发帖数: 785 | 7 这样的话，每次要回溯上一个面值的一个，也对哦。
就是写起来比较麻烦..
【在 r****o 的大作中提到】
: 贪婪先试最大的，不行再试小的嘛。
: 这题是不是用贪婪效率更高?
|
c*********n
发帖数: 1057 | 8 greedy有的时候不行的吧
比如硬币：24 10 1
要求30
那最优是 10 10 10
greedy的话是24 1 1 1 1 1 1
【在 r****o 的大作中提到】
: 贪婪先试最大的，不行再试小的嘛。
: 这题是不是用贪婪效率更高?
|
w*****e
发帖数: 197 | 9 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很难过，我该怎么劝他呢？
|
y**i
发帖数: 1112 | 10 好像greedy有时候确实不是最优的
【在 c*********n 的大作中提到】
: greedy有的时候不行的吧
: 比如硬币：24 10 1
: 要求30
: 那最优是 10 10 10
: greedy的话是24 1 1 1 1 1 1
|
|
|
g*******y
发帖数: 1930 | 11 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很难过，我该怎么劝他呢？
|
a***9
发帖数: 364 | 12 的确不能永远用贪婪，试着抛砖引玉一个可以用贪婪的硬币面额情况：
首先注意到为了能表示任意整数，这些硬币面额的最低值必须是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
|
l******o
发帖数: 144 | 13 因为这道题本身就是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以前
|
d*******8
发帖数: 785 | 14 Nod，当时我就想Greedy是不行的嘛， 现在反而糊涂了。。
【在 c*********n 的大作中提到】
: greedy有的时候不行的吧
: 比如硬币：24 10 1
: 要求30
: 那最优是 10 10 10
: greedy的话是24 1 1 1 1 1 1
|
a***9
发帖数: 364 | 15 NP-hard? 难道你认为动归解这题的复杂度是NP-hard级别的吗
而且如果条件合适，可以用greedy的话，基本就是linear的，除去预处理。
【在 l******o 的大作中提到】
: 因为这道题本身就是NP-Hard的。所以没答出来不用难过。
: 第一句话是真的。第二句话是假的。
:
: DP好好学习一两天多体会下思想，会发现其实这个题不难的
: 我以前觉得这题难是因为总觉得DP的性能还不够好...
: 然还要当场
: coding，并且一个字母一个字母的念给他听。没想到Google会在电话里问这么难的题目
: 。LG想出了一种
: recursive的解法，但是面试官不满意，一定要动态规划的解法。LG后来没有code出来
: 。过几天Google来
|
l******o
发帖数: 144 | 16 是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的，除去预处理。
|
g*******y
发帖数: 1930 | 17 对
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的，除去预处理。
|
l******o
发帖数: 144 | 18 嗯，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搜索解或者剪枝的回
: 溯可能平均性能
: 好些。
|
a***9
发帖数: 364 | 19 有哪里有讲这题么？
为什么它的复杂度是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搜索解或者剪枝的回
: 溯可能平均性能
: 好些。
|
a***9
发帖数: 364 | 20 为啥你们都说这题是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的，除去预处理。
|
|
|
m*****f
发帖数: 1243 | 21 DP 解决硬币面值问题是很基础的DP问题啊， 如果你老公有复习DP的话
还是要再复习的多一些把 |
h**6
发帖数: 4160 | 22
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
|
R**e
发帖数: 274 | 23 有谁可以给个这道题的链接吗？
谢谢！
然还要当场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很难过，我该怎么劝他呢？
|
k***e
发帖数: 556 | 24 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很难过，我该怎么劝他呢？
|
r****o
发帖数: 1950 | 25 sorry, 误导你了，呵呵。
【在 d*******8 的大作中提到】
: Nod，当时我就想Greedy是不行的嘛， 现在反而糊涂了。。
|
C*********h
发帖数: 74 | 26 1.greedy 不是最优的。
2.这题是CS本科生的DP家庭作业。很基础。
3.你LG准备的不好，但是被GOOGLE锯掉很正常。 |
x******3
发帖数: 245 | 27 CLRS 2nd edition
习题16-1有详细讨论coin changing问题 |
p****j
发帖数: 4762 | 28 你劝他，amazon等着他呢，干嘛非要microsoft |
l******o
发帖数: 144 | 29 因为表示N只需要log(N)bit,所以输入的size不是N而是O(klogN)
所以O(kN)的时间复杂度是exponential的.
为啥你们都说这题是exponential的？就算google问一道NP-hard的问题
还是有点奇怪。
你是不是把这题看成其他题目了？ 也可能是我看错了
【在 a***9 的大作中提到】
: 为啥你们都说这题是exponential的？就算google问一道NP-hard的问题
: 还是有点奇怪。
: 你是不是把这题看成其他题目了？ 也可能是我看错了
|
m****u
发帖数: 3915 | 30 这题是标准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很难过，我该怎么劝他呢？
|
|
|
w****l
发帖数: 88 | 31 cmft.
没必要难过了，运气不太好，想要当场完整写出来，确实不是很容易..... |
s********a
发帖数: 1447 | 32 汗一个
CLRS是什么书？
【在 x******3 的大作中提到】
: CLRS 2nd edition
: 习题16-1有详细讨论coin changing问题
|
r***w
发帖数: 142 | 33 这题目是google面试里dynamic programming典型的试题。就在google推荐看的材料里
面的例题。你老公准备不充分。 |
a***9
发帖数: 364 | 34 thanks!
【在 l******o 的大作中提到】
: 因为表示N只需要log(N)bit,所以输入的size不是N而是O(klogN)
: 所以O(kN)的时间复杂度是exponential的.
:
: 为啥你们都说这题是exponential的？就算google问一道NP-hard的问题
: 还是有点奇怪。
: 你是不是把这题看成其他题目了？ 也可能是我看错了
|
a***9
发帖数: 364 | 35 嗯，我又绕了一下，是exp的，但这是因为N，不是因为k吧
【在 h**6 的大作中提到】
:
: DP解法需要O(Nk)的时间和空间，这是伪多项式问题，因为k不是输入参数的一个，而是
: 输入参数a1, a2, ..., ak的个数。
|
t********5
发帖数: 274 | 36 好像之前看到版上有人讨论过这个题目
还有人写了一段代码呢 |
r****o
发帖数: 1950 | 37 我还是没弄明白，为啥这里N的input size看成比特数，所以复杂度是exponential，那
为啥别的题目的N就不用看成比特数呢？
【在 a***9 的大作中提到】
: 嗯，我又绕了一下，是exp的，但这是因为N，不是因为k吧
|
a***9
发帖数: 364 | 38 直观上我是这么理解的:别的题目中，比如给n个ID，让找一个target的，
那么就是扫一遍就行，我们一看就是linear的，那是因为跟每个ID大小
没关系，只跟有多少个ID有关系。
但这题，复杂度是跟给的N的大小有关系。
所以，定义复杂度，是根据输入串长度的bits数来的，前一个的输入串
长是n*(log ID)，最后做到步骤跟n线性，但这里输入串只需要lgN，也
得做N步，就nb了
【在 r****o 的大作中提到】
: 我还是没弄明白，为啥这里N的input size看成比特数，所以复杂度是exponential，那
: 为啥别的题目的N就不用看成比特数呢？
|
D***h
发帖数: 183 | 39 因为多项式时间的complexity是相对输入规模而言的,只需要lg n bit就行,但是这里得
到的是关于输入的具体值的多项式时间,相比输入规模,这个是输入规模的指数级.
http://en.wikipedia.org/wiki/Pseudo-polynomial_time
【在 r****o 的大作中提到】
: 我还是没弄明白，为啥这里N的input size看成比特数，所以复杂度是exponential，那
: 为啥别的题目的N就不用看成比特数呢？
|
t******t
发帖数: 2404 | 40 it depends on who is the interviewer. some new-cop is tough |
|
|
e****e
发帖数: 975 | 41 DP是iterative，不是recursive
世过很多bay area的公司，就没见
【在 d*******8 的大作中提到】
: 奇怪了，DP难道不就是Recursive吗？
: 这道题目一个小公司也留给我作业的，我写了DP发过去，那边一开始说我程序写错了。
: 我回信说程序没错我还有Testing例子的，然后那边又说我DP不是最优解..
: 我在想，妈呀，难道他还用贪婪做嘛，就没争论Move on了。
:
: 然还要当场coding，并且一个字母一个字母的念给他听。没想到Google会在电话里问这
: 么难的题目。LG想出了一种recursive的解法，但是面试官不满意，一定要动态规划的
: 解法。LG后来没有code出
: 才会用到的么？实际工作中真的需要么？LG以前也面世过很多bay area的公司，就没见
: 过这么难的面试题。LG很难过，我该怎么劝他呢？
|
r****o
发帖数: 1950 | 42 多谢，可不可以这么理解:
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了
|
R********n
发帖数: 3601 | |
