Google面经题密码箱问题解法求问

不是很明白题意，如果说是一个4位的行李箱要破解密码的话，每次动一位的解法和debruijn序列不一致啊
如果答案是debruijn序列的话，说明题意是一个类似于sliding window的输入框，前面的数字会自动被挤出去然后后面键入的数字可以是0-9中的任意一个。

所以题里到底说的是怎样的密码锁


是不是跟这道题一样的
http://www.careercup.com/question?id=5126565916573696

dietpepsi 发表于 2016-1-24 17:01
不是很明白题意，如果说是一个4位的行李箱要破解密码的话，每次动一位的解法和debruijn序列不一致啊
如果 ...

我想楼主（@神罗天征）问的这道题应该是“sliding window”的那种情况。否则，他说的“包含所有的4位数序列，让这个序列尽可能短”这句话就没有意义了。但是，楼上@skye_luobopi提到的那道3位密码锁题则是另外一种情况。

stellari 发表于 2016-1-24 19:12
我想楼主（@神罗天征）问的这道题应该是“sliding window”的那种情况。否则，他说的“包含所有的4位数序 ...

妥~，那我就明白了~
所以那这题就是在得在一个3位deBruijin图上找一个欧拉回路。每一个点有10个出度10个入度，一共1000个vertices和10000条edge。 不用Lyndon words的知识应该也可以构造出来。效率肯定比最优解低，但应该比Brute Force DFS快。

dietpepsi 发表于 2016-1-25 08:03
妥~，那我就明白了~
所以那这题就是在得在一个3位deBruijin图上找一个欧拉回路。每一个点有10个出度10个 ...

我之前贴的那段代码其实本质上就是在4维de Bruijn图上找Hamilton回路，和3维de Bruijn上的欧拉回路是一个意思。但是，这是在我已知de Bruijn是Hamiltonian的情况下写出的代码。如果是面试的时候，假设我之前从没有听说过de Bruijn，如何快速向面试官说明de Bruijn图是Hamiltonian或者Eulerian呢？

stellari 发表于 2016-1-25 09:20
我之前贴的那段代码其实本质上就是在4维de Bruijn图上找Hamilton回路，和3维de Bruijn上的欧拉回路是一个 ...

找欧拉回路有非常简单的Hierholzer算法，代码就这几行。我跟deBruijn对比过，是正确的。这里面为了和deBruijn答案相近我把结果reverse了，不reverse肯定也是有效答案。不过这个写法计算k = 10 n = 4会出现stackoverflow. 需要设置-Xss2m或以上。

1. public class EulerSolution {
   
2.     int n, k, v;
   
3.     boolean[][] visited;
   
4.     StringBuilder sequence;
   
5. 
   
6.     public String crackSequence(int k, int n) {
   
7.         this.n = n;
   
8.         this.k = k;
   
9.         v = (int)Math.pow(k, n - 1); // vertices are n-1 bit radix k number.
   
10.         visited = new boolean[v][k]; // edge list
    
11.         sequence = new StringBuilder();
    
12.         dfs(0);
    
13.         return sequence.reverse().toString();
    
14.     }
    
15. 
    
16.     private void dfs(int u) {
    
17.         for (int i = 0; i < k; ++i) {
    
18.             if (!visited[u][i]) {
    
19.                 visited[u][i] = true;
    
20.                 dfs((u * k + i) % v);
    
21.                 sequence.append(i);
    
22.             }
    
23.         }
    
24.     }
    
25. }

复制代码

我觉得这道题在题意明确的情况下，把所有状态看成点，状态之间的转移看成边是比较自然的。
这样就有两种看法，一种就是把4位看成状态，一种就是把3位看成状态。
把4位看成状态的图上面找Hamilton回路，很显然是本题的答案，因为访问了每一个节点一次且只有一次。
把3位看成状态的图上面找欧拉回路可能需要给面试官解释一下。但我觉得还是比较好解释的。
因为每一条边其实代表了一种4位的状态，于是就很好解释了。
那么上面的DFS找欧拉回路的算法就是相当简单有效的解法了。在删除边和查找下一个没有访问的边的复杂度是O(1)的情况下这个算法的复杂度是O(E)的，也就是O(k^n)的，de Buijin构造算法不会比这个复杂度更好。
我这个实现没有用LinkedList或者Hash来保存边的信息，所以每次都是循环所有可能的边，也就是O(k)查找边，所以总的复杂度是O(k^(n+1))。
考虑到
k = 10 n = 4
我觉得没啥问题。

证明这个图是欧拉的非常容易，因为有向图，每一个节点的入度和出度都相等，必然是欧拉图。

这个写法更好，复杂度完全是O(E)了，不过对(10,4)还是会stackoverflow。设置-Xss2m或以上就可以，貌似不是啥大问题。

1. public class EulerSolution {
   
2.     int n, k, v;
   
3.     int[] edge;
   
4.     StringBuilder sequence;
   
5. 
   
6.     public String crackSequence(int k, int n) {
   
7.         this.n = n;
   
8.         this.k = k;
   
9.         v = 1; for (int i = 0; i < n - 1; ++i) v *= k; // vertices are n-1 bit radix k number.
   
10.         edge = new int[v]; // edge list
    
11.         sequence = new StringBuilder();
    
12.         dfs(0);
    
13. //        for (int i = 0; i < n - 1; ++i) sequence.append(0);
    
14.         return sequence.reverse().toString();
    
15.     }
    
16. 
    
17.     // Hierholzer's algorithm
    
18.     private void dfs(int u) {
    
19.         while (edge[u] != k) {
    
20.             int i = edge[u]++;
    
21.             dfs((u * k + i) % v);
    
22.             sequence.append(i);
    
23.         }
    
24.     }
    
25. 
    
26.     public static void main(String[] args) {
    
27.         System.out.println(new EulerSolution().crackSequence(9, 4).length());
    
28.     }
    
29. }

复制代码

改写成Iterative，避免了全局变量，复杂度O(E) = O(k^n)

1. public class IterativeEulerSolution {
   
2. 
   
3.     // Hierholzer's algorithm
   
4.     public String crackSequence(int k, int n) {
   
5.         int v = 1;
   
6.         for (int i = 0; i < n - 1; ++i) v *= k; // vertices are n-1 bit radix k number.
   
7.         int[] edge = new int[v];
   
8.         StringBuilder sequence = new StringBuilder();
   
9.         
   
10.         int u = 0, i = 0;
    
11.         Deque<Integer[]> stack = new ArrayDeque<>();
    
12.         while (true) {
    
13.             if (i == k) {
    
14.                 if (stack.isEmpty()) break;
    
15.                 Integer[] t = stack.pop();
    
16.                 u = t[0];
    
17.                 sequence.append(t[1]);
    
18.                 i = edge[u];
    
19.             } else {
    
20.                 stack.push(new Integer[]{u, i});
    
21.                 edge[u]++;
    
22.                 u = (u * k + i) % v;
    
23.                 i = edge[u];
    
24.             }
    
25.         }
    
26. 
    
27. //        for (int i = 0; i < n - 1; ++i) sequence.append(0);
    
28.         return sequence.reverse().toString();
    
29.     }
    
30. 
    
31.     public static void main(String[] args) {
    
32.         System.out.println(new IterativeEulerSolution().crackSequence(10, 4).length());
    
33.     }
    
34. }

复制代码

来一发Benchmark~

1. // (k,n)      de Bruijin       recursive-euler        iterative-euler
   
2. // (2,2)      0.094 ms         0.031 ms               0.121 ms
   
3. // (2,4)      0.105 ms         0.041 ms               0.131 ms
   
4. // (2,8)      0.427 ms         0.165 ms               0.888 ms
   
5. // (4,2)      0.230 ms         0.044 ms               0.132 ms
   
6. // (4,4)      0.297 ms         0.174 ms               0.651 ms
   
7. // (4,6)      2.091 ms         1.098 ms               5.627 ms
   
8. // (8,2)      0.155 ms         0.055 ms               0.179 ms
   
9. // (8,4)      1.831 ms         0.993 ms               9.783 ms
   
10. // (10,4)     4.405 ms         1.848 ms              13.556 ms
    
11. // (20,4)    17.316 ms        55.785 ms              71.769 ms
    
12. // (10,6)    48.535 ms        79.245 ms             270.148 ms
    

复制代码