一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 2806|回复: 45
收起左侧

[算法题] Google面经题密码箱问题解法求问

[复制链接] |试试Instant~ |关注本帖
神罗天征 发表于 2016-1-18 02:56:29 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
求问这道题的算法,看不懂代码,求大神解释一下~
一堆密码箱,每个密码都是四位0-9之间,算一个暴力破解序列,包含所有可能的四位序列,让这个序列尽量短
用的是DeBruijn,代码如下

  1. public class DeBruijn {
  2.         public static String generateDeBruijnSequence(int k, int n) {
  3.                 StringBuilder sequence = new StringBuilder();
  4.                 generateLyndonWords(1, 1, k, new int[n+1], sequence);
  5.                 return sequence.toString();
  6.         }

  7.         private static void generateLyndonWords(int t, int p, int k, int[] a, StringBuilder sequence) {
  8.                 if (t > a.length-1) {
  9.                         if((a.length-1)%p==0) {
  10.                                 for(int i = 1; i < p+1;i++) {
  11.                                         sequence.append(a[i]);
  12.                                 }
  13.                         }
  14.                 } else {
  15.                         a[t] = a[t-p];
  16.                         generateLyndonWords(t+1,p, k, a, sequence);
  17.                         for(int j=a[t-p]+1; j<=k-1; j++) {
  18.                                 a[t] = j;
  19.                                 generateLyndonWords(t+1,t, k, a, sequence);
  20.                         }
  21.                 }
  22.         }
  23.         public static void main(String[] args){
  24.                 System.out.println(generateDeBruijnSequence(10, 4).length());
  25.         }
  26. }
复制代码
coolidgelyt 发表于 2016-1-26 08:30:23 | 显示全部楼层
这里有个贴子说得很清楚:http://xwk.iteye.com/blog/2129621
回复 支持 1 反对 0

使用道具 举报

战栗的百香果 发表于 2016-1-22 07:50:42 | 显示全部楼层
我也是面的这道题- -
回复 支持 反对

使用道具 举报

 楼主| 神罗天征 发表于 2016-1-22 07:55:53 | 显示全部楼层

请问你知道求解得吗
回复 支持 反对

使用道具 举报

战栗的百香果 发表于 2016-1-22 07:56:35 | 显示全部楼层
神罗天征 发表于 2016-1-22 07:55
请问你知道求解得吗

我就是因为这道题跪了- -
回复 支持 反对

使用道具 举报

 楼主| 神罗天征 发表于 2016-1-22 08:02:14 | 显示全部楼层
战栗的百香果 发表于 2016-1-22 07:56
我就是因为这道题跪了- -

好吧,我就是看了面经看到了这道题,觉得太难了,google了解法,但是也不看懂……
回复 支持 反对

使用道具 举报

战栗的百香果 发表于 2016-1-22 08:18:44 | 显示全部楼层
神罗天征 发表于 2016-1-22 08:02
好吧,我就是看了面经看到了这道题,觉得太难了,google了解法,但是也不看懂……

我当时听到这道题写了个暴力然后就蒙了
回复 支持 反对

使用道具 举报

 楼主| 神罗天征 发表于 2016-1-22 08:38:31 | 显示全部楼层
战栗的百香果 发表于 2016-1-22 08:18
我当时听到这道题写了个暴力然后就蒙了

这面得太难了吧,gg太变态了。那暴力求解怎么做呀
回复 支持 反对

使用道具 举报

nlx 发表于 2016-1-22 11:50:39 | 显示全部楼层
这个题目有些难了。主要是很多人没有见过Lyndon word。可以参考 https://en.wikipedia.org/wiki/Lyndon_word
这样的题目其实回答的时候要和面试官讨论,首先说只有1个箱子,每个密码只有1位,每位密码都只有2个值可去,然后开始向上逐一构造,比方说,先变化成2位密码,看看怎么写。好像GOOGLE非常喜欢问这类构造性的问题。

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

战栗的百香果 发表于 2016-1-22 12:35:56 | 显示全部楼层
神罗天征 发表于 2016-1-22 08:38
这面得太难了吧,gg太变态了。那暴力求解怎么做呀

dfs生成所有四位数啊- -
回复 支持 反对

使用道具 举报

蛀牙jj 发表于 2016-1-22 14:36:39 | 显示全部楼层
战栗的百香果 发表于 2016-1-22 12:35
dfs生成所有四位数啊- -

我能想到的也是暴力破解啊,四个for循环嵌套
回复 支持 反对

使用道具 举报

 楼主| 神罗天征 发表于 2016-1-22 15:23:59 | 显示全部楼层
蛀牙jj 发表于 2016-1-22 14:36
我能想到的也是暴力破解啊,四个for循环嵌套

那各位大神,这个解法你们能看懂吗?
回复 支持 反对

使用道具 举报

 楼主| 神罗天征 发表于 2016-1-22 15:24:18 | 显示全部楼层
nlx 发表于 2016-1-22 11:50
这个题目有些难了。主要是很多人没有见过Lyndon word。可以参考 https://en.wikipedia.org/wiki/Lyndon_wor ...

那各位大神,这个解法你们能看懂吗?
回复 支持 反对

使用道具 举报

163 发表于 2016-1-23 08:38:14 | 显示全部楼层
nlx 发表于 2016-1-22 11:50
这个题目有些难了。主要是很多人没有见过Lyndon word。可以参考 https://en.wikipedia.org/wiki/Lyndon_wor ...

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

使用道具 举报

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

当然,说了这么多,主要原因是我也没看懂代码……
回复 支持 反对

使用道具 举报

 楼主| 神罗天征 发表于 2016-1-23 09:16:04 | 显示全部楼层
stellari 发表于 2016-1-23 09:09
个人意见,这个题的最优解法要求你对de Bruijn图和汉密尔顿回路或者Lyndon words有相当了解,作为面试题的 ...

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

使用道具 举报

illuminati 发表于 2016-1-23 09:33:50 | 显示全部楼层
我也是gg申请intern的时候 直接跪了。。。。
回复 支持 反对

使用道具 举报

 楼主| 神罗天征 发表于 2016-1-23 09:59:21 | 显示全部楼层
illuminati 发表于 2016-1-23 09:33
我也是gg申请intern的时候 直接跪了。。。。

这不是一道onsite的题吗……怎么intern都来了
回复 支持 反对

使用道具 举报

illuminati 发表于 2016-1-23 10:24:05 | 显示全部楼层
神罗天征 发表于 2016-1-23 09:59
这不是一道onsite的题吗……怎么intern都来了

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

使用道具 举报

 楼主| 神罗天征 发表于 2016-1-23 11:00:06 | 显示全部楼层
illuminati 发表于 2016-1-23 10:24
我点背啊。。我申intern 第一轮phone interview的时候 就被烤了这道题。。。。然后就傻了

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

使用道具 举报

stellari 发表于 2016-1-23 17:51:23 | 显示全部楼层
本帖最后由 stellari 于 2016-1-23 18:00 编辑

大概写了一下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;
        }
};




回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-10 10:59

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表