c*****e
发帖数: 737 | 1 敢打赌那个面试官如果没看过解法的话，搞1年也搞不出。那么用这个问题测试面试者
的意义在哪里？ |
B*******1
发帖数: 2454 | 2 一般应该想到dp那个解法吧，想不到最牛那个解法我觉得正常。 |
f*******t
发帖数: 7549 | |
S*******w
发帖数: 24236 | 4 就问你复习没复习而已
【在 c*****e 的大作中提到】
: 敢打赌那个面试官如果没看过解法的话，搞1年也搞不出。那么用这个问题测试面试者
: 的意义在哪里？
|
b***u
发帖数: 12010 | 5 会dp就能搞出这题。
【在 c*****e 的大作中提到】
: 敢打赌那个面试官如果没看过解法的话，搞1年也搞不出。那么用这个问题测试面试者
: 的意义在哪里？
|
c*****e
发帖数: 737 | 6 会dp的也不可能10分钟搞出最优解，如果没看过的话。
【在 b***u 的大作中提到】
: 会dp就能搞出这题。
|
S*******w
发帖数: 24236 | 7 这年头去公司面试就是题海战术
反正去了也是做螺丝钉 混口饭吃
【在 c*****e 的大作中提到】
: 会dp的也不可能10分钟搞出最优解，如果没看过的话。
|
c*****e
发帖数: 737 | 8 举个例子，matrix multiplication，你应该懂dp的吧。g公司面试一向追求最优解，按
理matrix multiplication的lower bound在n^2，那么你10分钟内写个出来。
【在 b***u 的大作中提到】
: 会dp就能搞出这题。
|
w**z
发帖数: 8232 | 9 DP只是在读书的学算法的时候遇见过。工作多年（只是普通码工），连听都没听人提过
。现在又依稀唤起遥远的记忆。 |
p*****2
发帖数: 21240 | 10
我读书时候也没学过。第一次见到这词就是在本版。
【在 w**z 的大作中提到】
: DP只是在读书的学算法的时候遇见过。工作多年（只是普通码工），连听都没听人提过
: 。现在又依稀唤起遥远的记忆。
|
|
|
l***i
发帖数: 1309 | 11 matrix multiplication has better than O(n^3) algorithm but nobody will ask
you about this, and this has nothing to do with DP. It was first discovered
by Strassen with O(n^log_2 7) and later improved by several people.
【在 c*****e 的大作中提到】
: 举个例子，matrix multiplication，你应该懂dp的吧。g公司面试一向追求最优解，按
: 理matrix multiplication的lower bound在n^2，那么你10分钟内写个出来。
|
d********w
发帖数: 363 | 12 什么是最优解呀，O(nlgn)?
【在 c*****e 的大作中提到】
: 会dp的也不可能10分钟搞出最优解，如果没看过的话。
|
c*****e
发帖数: 737 | 13 divide and conquer也是基本的算法技术吧？g公司一向追求最完美的解法，那么
Strassen的就显得太弱了，10分钟想个optimal的出来。
discovered
【在 l***i 的大作中提到】
: matrix multiplication has better than O(n^3) algorithm but nobody will ask
: you about this, and this has nothing to do with DP. It was first discovered
: by Strassen with O(n^log_2 7) and later improved by several people.
|
w**z
发帖数: 8232 | 14 应该说是10分钟内复述出一个你复习过的解法。你不会觉的自己比Strassen牛吧
【在 c*****e 的大作中提到】
: divide and conquer也是基本的算法技术吧？g公司一向追求最完美的解法，那么
: Strassen的就显得太弱了，10分钟想个optimal的出来。
:
: discovered
|
a********m
发帖数: 15480 | 15 解题过程比最终解法更重要。
【在 c*****e 的大作中提到】
: 举个例子，matrix multiplication，你应该懂dp的吧。g公司面试一向追求最优解，按
: 理matrix multiplication的lower bound在n^2，那么你10分钟内写个出来。
|
b******t
发帖数: 965 | 16 这个题如果只要求长度 不要求序列的话 我在网上看到个很短的code
用 C++里的set
http://comeoncodeon.wordpress.com/2009/08/12/longest-increasing
【在 c*****e 的大作中提到】
: 敢打赌那个面试官如果没看过解法的话，搞1年也搞不出。那么用这个问题测试面试者
: 的意义在哪里？
|
g*****i
发帖数: 2162 | 17 对,没听说"一向追求最完美的解法",除非个别面试官要卡你. 如果你复习过了做的很顺
利,面试官肯定不会刁难.如果你没复习过但是展示了合理的思路和逻辑,我觉得也不会
刁难的.
单这题来说,是常见题,和string相关的就那么几个问题,我面FB被问过这个,给了dp的解
法. 如果没事先看到过这题,但是对dp理解的比较好,应该也是能做出来的.
现在的码工面试和高考差不多,也算是IT公司多年经验积累的结果,虽然不是最公平但是
也没有更好的挑人方法.
【在 a********m 的大作中提到】
: 解题过程比最终解法更重要。
|
c*****e
发帖数: 737 | 18 至少我工作4年内从没用过dp。g公司的码农难道和其他公司如此不同，写代码都是dp的？
现实工作中，选择和使用合适的数据结构比较重要。
举个例子，什么时候用std::map而不是hashmap? 什么时候可以用但不用map而用array
，每次做线性查找？->当你知道你的element的size很小，比如只有5个以下，那么你可
以抛弃map啊，hash啊，直接用array线性查找。
写代码要有感觉的，dp什么的你基本不可能在工作中碰到。一般刚毕业的小朋友装b喜
欢问这些问题。 |
c*****e
发帖数: 737 | 19 dp的流行么，和acm icpc有关。因为出题的实在想不出其他的了。
【在 w**z 的大作中提到】
: DP只是在读书的学算法的时候遇见过。工作多年（只是普通码工），连听都没听人提过
: 。现在又依稀唤起遥远的记忆。
|
b***u
发帖数: 12010 | 20 matrix multiplication业界都在研究怎么把constant factor降低个0.xx，难度系数和
longest subsequence是不一样的。
longest subsequence算dp里难度中等的。你硬要说面试管一年也搞不出来是太小看人了。
g家的brain teaser才变态。签了nda就不说了。
【在 c*****e 的大作中提到】
: 举个例子，matrix multiplication，你应该懂dp的吧。g公司面试一向追求最优解，按
: 理matrix multiplication的lower bound在n^2，那么你10分钟内写个出来。
|
|
|
P***P
发帖数: 1387 | 21 n^2? 就这个水平还好意思质疑别人面试题,多学习点吧
【在 c*****e 的大作中提到】
: 举个例子，matrix multiplication，你应该懂dp的吧。g公司面试一向追求最优解，按
: 理matrix multiplication的lower bound在n^2，那么你10分钟内写个出来。
|
P***P
发帖数: 1387 | 22 正儿八经上个算法课的都应该会把, 也就algorithm design后面习题难度
【在 c*****e 的大作中提到】
: 敢打赌那个面试官如果没看过解法的话，搞1年也搞不出。那么用这个问题测试面试者
: 的意义在哪里？
|
b***u
发帖数: 12010 | 23 我还真面试时搞出这道了。之前没写过。用了不止10分钟，可还是搞出最优还和俄大叔
侃了半天self driving car。
【在 c*****e 的大作中提到】
: 会dp的也不可能10分钟搞出最优解，如果没看过的话。
|
g*********e
发帖数: 14401 | 24 你们说的DP是NLOGN的那个吗？WIKI上的？
还是N^2的？ |
b***u
发帖数: 12010 | 25 http://en.wikipedia.org/wiki/Coppersmith%E2%80%93Winograd_algor
楼主要是能用两年搞出O( n^2 )的矩阵相乘，就可以鄙视全版了。现在只能被全版鄙视。
【在 P***P 的大作中提到】
: n^2? 就这个水平还好意思质疑别人面试题,多学习点吧
|
f**********r
发帖数: 2137 | |
a********m
发帖数: 15480 | 27 赞。
【在 b***u 的大作中提到】
: 我还真面试时搞出这道了。之前没写过。用了不止10分钟，可还是搞出最优还和俄大叔
: 侃了半天self driving car。
|
y*******o
发帖数: 6632 | 28 congs,You jump to google?
【在 b***u 的大作中提到】
: 我还真面试时搞出这道了。之前没写过。用了不止10分钟，可还是搞出最优还和俄大叔
: 侃了半天self driving car。
|
b***u
发帖数: 12010 | 29 没。貌似死在中国大妈手上了。
【在 y*******o 的大作中提到】
: congs,You jump to google?
|
w****x
发帖数: 2483 | 30 给个O(n^2)的DP解就可以了, 专什么牛角尖啊, 真是!! |
|
|
H***e
发帖数: 476 | 31 n^2的我觉得还是能搞出来的
nlgn的就夸张了
【在 c*****e 的大作中提到】
: 敢打赌那个面试官如果没看过解法的话，搞1年也搞不出。那么用这个问题测试面试者
: 的意义在哪里？
|
S**********r
发帖数: 1410 | 32 这就是游戏规则，你说一群人抢着把一个足球踢到对方门里去，意义在哪里：-)
【在 c*****e 的大作中提到】
: 敢打赌那个面试官如果没看过解法的话，搞1年也搞不出。那么用这个问题测试面试者
: 的意义在哪里？
|
j********x
发帖数: 2330 | 33 。。。
【在 P***P 的大作中提到】
: n^2? 就这个水平还好意思质疑别人面试题,多学习点吧
|
l*********b
发帖数: 1541 | 34 估计人家就看你学习的能力。
你会不一定表示学习能力强，但是不会的话他不知道你到底如何。人家可挑选的人一大
把，按概率算，自然选会做的，不管你复习没复习过。 |
