s*****i
发帖数: 32 | 1 4位的密码，遍历完所有0000-9999的可能性后，锁就能打开。
把所有的可能密码连接在一起成为总长度为4*10000=40000的string。这个string的某
连续四位肯定能够能解开锁。
上面的string不是唯一的。比如实际密码是2345，string的某5位是12345，1234是一个
组合，2345是另一个组合。也就是说他们共享了一些数字。导致总长度降低。
现在求一个最短的string，其中某连续4位一定是可以解开锁的密码。 |
B*******1
发帖数: 2454 | 2 这是我onsite的第一道题 一年多前 我遇到的时候还从没有见过
【在 s*****i 的大作中提到】
: 4位的密码，遍历完所有0000-9999的可能性后，锁就能打开。
: 把所有的可能密码连接在一起成为总长度为4*10000=40000的string。这个string的某
: 连续四位肯定能够能解开锁。
: 上面的string不是唯一的。比如实际密码是2345，string的某5位是12345，1234是一个
: 组合，2345是另一个组合。也就是说他们共享了一些数字。导致总长度降低。
: 现在求一个最短的string，其中某连续4位一定是可以解开锁的密码。
|
s*****i
发帖数: 32 | 3 你怎么做的？通过了面试，说明做的还不错。
【在 B*******1 的大作中提到】
: 这是我onsite的第一道题 一年多前 我遇到的时候还从没有见过
|
f*****e
发帖数: 2992 | 4 deBrujin cycle.
【在 s*****i 的大作中提到】
: 你怎么做的？通过了面试，说明做的还不错。
|
P****2
发帖数: 197 | |
s*****i
发帖数: 32 | 6 TSP是NP complete吧。这个有有效的算法吗？
【在 P****2 的大作中提到】
: 最短母串，可以有向图TSP
|
s*****i
发帖数: 32 | 7 正在searching and reading.
【在 f*****e 的大作中提到】
: deBrujin cycle.
|
s*****i
发帖数: 32 | 8 怎么证明 Each B(k, n) has length k^n.
【在 f*****e 的大作中提到】
: deBrujin cycle.
|
b**********r
发帖数: 91 | 9 gray code
【在 s*****i 的大作中提到】
: 4位的密码，遍历完所有0000-9999的可能性后，锁就能打开。
: 把所有的可能密码连接在一起成为总长度为4*10000=40000的string。这个string的某
: 连续四位肯定能够能解开锁。
: 上面的string不是唯一的。比如实际密码是2345，string的某5位是12345，1234是一个
: 组合，2345是另一个组合。也就是说他们共享了一些数字。导致总长度降低。
: 现在求一个最短的string，其中某连续4位一定是可以解开锁的密码。
|
j*********g
发帖数: 36 | 10 This is not gray code. No need to formulate it as TSP. Also, debrujin
graph only gives you a problem formulation.
You can solve by finding an Eulerian tour. Each node is a 3-digit number eg
100, and two nodes 100 and 001 are adjacent if they can be combined into
1001. Now every node has equal in-degree and out-degree, thus an Eulerien
tour exists and can be found using the standard algorithm. |
|
|
P****2
发帖数: 197 | 11 啥算有效。。DP的n^2 * 2^n算不
【在 s*****i 的大作中提到】
: TSP是NP complete吧。这个有有效的算法吗？
|
P****2
发帖数: 197 | 12 没看懂为啥是欧拉，不是哈密顿回路么，每个NODE是四位数，边是重复的字母
1001 => 1002, 3
1832 => 2321, 2
不应该是找条回路，穿过所有NODE，MAX PATH WEIGHT，就是TSP啊
eg
【在 j*********g 的大作中提到】
: This is not gray code. No need to formulate it as TSP. Also, debrujin
: graph only gives you a problem formulation.
: You can solve by finding an Eulerian tour. Each node is a 3-digit number eg
: 100, and two nodes 100 and 001 are adjacent if they can be combined into
: 1001. Now every node has equal in-degree and out-degree, thus an Eulerien
: tour exists and can be found using the standard algorithm.
|
b*********h
发帖数: 103 | |
j*********g
发帖数: 36 | 14 Eulerian tour没有走多。看了我写的方法？关键是让每个edge是四位数，而不是node |
P****2
发帖数: 197 | 15 这写错了，应该是
1100=>1002,3 (选这个路径相当于合并成11002)
1823=>2321,2 （选这个路径相当于合并成182321)
【在 P****2 的大作中提到】
: 没看懂为啥是欧拉，不是哈密顿回路么，每个NODE是四位数，边是重复的字母
: 1001 => 1002, 3
: 1832 => 2321, 2
: 不应该是找条回路，穿过所有NODE，MAX PATH WEIGHT，就是TSP啊
:
: eg
|
M*******a
发帖数: 1633 | 16 Best case 10003 digit enough
可不可以一个一个digit试过去and back tracking如果不行 |
M*******a
发帖数: 1633 | 17 G家题目难道都要你事先知道什么deBrujin cycle才做得出来？
这里多少人认为自己事先不知道deBrujin cycle能当场figure out出来？ |
M*******a
发帖数: 1633 | 18 我老编了个程序验证过了，基本只要一位一位算过去，如果不行就backtracking就行了
，其实需要backtracking的情况很少。
基本只要1003个字符就可以了，而且首尾可以衔接，也就是说一个1000的环就可以了 |
j*********g
发帖数: 36 | 19
对的，你的backtrack work就是因为Eulerian tour存在
【在 M*******a 的大作中提到】
: 我老编了个程序验证过了，基本只要一位一位算过去，如果不行就backtracking就行了
: ，其实需要backtracking的情况很少。
: 基本只要1003个字符就可以了，而且首尾可以衔接，也就是说一个1000的环就可以了
|
M*******a
发帖数: 1633 | 20 我觉得这个题目搞成图的东西来作只有麻烦，30分钟内做出来需要。
还是我的简单，基本几乎线形，什么recursion都没有。
【在 j*********g 的大作中提到】
:
: 对的，你的backtrack work就是因为Eulerian tour存在
|
|
|
X****y
发帖数: 33 | 21 我一年前在苏黎世的G也遇到过。 欧拉回路。
【在 s*****i 的大作中提到】
: 4位的密码，遍历完所有0000-9999的可能性后，锁就能打开。
: 把所有的可能密码连接在一起成为总长度为4*10000=40000的string。这个string的某
: 连续四位肯定能够能解开锁。
: 上面的string不是唯一的。比如实际密码是2345，string的某5位是12345，1234是一个
: 组合，2345是另一个组合。也就是说他们共享了一些数字。导致总长度降低。
: 现在求一个最短的string，其中某连续4位一定是可以解开锁的密码。
|
i******t
发帖数: 22541 | 22 他妈的 这么难的题 之前没研究过这个什么欧拉回路的 没法玩啊 |
z****e
发帖数: 54598 | |
f********x
发帖数: 2086 | 24
求细节
怎么一个个的试过去？
每次加一个digit怎么判断是否需要back tracking？
【在 M*******a 的大作中提到】
: Best case 10003 digit enough
: 可不可以一个一个digit试过去and back tracking如果不行
|
