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

蛀牙jj 发表于 2016-1-22 14:36
我能想到的也是暴力破解啊，四个for循环嵌套

那各位大神，这个解法你们能看懂吗？

nlx 发表于 2016-1-22 11:50
这个题目有些难了。主要是很多人没有见过Lyndon word。可以参考 https://en.wikipedia.org/wiki/Lyndon_wor ...

那各位大神，这个解法你们能看懂吗？

nlx 发表于 2016-1-22 11:50
这个题目有些难了。主要是很多人没有见过Lyndon word。可以参考 https://en.wikipedia.org/wiki/Lyndon_wor ...

大神你好，请问关于Lyndon word你有什么好的资料吗？我找了一些，看上去都说的很晦涩。
这个算法的粗糙框架我是知道了，就是把Lyndon words按字典序排起来就是结果。但是算法的正确性以及Lyndon word的generating algorithm看上去都很精妙，能否指点一下？谢谢！

个人意见，这个题的最优解法要求你对de Bruijn图和汉密尔顿回路或者Lyndon words有相当了解，作为面试题的话，明显过于难了。所以我想应该和Flip Game这类题是一个性质：你用DFS等方法解出来是完全可以的，然后再进行优化，复杂度分析等等。这题的作用应该是看你“在面对一个非常难的问题时，会采用怎样的思考方式去试图解决它”。

当然，说了这么多，主要原因是我也没看懂代码……

stellari 发表于 2016-1-23 09:09
个人意见，这个题的最优解法要求你对de Bruijn图和汉密尔顿回路或者Lyndon words有相当了解，作为面试题的 ...

这道题实在是太难了，对我来说，代码也是，考到这道题，直接写出来的话，gg应该都是直接录了……
但是，说了这么多，还是不懂代码上意思我还是放弃这道题吧

我也是gg申请intern的时候 直接跪了。。。。

illuminati 发表于 2016-1-23 09:33
我也是gg申请intern的时候 直接跪了。。。。

这不是一道onsite的题吗……怎么intern都来了

神罗天征 发表于 2016-1-23 09:59
这不是一道onsite的题吗……怎么intern都来了

我点背啊。。我申intern 第一轮phone interview的时候 就被烤了这道题。。。。然后就傻了

illuminati 发表于 2016-1-23 10:24
我点背啊。。我申intern 第一轮phone interview的时候 就被烤了这道题。。。。然后就傻了

我学长也是intern遇到了这道题~然后到现在都不知道怎么做……

大概写了一下DFS的代码，我认为面试的话，给到这种解法已经可以了。下面的代码基于这些事实：
1. 因为de Bruijn sequence其实上是一个环，所以这个序列可以以任意四位数开头。此处，我们总是选0000开头。
2. de Bruijn sequence长度总是k^n，在本题中就是10^4。

class DeBruijn10 {
        bool DFS(int ind) {
                if (ind==upper) { // No more number left
                        for (int i = 1; i <= n-1; ++i) { // Still need to validate the numbers that "wrap around"
                string st = seq.substr(upper-n+i, n-i) + seq.substr(0, i);
                                int temp = atoi(st.c_str());
                                if (avail[temp] == false) {
                    return false;
                                }
                        }
                        return true;
                }

                int prefix = atoi(seq.substr(ind-(n-1), n-1).c_str()) *10;
                for (int i = 0; i <= 9; ++i) {
                        int cur = prefix + i;    // Try each possible choice at the current location
                        if (avail[cur]) {        // If this number hasn't appeared so far
                                avail[cur] = false;  // then try it.
                                seq[ind] = i + '0';
                                if (DFS(ind+1)) return true;
                                avail[cur] = true;
                        }
                }
                return false;
        }
public:
    int n;
        int upper;
        vector<bool> avail;
        string seq;

        DeBruijn10(int _n):
                n(_n),
                upper(pow(10, n)),
                avail(upper, true),
                seq(upper, '0')
        {
                avail[0] = false;
                DFS(n);
        }
        void output() const {
            cout << "Length = " << seq.size() <<endl;
                cout << seq << endl;
        }
};