[Google] Guess Password - Shuatiblog.com

[Google] Guess Password - Shuatiblog.com
给你一个password 假定6位
有个function, 每call一次就给你一个triplet 是password 里的随即三位(order不变)。比如google, 可能返回: ggl, goe, oog, ool…
问如何最有效破译这个密码?

六位密码随机给三位，应该有C(6, 3) = 20个bucket。
如果密码是abcdef，那么以a开头的bucket应该是 C(5, 2) = 10个。以b开头的buckt应该是C(4, 2) = 6个，以c开头的是3个，以d开头的是1个…. from this, we know the probability of the occurrance of each letter.

In this case, we generate many triplets, and calculate based on their frequencies. However, the guy also wrote about this condition:

如果abcd中间有相同(there are same letters in the 6-char password)，那么就会出现以a开头的是11个（abca)，13个(abad)，14个(abaa)，16个(aacd)，17个(aaca),19个(aaad)或者20个(aaaa).

思路是比较清楚，不过算法还要想想。

可以从最简单情况开始考虑：如果密码只有两位，随机给一位，应该怎么做

那么就是随机N次，把N次的结果分类计数。如果有两个bucket，比如是x和y，那么密码
应该是xy或者yx。如果只有一个bucket，比如是x，那密码就是xx。

http://www.mitbbs.com/article_t/JobHunting/32658281.html
那么三位密码随机给两位，应该有C(3,2) = 3个bucket.
比如xy, yz和xz，那么密码应该是xyz。
如果是xy, yx, yy，那么密码就是yxy. 
但是也有可能是两个bucket，比如xy（bucket count = 2N/3), yy (bucket count = N
/3), 那么三个bucket其实是xy, xy和yy， 密码是xyy. 
也有可能是一个bucket，xx (bucket count = N)，那么三个bucket其实是xx，xx和xx
，密码是xxx。

http://www.weiming.info/zhuti/JobHunting/32658281/


https://github.com/breezedu/leetcodes2013/blob/master/DecodeTripletPassword.java
我来一个不用统计学的Draft吧，只需要知道所有可能组合就可以推出原String：
比如google的所有可能组合一共是13种：{gge,gle,ole,ogl,goe,oge,gog,ool,ggl,oog
, gol,ooe,goo}，把这些组合都放到一个ArrayList里，然后call dfsDecode()就可以
逆推了。
ArrayList<String> prosStrList = new ArrayList<String>();
String head = "";
dfsDecode(head, setList, prosStrList);
private static void dfsDecode(String head, ArrayList<String> setList, ArrayList<String> prosStrList) {
  if(head.length()==6){  
    //check if every triple-letter string in the setList could be found in the current head string;
    //if yes, add head to prosStrList arrayList;  
    if(everyTriCouldbeFound(setList, head)){
      prosStrList.add(head);    
    }
    // prosStrList.add(head);
    return;
  }
 
  for(int i=0; i<setList.size(); i++){
    if(head==""){
      String headStr = setList.get(i);
      dfsDecode(headStr, setList, prosStrList);  
    } else {    
      if(head.substring(head.length()-2).equals( setList.get(i).substring(0,2) )){
        System.out.println(head + ": " + head.substring(head.length()-2) +", next:" +setList.get(i));
       
        String headNext = head + setList.get(i).charAt(setList.get(i).length()-1);
        dfsDecode(headNext, setList, prosStrList);
      }
    }//end if-else head=="" conditions;
   
  }//end for i<setList.size() loop;
 
}//end dfsDecode() method;

private static boolean everyTriCouldbeFound(ArrayList<String> setList, String head) {
  for(int index=0; index<setList.size(); index++){
   
    String currStr = setList.get(index);
    boolean found = false;
    for(int i=0; i<4; i++){
      for(int j=i+1; j<5; j++){
        for(int k=j+1; k<6; k++){
         
          if(currStr.charAt(0)==head.charAt(i) && currStr.charAt(1)==head.charAt(j) &&
            currStr.charAt(2)==head.charAt(k)) {
            found = true;
            i=6;j=6;k=6;
          }
        }
      }
    }
   
    if(found==false) return false;
  }
  return true;
}
private static String tripletPick(String oriStr) {
// TODO pick out three letters from a stirng, keep the original order;
int Len = oriStr.length();
if(Len ==3) return oriStr;
//here we know the length of the password string is 6;

String retStr = "";

int index1 = (int)(Math.random()*(Len-2));
int index2 = (int)(Math.random()*(Len-2 - index1)) + index1+1;
int index3 = (int)(Math.random()*(Len-1-index2)) + index2+1;

//System.out.print(" indices: " + index1 + " " + index2 +" " + index3 +". ");

return retStr+oriStr.charAt(index1) + oriStr.charAt(index2) + oriStr.charAt(index3);
}
Read full article from [Google] Guess Password - Shuatiblog.com