j*********n
发帖数: 34 | 1 给你一个password 假定6位，
有个function 每call 一次就给你一个triplet 是password 里的随即三位，order不变
。比如google, 可能返回， ggl, goe, oog, ool, ........
问如何最有效破译这个密码，写code.
怎么做？ | y*****9
发帖数: 149 | 2 这能作么？如果你密码是aaaaaa，你怎么知道每次给你的是前3个a，还是都是a?比如你
密码是aaabbb也可能每次都得到aaa。
是说得考虑给了很多次数组之后最大可能的密码是多少么？ | b***e
发帖数: 1419 | 3 只有六位的话就暴力了。不断的call知道发现六个数都是什么，不管顺序。然后做全排
列找出符合条件的...
【在 j*********n 的大作中提到】
: 给你一个password 假定6位，
: 有个function 每call 一次就给你一个triplet 是password 里的随即三位，order不变
: 。比如google, 可能返回， ggl, goe, oog, ool, ........
: 问如何最有效破译这个密码，写code.
: 怎么做？
| p*****2
发帖数: 21240 | 4
有道理
【在 y*****9 的大作中提到】
: 这能作么？如果你密码是aaaaaa，你怎么知道每次给你的是前3个a，还是都是a?比如你
: 密码是aaabbb也可能每次都得到aaa。
: 是说得考虑给了很多次数组之后最大可能的密码是多少么？
| s********f
发帖数: 510 | 5 可以从最简单情况开始考虑：如果密码只有两位，随机给一位，应该怎么做
那么就是随机N次，把N次的结果分类计数。如果有两个bucket，比如是x和y，那么密码
应该是xy或者yx。如果只有一个bucket，比如是x，那密码就是xx。
那么三位密码随机给两位，应该有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。
六位密码随机给三位，应该有C(6, 3) = 20个bucket。
比如密码是google
那么着二十个bucket是
goo, gog, gol, goe, gog, gol, goe, ggl, gge, gle, oog, ool, ooe, ogl, oge,
ole, ogl, oge, ole, gle
那么以g开头的bucket最多，11个，并且多余C(5,2)=10, 说明password首字母应该是g,
并且应该有一个g在后面 因为11-10=1那么第二个g只能在倒数第三位了。
以o开头的bucket第二多，有9个，多余C(4,2)=6, 说明password第二字母是0，并且有
一个o在后面。9-6=3=C(3,2)，说明第二个o在倒数第四位.
反过来看，以e结尾的bucket有正好10个，说明e是尾字母，以l结尾的bucket有正好6个
，说明l是倒数第二个字母。
那么密码是google。
如果密码是aaaaaa, 那么应该20个bucket都是aaa, 也可以得出密码是aaaaaa的结论。
不过这不是程序，只是思路。 | s********f
发帖数: 510 | 6 如果密码是abcdef
那么以a开头的bucket应该是10个。以b开头的buckt应该是6个，以c开头的是3个，以d
开头的是1个。
如果abcd中间有相同，那么就会出现以a开头的是11个（abca)，13个(abad)， 14个(
abaa),16个(aacd)，17个(aaca),19个(aaad)或者20个(aaaa)
思路是比较清楚，不过算法还要想想。 | w********s
发帖数: 1570 | 7 假设password=abcdef
那么每次给3位x,y,z的话，x只可能在{a,b,c}中，z只可能在{d,e,f}中，
那么根据随机给的可以得出{a,b,c}和{d,e,f}
为了确定顺序，a,b,c有6种排列，d,e,f有6种排列，总共36中可能
对每一种可能做一个bucket，那么每次检验这36个bucket，直到过滤剩下1个bucket，
那个就是password.
【在 j*********n 的大作中提到】
: 给你一个password 假定6位，
: 有个function 每call 一次就给你一个triplet 是password 里的随即三位，order不变
: 。比如google, 可能返回， ggl, goe, oog, ool, ........
: 问如何最有效破译这个密码，写code.
: 怎么做？
| l*********8
发帖数: 4642 | 8 如果没有重复字母的话，可以用topological sort.
【在 j*********n 的大作中提到】
: 给你一个password 假定6位，
: 有个function 每call 一次就给你一个triplet 是password 里的随即三位，order不变
: 。比如google, 可能返回， ggl, goe, oog, ool, ........
: 问如何最有效破译这个密码，写code.
: 怎么做？
| l*******g
发帖数: 82 | 9 这是个统计题
给你一个password 假定6位， 有个function 每call 一次就给你一个triplet 是
password 里的随即三位，order不变。比如google, 可能........
【在 j*********n 的大作中提到】
: 给你一个password 假定6位，
: 有个function 每call 一次就给你一个triplet 是password 里的随即三位，order不变
: 。比如google, 可能返回， ggl, goe, oog, ool, ........
: 问如何最有效破译这个密码，写code.
: 怎么做？
| m*****n
发帖数: 2152 | 10 假设a b c d e f 是password字符的位置，而 x y z 是返回字符的位置。
x 可能是{a,b,c,d}
y 可能是{b,c,d,e}
z 可能是{c,d,e,f}
所有的组合是C(6,3) = 20种。
每个字符pos出现的概率表如下：
x y z
a 10/20 0 0
b 6/20 4/20 0
c 3/20 6/20 1/20
d 1/20 6/20 3/20
e 0 4/20 6/20
f 0 0 10/20
所以在均匀完全随机的情况下，password每个位置出现的概率是50%。所以call 20次
function的，某一个位置完全不出现的概率是0.5^20 ~ 10^(-6)，几乎可以认为不可能。
建一个二维的histogram，x axis是char，y axis是char在password的bucket的
position。
run 足够大n次 function，fill histogram，如果histogram有m个char，password有m
个字母。
然后看，每个char在y axis的频率，
比如google，首先确定有4个char {g, o, l, e}，
e最少，而且总在z pos出现，所以是最后一个,l只出现在y 和z pos上，所以是倒数第
二个，
g,o在x pos上的频率最高（应该差不多），但是g比o在y pos上的次数少，所以g是第一
个，o是第二个。
最后比较g和o在y,z上的频率，确定第三个和第四个位置是{g, o},{o,g}中的一种, ({g
,g},{o,o}已经不可能了。)
最后，楼主的G家不是google，是goldman saks吧，这是更像一道quant的题。
【在 w********s 的大作中提到】
: 假设password=abcdef
: 那么每次给3位x,y,z的话，x只可能在{a,b,c}中，z只可能在{d,e,f}中，
: 那么根据随机给的可以得出{a,b,c}和{d,e,f}
: 为了确定顺序，a,b,c有6种排列，d,e,f有6种排列，总共36中可能
: 对每一种可能做一个bucket，那么每次检验这36个bucket，直到过滤剩下1个bucket，
: 那个就是password.
| | | h*d
发帖数: 19309 | 11 通过3位字母来做排列应该快一些，而且通过新的3位字母输入可以排除掉一些排列
【在 b***e 的大作中提到】
: 只有六位的话就暴力了。不断的call知道发现六个数都是什么，不管顺序。然后做全排
: 列找出符合条件的...
| A*********c
发帖数: 430 | 12 "不断的call知道发现六个数都是什么"
这步如何确定终止条件？无法知道是否已经返回了全部6个数，还是总有某位没有被返
回。
虽然不停地call概率越来越大
比如密码是aaaaaaaaa
每次返回aa
密码是aaaaaaaab也可能如此
【在 b***e 的大作中提到】
: 只有六位的话就暴力了。不断的call知道发现六个数都是什么，不管顺序。然后做全排
: 列找出符合条件的...
| l***e
发帖数: 450 | 13 you have to assume the generated triplet is evenly distributed otherwise
there is no exit condition and there is no guarantee to get the right
password after n times. | w********s
发帖数: 1570 | 14 频率统计法
ABCDEF，每次triplet XYZ
记录X的频率，Y的频率，Z的频率
X可能包含了ABCD，A出现的频率是10/20,B:6/20,C:3/20,D:1/20
ABCD如果都相同，那么就是20
ABCD如果其中2个字母相同，就是16，13，11，9，7，4
3个字母相同，结果是19,14,10,17
都不相同就是10,6,3,1
注意10可能是abbb或者abcd，那么用Y的频率来判断哪种情况。
std::string triplet()
{
static std::string password = "google";
std::set digits;
while (digits.size() < 3)
{
int d = rand() % 6;
digits.insert(d);
}
std::string result;
for (std::set::const_iterator it = digits.begin(); it != digits.end
(); ++it)
{
result += password[*it];
}
return result;
}
void normalize(int* array, int size, int repeat)
{
for (int i = 0; i < size; ++i)
{
if (array[i] > 0)
{
array[i] = (array[i] * 20. / repeat) + 0.5;
}
}
}
std::string getfirst(int* first, int* mid)
{
std::string result = "----";
for (int i = 0; i < 26; ++i)
{
int cnt = first[i];
if (cnt > 0)
{
char ch = 'a' + i;
if (cnt == 10)
{
if (mid[ch - 'a'] > 10)
{
result[1] = ch; result[2] = ch; result[3] = ch;
}
else
{
result[0] = ch;
}
continue;
}
switch(cnt)
{
case 1:
result[3] = ch;
break;
case 3:
result[2] = ch;
break;
case 6:
result[1] = ch;
break;
case 10:
result[0] = ch;
break;
case 4:
result[3] = ch; result[2] = ch;
break;
case 7:
result[3] = ch; result[1] = ch;
break;
case 9:
result[2] = ch;result[1] = ch;
break;
case 11:
result[0] = ch; result[3] = ch;
break;
case 13:
result[0] = ch; result[2] = ch;
break;
case 16:
result[0] = ch; result[1] = ch;
break;
case 17:
result[0] = ch; result[1] = ch; result[3] = ch;
break;
case 14:
result[0] = ch; result[2] = ch; result[3] = ch;
break;
case 19:
result[0] = ch; result[1] = ch; result[2] = ch;
break;
case 20:
result[0] = ch; result[1] = ch; result[2] = ch; result[3] =
ch;
break;
default:
break;
}
}
}
return result;
}
int _tmain(int argc, _TCHAR* argv[])
{
srand(time(NULL));
int f[26] = {0};
int m[26] = {0};
int t[26] = {0};
std::vector triplets;
int repeat = 3000;
for (int i = 0; i < repeat; ++i)
{
std::string str = triplet();
f[str[0] - 'a']++;
m[str[1] - 'a']++;
t[str[2] - 'a']++;
triplets.push_back(str);
}
// normalize
normalize(f, 26, repeat);
normalize(m, 26, repeat);
normalize(t, 26, repeat);
std::string firstpart = getfirst(f, m);
std::string secondpart = getfirst(t, m);
std::string result = firstpart + secondpart[1] + secondpart[0];
std::cout << result <<"\n";
getchar();
} | w********s
发帖数: 1570 | 15 湿了一下，triplet 3000次的话，根据出现的频率计算都可以猜对。
【在 j*********n 的大作中提到】
: 给你一个password 假定6位，
: 有个function 每call 一次就给你一个triplet 是password 里的随即三位，order不变
: 。比如google, 可能返回， ggl, goe, oog, ool, ........
: 问如何最有效破译这个密码，写code.
: 怎么做？
| g*********e
发帖数: 14401 | 16 这题想来想去就只能靠概率来猜。
抛足够多次的话，通过第一位的结果就可以推测出前四个字母
通过最后一位的结果可以推测出后四位字母 | w********s
发帖数: 1570 | 17 还有一种情况需要中间一位
比如ABCD=gooo,o和g在第一位的概率是一样的。
【在 g*********e 的大作中提到】
: 这题想来想去就只能靠概率来猜。
: 抛足够多次的话，通过第一位的结果就可以推测出前四个字母
: 通过最后一位的结果可以推测出后四位字母
| d******g
发帖数: 38 | 18 分析很正确，但是感觉后面判断的时候算法流程不是很清晰
假设字符i在每个位置的出现概率是Pi=(px, py, pz)，例如你的例子Pa=(0.5, 0, 0)
由于重复的问题，最后只能统计出不同字符的出现概率，例如这个例子只有Pg,Po,Pl,
Pe
问题其实就是要找出一个Pa~Pf的组合，使其概率分布等于观察到的结果，例如
Pa+Pd = Pg
Pb+Pc = Po
Pe = Pl
Pf = Pe //注意区分2个Pe，左边代表第五个字符，右边是字母e
或者找到一个0-1矩阵A，使得A[Pa, ... Pf]^T=[Pg, Po, Pl, Pe]^T
如果概率很有特征（可以认为是概率vector的feature），例如最后一个字母的(0,0,0.
5)，那heuristic的方法就可以确定Pf=Pe，但是如果问题的规模大一些可能就会出现
ambiguous的组合，我能想到的办法就是遍历可能的组合，寻找最接近统计结果的组合
如果没有重复字母，那就是很简单了
能。
m
{g
bucket，
【在 m*****n 的大作中提到】
: 假设a b c d e f 是password字符的位置，而 x y z 是返回字符的位置。
: x 可能是{a,b,c,d}
: y 可能是{b,c,d,e}
: z 可能是{c,d,e,f}
: 所有的组合是C(6,3) = 20种。
: 每个字符pos出现的概率表如下：
: x y z
: a 10/20 0 0
: b 6/20 4/20 0
: c 3/20 6/20 1/20
| d******g
发帖数: 38 | 19 你的code只能猜google还是可以猜任意6位字符串？貌似只是根据google做heuristic？
ps，看到static string = "google"，我觉得最好的破解办法也许是反编译:)
【在 w********s 的大作中提到】
: 频率统计法
: ABCDEF，每次triplet XYZ
: 记录X的频率，Y的频率，Z的频率
: X可能包含了ABCD，A出现的频率是10/20,B:6/20,C:3/20,D:1/20
: ABCD如果都相同，那么就是20
: ABCD如果其中2个字母相同，就是16，13，11，9，7，4
: 3个字母相同，结果是19,14,10,17
: 都不相同就是10,6,3,1
: 注意10可能是abbb或者abcd，那么用Y的频率来判断哪种情况。
: std::string triplet()
| w********s
发帖数: 1570 | 20 都试过了，没问题。
【在 d******g 的大作中提到】
: 你的code只能猜google还是可以猜任意6位字符串？貌似只是根据google做heuristic？
: ps，看到static string = "google"，我觉得最好的破解办法也许是反编译:)
| | | w********s
发帖数: 1570 | 21 所有的组合都可以
比如
aaaaaa
abcdef
aabccd
aabbcc
...
【在 d******g 的大作中提到】
: 你的code只能猜google还是可以猜任意6位字符串？貌似只是根据google做heuristic？
: ps，看到static string = "google"，我觉得最好的破解办法也许是反编译:)
| f******n
发帖数: 279 | | g****s
发帖数: 1755 | 23 我来一个不用统计学的Draft吧，只需要知道所有可能组合就可以推出原String：
比如google的所有可能组合一共是13种：{gge,gle,ole,ogl,goe,oge,gog,ool,ggl,oog
, gol,ooe,goo}，把这些组合都放到一个ArrayList里，然后call dfsDecode()就可以
逆推了。
private static void dfsDecode(String head, ArrayList setList,
ArrayList prosStrList) {
// TODO Auto-generated method stub
if(head.length()==6){
prosStrList.add(head);
return;
}
for(int i=0; i
if(head==""){
String headStr = setList.get(i);
dfsDecode(headStr, setList, prosStrList);
} else {
// System.out.println(head + ": " + head.substring(head.
length()-2) +", next:" +setList.get(i).substring(0,2));
if(head.substring(head.length()-2).equals( setList.get(i).
substring(0,2) )){
String headNext = head + setList.get(i).charAt(2);
dfsDecode(headNext, setList, prosStrList);
}
}//end if-else head=="" conditions;
}//end for i
}//end dfsDecode() method;
完整的Java Code请见（随机写的tripletPick(),不满足均匀分布）：
https://github.com/breezedu/leetcodes2013/blob/master/DecodeTripletPassword.
java
目前对
google
aaaaaa
abcdef
aabccd
aabbcc
这些都Word，但对ababab这样重复的需要外加一段 recheck();
如果事先没有准备过类似的问题，Onsite遇到这样的题目还是很花费时间的吧，怎么破
？？ | C******w
发帖数: 23 | | d******g
发帖数: 38 | 25 好，给你点赞！
【在 w********s 的大作中提到】
: 所有的组合都可以
: 比如
: aaaaaa
: abcdef
: aabccd
: aabbcc
: ...
|
|
