s*i
2 楼
4位的密码，遍历完所有0000-9999的可能性后，锁就能打开。
把所有的可能密码连接在一起成为总长度为4*10000=40000的string。这个string的某
连续四位肯定能够能解开锁。
上面的string不是唯一的。比如实际密码是2345，string的某5位是12345，1234是一个
组合，2345是另一个组合。也就是说他们共享了一些数字。导致总长度降低。
现在求一个最短的string，其中某连续4位一定是可以解开锁的密码。
把所有的可能密码连接在一起成为总长度为4*10000=40000的string。这个string的某
连续四位肯定能够能解开锁。
上面的string不是唯一的。比如实际密码是2345，string的某5位是12345，1234是一个
组合，2345是另一个组合。也就是说他们共享了一些数字。导致总长度降低。
现在求一个最短的string，其中某连续4位一定是可以解开锁的密码。
r*z
3 楼
谁欺负你了
【在 u*********k 的大作中提到】
: 很不开心
【在 u*********k 的大作中提到】
: 很不开心
B*1
4 楼
这是我onsite的第一道题 一年多前 我遇到的时候还从没有见过
【在 s*****i 的大作中提到】
: 4位的密码，遍历完所有0000-9999的可能性后，锁就能打开。
: 把所有的可能密码连接在一起成为总长度为4*10000=40000的string。这个string的某
: 连续四位肯定能够能解开锁。
: 上面的string不是唯一的。比如实际密码是2345，string的某5位是12345，1234是一个
: 组合，2345是另一个组合。也就是说他们共享了一些数字。导致总长度降低。
: 现在求一个最短的string，其中某连续4位一定是可以解开锁的密码。
【在 s*****i 的大作中提到】
: 4位的密码，遍历完所有0000-9999的可能性后，锁就能打开。
: 把所有的可能密码连接在一起成为总长度为4*10000=40000的string。这个string的某
: 连续四位肯定能够能解开锁。
: 上面的string不是唯一的。比如实际密码是2345，string的某5位是12345，1234是一个
: 组合，2345是另一个组合。也就是说他们共享了一些数字。导致总长度降低。
: 现在求一个最短的string，其中某连续4位一定是可以解开锁的密码。
u*k
5 楼
想发泄发泄
s*i
6 楼
你怎么做的？通过了面试，说明做的还不错。
【在 B*******1 的大作中提到】
: 这是我onsite的第一道题 一年多前 我遇到的时候还从没有见过
【在 B*******1 的大作中提到】
: 这是我onsite的第一道题 一年多前 我遇到的时候还从没有见过
i*4
7 楼
patpat
f*e
8 楼
deBrujin cycle.
【在 s*****i 的大作中提到】
: 你怎么做的？通过了面试，说明做的还不错。
【在 s*****i 的大作中提到】
: 你怎么做的？通过了面试，说明做的还不错。
u*k
9 楼
一个朋友出家了
可惜我有家有口，不然我也出家了
可惜我有家有口，不然我也出家了
P*2
10 楼
最短母串，可以有向图TSP
L*1
11 楼
断背了
s*i
12 楼
TSP是NP complete吧。这个有有效的算法吗？
【在 P****2 的大作中提到】
: 最短母串，可以有向图TSP
【在 P****2 的大作中提到】
: 最短母串，可以有向图TSP
t*t
13 楼
这生活环境真不一样啊。。。
s*i
14 楼
正在searching and reading.
【在 f*****e 的大作中提到】
: deBrujin cycle.
【在 f*****e 的大作中提到】
: deBrujin cycle.
u*k
15 楼
人生就是一笔交易
你不去交易别人
就是被别人交易
不如如佛门忘却所有牵虑
你不去交易别人
就是被别人交易
不如如佛门忘却所有牵虑
s*i
16 楼
怎么证明 Each B(k, n) has length k^n.
【在 f*****e 的大作中提到】
: deBrujin cycle.
【在 f*****e 的大作中提到】
: deBrujin cycle.
b*r
17 楼
gray code
【在 s*****i 的大作中提到】
: 4位的密码，遍历完所有0000-9999的可能性后，锁就能打开。
: 把所有的可能密码连接在一起成为总长度为4*10000=40000的string。这个string的某
: 连续四位肯定能够能解开锁。
: 上面的string不是唯一的。比如实际密码是2345，string的某5位是12345，1234是一个
: 组合，2345是另一个组合。也就是说他们共享了一些数字。导致总长度降低。
: 现在求一个最短的string，其中某连续4位一定是可以解开锁的密码。
【在 s*****i 的大作中提到】
: 4位的密码，遍历完所有0000-9999的可能性后，锁就能打开。
: 把所有的可能密码连接在一起成为总长度为4*10000=40000的string。这个string的某
: 连续四位肯定能够能解开锁。
: 上面的string不是唯一的。比如实际密码是2345，string的某5位是12345，1234是一个
: 组合，2345是另一个组合。也就是说他们共享了一些数字。导致总长度降低。
: 现在求一个最短的string，其中某连续4位一定是可以解开锁的密码。
j*g
18 楼
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.
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
19 楼
啥算有效。。DP的n^2 * 2^n算不
【在 s*****i 的大作中提到】
: TSP是NP complete吧。这个有有效的算法吗？
【在 s*****i 的大作中提到】
: TSP是NP complete吧。这个有有效的算法吗？
P*2
20 楼
没看懂为啥是欧拉，不是哈密顿回路么，每个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.
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
21 楼
TSP 无解，Euler tour 走多了
j*g
22 楼
Eulerian tour没有走多。看了我写的方法？关键是让每个edge是四位数，而不是node
P*2
23 楼
这写错了，应该是
1100=>1002,3 (选这个路径相当于合并成11002)
1823=>2321,2 （选这个路径相当于合并成182321)
【在 P****2 的大作中提到】
: 没看懂为啥是欧拉，不是哈密顿回路么，每个NODE是四位数，边是重复的字母
: 1001 => 1002, 3
: 1832 => 2321, 2
: 不应该是找条回路，穿过所有NODE，MAX PATH WEIGHT，就是TSP啊
:
: eg
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
24 楼
Best case 10003 digit enough
可不可以一个一个digit试过去and back tracking如果不行
可不可以一个一个digit试过去and back tracking如果不行
M*a
25 楼
G家题目难道都要你事先知道什么deBrujin cycle才做得出来？
这里多少人认为自己事先不知道deBrujin cycle能当场figure out出来？
这里多少人认为自己事先不知道deBrujin cycle能当场figure out出来？
M*a
26 楼
我老编了个程序验证过了，基本只要一位一位算过去，如果不行就backtracking就行了
，其实需要backtracking的情况很少。
基本只要1003个字符就可以了，而且首尾可以衔接，也就是说一个1000的环就可以了
，其实需要backtracking的情况很少。
基本只要1003个字符就可以了，而且首尾可以衔接，也就是说一个1000的环就可以了
j*g
27 楼
对的，你的backtrack work就是因为Eulerian tour存在
【在 M*******a 的大作中提到】
: 我老编了个程序验证过了，基本只要一位一位算过去，如果不行就backtracking就行了
: ，其实需要backtracking的情况很少。
: 基本只要1003个字符就可以了，而且首尾可以衔接，也就是说一个1000的环就可以了
M*a
28 楼
我觉得这个题目搞成图的东西来作只有麻烦，30分钟内做出来需要。
还是我的简单，基本几乎线形，什么recursion都没有。
【在 j*********g 的大作中提到】
:
: 对的，你的backtrack work就是因为Eulerian tour存在
还是我的简单，基本几乎线形，什么recursion都没有。
【在 j*********g 的大作中提到】
:
: 对的，你的backtrack work就是因为Eulerian tour存在
X*y
29 楼
我一年前在苏黎世的G也遇到过。 欧拉回路。
【在 s*****i 的大作中提到】
: 4位的密码，遍历完所有0000-9999的可能性后，锁就能打开。
: 把所有的可能密码连接在一起成为总长度为4*10000=40000的string。这个string的某
: 连续四位肯定能够能解开锁。
: 上面的string不是唯一的。比如实际密码是2345，string的某5位是12345，1234是一个
: 组合，2345是另一个组合。也就是说他们共享了一些数字。导致总长度降低。
: 现在求一个最短的string，其中某连续4位一定是可以解开锁的密码。
【在 s*****i 的大作中提到】
: 4位的密码，遍历完所有0000-9999的可能性后，锁就能打开。
: 把所有的可能密码连接在一起成为总长度为4*10000=40000的string。这个string的某
: 连续四位肯定能够能解开锁。
: 上面的string不是唯一的。比如实际密码是2345，string的某5位是12345，1234是一个
: 组合，2345是另一个组合。也就是说他们共享了一些数字。导致总长度降低。
: 现在求一个最短的string，其中某连续4位一定是可以解开锁的密码。
i*t
30 楼
他妈的 这么难的题 之前没研究过这个什么欧拉回路的 没法玩啊
z*e
31 楼
图论的题总是最难
f*x
32 楼
求细节
怎么一个个的试过去？
每次加一个digit怎么判断是否需要back tracking？
【在 M*******a 的大作中提到】
: Best case 10003 digit enough
: 可不可以一个一个digit试过去and back tracking如果不行
相关阅读
CPT工作期间要回国出差2周大家公司派回中国工作3个月什么的都是什么公司啊？人生第一次的phone interview需要准备多长时间Google onsite fail 掉后多久可以再申请呢？array of pointers to functions搬家公司微软的背景调查有人面试过了fund accountant职位吗?interview experience and ask for blessOPT EAD card 可以打两份工么？新工作offer的问题 (转载)只有面试，没有下文大家看看我这情况能不能办H1-b跟以前老板要工作推荐的邮件怎么写下个礼拜人生第一个onsite，求bless并附部分phone interviewH1B approved急问个改简历应对background check的问题。what is the website of collections of interview questions?bloomberg online Test问道题