l*********8
发帖数: 4642 | 1 1. 求一个字符串，只包含0-9的digit， 并且所有的四位数字的组合都是这个字符串的
sub-string.
2. 一个m*n float矩阵A，在每个格子可以向上下左右四个方向移动。 求左上角到右下
角的一条路径，使得路径上所有数字的乘积最大（路径上不能有重复的格子）。 |
j***y
发帖数: 1640 | |
v*****y
发帖数: 68 | 3 “四位数字的组合”指的是1000-9999吗？还是0000-9999？ |
l*********8
发帖数: 4642 | 4 0000-9999
【在 v*****y 的大作中提到】
: “四位数字的组合”指的是1000-9999吗？还是0000-9999？
|
k***s
发帖数: 6 | |
l*********8
发帖数: 4642 | 6 厉害。
我是跪了。
【在 k***s 的大作中提到】
: 第一题是De Bruijn sequence吧
: http://en.wikipedia.org/wiki/De_Bruijn_sequence
|
g*********e
发帖数: 14401 | 7 第二题数字可以是负数吗
【在 l*********8 的大作中提到】
: 1. 求一个字符串，只包含0-9的digit， 并且所有的四位数字的组合都是这个字符串的
: sub-string.
: 2. 一个m*n float矩阵A，在每个格子可以向上下左右四个方向移动。 求左上角到右下
: 角的一条路径，使得路径上所有数字的乘积最大（路径上不能有重复的格子）。
|
l*********8
发帖数: 4642 | 8 可以
【在 g*********e 的大作中提到】
: 第二题数字可以是负数吗
|
k***s
发帖数: 6 | 9 遇到这样的题我也得跪
敢问这是哪个大公司的题？
【在 l*********8 的大作中提到】
: 厉害。
: 我是跪了。
|
l*********8
发帖数: 4642 | 10 top company, 具体不说了
【在 k***s 的大作中提到】
: 遇到这样的题我也得跪
: 敢问这是哪个大公司的题？
|
|
|
l**********1
发帖数: 415 | 11 第一题不会
感觉第二题只能dfs不能dp，因为1）要一个路径作为答案而不是只要一个数字。2）因
为可以四个方向走，所以解的树有环
等待大牛解答 |
n********e
发帖数: 41 | |
h***y
发帖数: 43 | 13 第一题 bottom-up DP algorithm? |
A*********c
发帖数: 430 | 14 G家，第一题讨论过。
【在 l*********8 的大作中提到】
: 1. 求一个字符串，只包含0-9的digit， 并且所有的四位数字的组合都是这个字符串的
: sub-string.
: 2. 一个m*n float矩阵A，在每个格子可以向上下左右四个方向移动。 求左上角到右下
: 角的一条路径，使得路径上所有数字的乘积最大（路径上不能有重复的格子）。
|
A*********c
发帖数: 430 | 15 第二题感觉像是一维max product的二维版本配上leetcode的path sum。
【在 l*********8 的大作中提到】
: 1. 求一个字符串，只包含0-9的digit， 并且所有的四位数字的组合都是这个字符串的
: sub-string.
: 2. 一个m*n float矩阵A，在每个格子可以向上下左右四个方向移动。 求左上角到右下
: 角的一条路径，使得路径上所有数字的乘积最大（路径上不能有重复的格子）。
|
l***n
发帖数: 89 | 16 哪里有讨论贴？能发一个么？不会做。
【在 A*********c 的大作中提到】
: G家，第一题讨论过。
|
N*****Z
发帖数: 70 | 17 第一题这个行不？
"0123456789012345678901234567890123456789"
【在 l*********8 的大作中提到】
: 1. 求一个字符串，只包含0-9的digit， 并且所有的四位数字的组合都是这个字符串的
: sub-string.
: 2. 一个m*n float矩阵A，在每个格子可以向上下左右四个方向移动。 求左上角到右下
: 角的一条路径，使得路径上所有数字的乘积最大（路径上不能有重复的格子）。
|
l*********8
发帖数: 4642 | 18 不行，很多组合都没有cover
【在 N*****Z 的大作中提到】
: 第一题这个行不？
: "0123456789012345678901234567890123456789"
|
U***A
发帖数: 849 | |
l*********8
发帖数: 4642 | 20 0134
【在 U***A 的大作中提到】
: 还有那些组合没有cover?
|
|
|
n********e
发帖数: 41 | 21 没要求最短的。把所有数都加进String... 长度也就 10000*4 个字符。。。 |
b**q
发帖数: 247 | 22 第一题少写条件了吧 否则只要把所有四位数连起来就好了
看楼下给你的de bruijn sequence还差不多 |
l*********8
发帖数: 4642 | 23 当然可以把所有四位数连起来。 但在面试官那里也得不了什么好分数
【在 b**q 的大作中提到】
: 第一题少写条件了吧 否则只要把所有四位数连起来就好了
: 看楼下给你的de bruijn sequence还差不多
|
b**q
发帖数: 247 | 24 o 那倒是
习惯了题目给出限制条件了
【在 l*********8 的大作中提到】
: 当然可以把所有四位数连起来。 但在面试官那里也得不了什么好分数
|
f******n
发帖数: 279 | |
g*********e
发帖数: 14401 | 26
感觉第二个问题是NP，类似于longest simple path. 将edge 取对数就是乘积
http://en.wikipedia.org/wiki/Longest_path_problem
【在 l*********8 的大作中提到】
: 1. 求一个字符串，只包含0-9的digit， 并且所有的四位数字的组合都是这个字符串的
: sub-string.
: 2. 一个m*n float矩阵A，在每个格子可以向上下左右四个方向移动。 求左上角到右下
: 角的一条路径，使得路径上所有数字的乘积最大（路径上不能有重复的格子）。
|
g**********y
发帖数: 14569 | 27 对第二个题，你confirm了所有的条件：
－四个方向都可以移动？
－数字是float？可以是0？
如果这是所有的条件，
1. 0出现在路径上无意义，除了特殊情况
2. 绝对值<1的数出现在路径上无意义
3. 找到一条路径把剩下的数的数一笔画出来
4. 如果乘积为负，考虑去掉一个最小负数；或者乘以最大的负数（绝对值<1)
总之，很多分叉情况，写起来很麻烦。我感觉：这有可能不是他想要问的题。 |
J***o
发帖数: 553 | 28 <1的数并不是没有意义的，因为可能要到达一些比较大的数必须经过<1的数，cost<
benefit
看题没有附加限制的话应该是NP-hard吧
【在 g**********y 的大作中提到】
: 对第二个题，你confirm了所有的条件：
: －四个方向都可以移动？
: －数字是float？可以是0？
: 如果这是所有的条件，
: 1. 0出现在路径上无意义，除了特殊情况
: 2. 绝对值<1的数出现在路径上无意义
: 3. 找到一条路径把剩下的数的数一笔画出来
: 4. 如果乘积为负，考虑去掉一个最小负数；或者乘以最大的负数（绝对值<1)
: 总之，很多分叉情况，写起来很麻烦。我感觉：这有可能不是他想要问的题。
|
g**********y
发帖数: 14569 | 29 是的，如果这样，就更可能题目不是面试官想问的。有个朋友说的很有道理：遇到这种
情况，一定要跟面试官核实，如果你感觉题目太难，更可能是理解出了偏差。也可能是
：面试官当时没想太清楚，你问他时，他觉得条件放松一点也可以用原来的思路解，殊
不知一放松可能就放成NP－hard了。
【在 J***o 的大作中提到】
: <1的数并不是没有意义的，因为可能要到达一些比较大的数必须经过<1的数，cost<
: benefit
: 看题没有附加限制的话应该是NP-hard吧
|
l*********8
发帖数: 4642 | 30 谢谢火鸡哥的建议。 的确我还需要加强沟通能力。
这道题我当时做不出来，面试官倒是换了道简单些的题目。 但不知道feedback怎么写
了。
我这次已经挂了。 只有move on投其他公司了。
【在 g**********y 的大作中提到】
: 是的，如果这样，就更可能题目不是面试官想问的。有个朋友说的很有道理：遇到这种
: 情况，一定要跟面试官核实，如果你感觉题目太难，更可能是理解出了偏差。也可能是
: ：面试官当时没想太清楚，你问他时，他觉得条件放松一点也可以用原来的思路解，殊
: 不知一放松可能就放成NP－hard了。
|
|
|
g*********e
发帖数: 14401 | 31
google的面试里 问np复杂度的问题也是有的。
有些interviewer其实自己也不知道题目怎么做，就拿来问
【在 g**********y 的大作中提到】
: 是的，如果这样，就更可能题目不是面试官想问的。有个朋友说的很有道理：遇到这种
: 情况，一定要跟面试官核实，如果你感觉题目太难，更可能是理解出了偏差。也可能是
: ：面试官当时没想太清楚，你问他时，他觉得条件放松一点也可以用原来的思路解，殊
: 不知一放松可能就放成NP－hard了。
|
