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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 给你一个password 假定6位, : 有个function 每call 一次就给你一个triplet 是password 里的随即三位,order不变 : 。比如google, 可能返回, ggl, goe, oog, ool, ........ : 问如何最有效破译这个密码,写code. : 怎么做?
| p*****2 发帖数: 21240 | 4
有道理
【在 y*****9 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 这能作么?如果你密码是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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 给你一个password 假定6位, : 有个function 每call 一次就给你一个triplet 是password 里的随即三位,order不变 : 。比如google, 可能返回, ggl, goe, oog, ool, ........ : 问如何最有效破译这个密码,写code. : 怎么做?
| l*********8 发帖数: 4642 | 8 如果没有重复字母的话,可以用topological sort.
【在 j*********n 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 给你一个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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 给你一个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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 假设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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 只有六位的话就暴力了。不断的call知道发现六个数都是什么,不管顺序。然后做全排 : 列找出符合条件的...
| A*********c 发帖数: 430 | 12 "不断的call知道发现六个数都是什么"
这步如何确定终止条件?无法知道是否已经返回了全部6个数,还是总有某位没有被返
回。
虽然不停地call概率越来越大
比如密码是aaaaaaaaa
每次返回aa
密码是aaaaaaaab也可能如此
【在 b***e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 只有六位的话就暴力了。不断的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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 给你一个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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 这题想来想去就只能靠概率来猜。 : 抛足够多次的话,通过第一位的结果就可以推测出前四个字母 : 通过最后一位的结果可以推测出后四位字母
| 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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 假设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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 频率统计法 : 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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 你的code只能猜google还是可以猜任意6位字符串?貌似只是根据google做heuristic? : ps,看到static string = "google",我觉得最好的破解办法也许是反编译:)
| | | w********s 发帖数: 1570 | 21 所有的组合都可以
比如
aaaaaa
abcdef
aabccd
aabbcc
...
【在 d******g 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 你的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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 所有的组合都可以 : 比如 : aaaaaa : abcdef : aabccd : aabbcc : ...
|
|