i*********e
发帖数: 90 | 1 在板上看到一个狗家面试题，但是没有看到解法。不明白这个用toposort怎么做。有大
侠解释一下吗？题目如下：
有一个字典因为某种原因每个字符都被替换成一个别的字符了（但还是一一对应)，但
是单词的顺序没有改变，比如
cat
coffee
common
变成了
dkc
dbhhzz
dbllbq
让找出的这个替换的规则（guaranteed to have a unique one) | t********2
发帖数: 28 | 2
在板上看到一个狗家面试题，但是没有看到解法。不明白这个用toposort怎么做。有大
侠解释一下吗？题目如下：有一个字典因为某种原因每个字符都被替换成一个别的字符
了（但还是一一对........
【在 i*********e 的大作中提到】
: 在板上看到一个狗家面试题，但是没有看到解法。不明白这个用toposort怎么做。有大
: 侠解释一下吗？题目如下：
: 有一个字典因为某种原因每个字符都被替换成一个别的字符了（但还是一一对应)，但
: 是单词的顺序没有改变，比如
: cat
: coffee
: common
: 变成了
: dkc
: dbhhzz
| t********2
发帖数: 28 | 3 感觉就是排序 凑够26个 一一对应原来的字符就可以了
【在 t********2 的大作中提到】
:
: 在板上看到一个狗家面试题，但是没有看到解法。不明白这个用toposort怎么做。有大
: 侠解释一下吗？题目如下：有一个字典因为某种原因每个字符都被替换成一个别的字符
: 了（但还是一一对........
| l*****a
发帖数: 14598 | 4 什么叫单词的顺序没有变？正常意义上dkc应该在dbhhzz后面吧？
题目是通过单词mapping找到
a to z的一个permutation,并且任意字母都不在原位？
【在 i*********e 的大作中提到】
: 在板上看到一个狗家面试题，但是没有看到解法。不明白这个用toposort怎么做。有大
: 侠解释一下吗？题目如下：
: 有一个字典因为某种原因每个字符都被替换成一个别的字符了（但还是一一对应)，但
: 是单词的顺序没有改变，比如
: cat
: coffee
: common
: 变成了
: dkc
: dbhhzz
| q*****w
发帖数: 62 | 5 昨天面试刚被问道，先两两构建graph中connection，然后对图进行拓扑排序。 | s******d
发帖数: 424 | 6 可以统计每个字符出现次数然后匹配吗？类似加密破解，一般来说S是出现最多的。。
。 | n*****a
发帖数: 107 | 7 这个题是我上nlp课时的一个作业，当时给了一大串文本，也是像你这种编码的，然后
找出对应关系。这个decipher是个经典问题，网上应该有好多例子的。
如果没有其他的数据的话，应该是用EM算法来做的
首先random initialize两种probability， e代表英文字母，c代表密码字母：
p(e_i|e_i-1) 一个字母出现在另一个字母之后的概率
and p(c|e) 这个英文字母e，被编码成c的概率
然后用forward-backward algorithm，求fractional count。更新那两个概率值。
然后这样来回更新几次。
直到整体的概率值（forward algorithm的最后结果）不再增加了，就结束了。
【在 i*********e 的大作中提到】
: 在板上看到一个狗家面试题，但是没有看到解法。不明白这个用toposort怎么做。有大
: 侠解释一下吗？题目如下：
: 有一个字典因为某种原因每个字符都被替换成一个别的字符了（但还是一一对应)，但
: 是单词的顺序没有改变，比如
: cat
: coffee
: common
: 变成了
: dkc
: dbhhzz
| g*****n
发帖数: 31 | 8 单词的顺序没有改变。。。
这个条件下 这个题就比你说的容易多了
【在 n*****a 的大作中提到】
: 这个题是我上nlp课时的一个作业，当时给了一大串文本，也是像你这种编码的，然后
: 找出对应关系。这个decipher是个经典问题，网上应该有好多例子的。
: 如果没有其他的数据的话，应该是用EM算法来做的
: 首先random initialize两种probability， e代表英文字母，c代表密码字母：
: p(e_i|e_i-1) 一个字母出现在另一个字母之后的概率
: and p(c|e) 这个英文字母e，被编码成c的概率
: 然后用forward-backward algorithm，求fractional count。更新那两个概率值。
: 然后这样来回更新几次。
: 直到整体的概率值（forward algorithm的最后结果）不再增加了，就结束了。
| n*****a
发帖数: 107 | 9 这个没明白，要怎么拓扑排序啊。
【在 q*****w 的大作中提到】
: 昨天面试刚被问道，先两两构建graph中connection，然后对图进行拓扑排序。
| q*****w
发帖数: 62 | 10 看到楼上EM都出来了，我觉得应该是楼主没说清楚题目．就在昨天在yahoo面试中考到
一模一样地题目。
应该是这样：
最初有一个list l1，这个list是经过字典排序过的，eg，“apple“， “boy”。现在
对l1做一个变换， 这个变换是一一映射。数学表示为f : a->e, p->d, l->f, e->o, b
->...... 这样就得到了变换后的list, l2, 假设是 eddfo, qxz。
题目是只给l2, 求映射关系。
题解：
因为顺序没有改变，所以可以得到 f-1(e) > f-1(q) 即e映射前对应字母在字典序中的
位置是大于q映射前，这样一直找下去。所有的两两关系是一个图，图中肯定是没有
cycle的（因为是一一映射）。这样对这个图进行拓扑排序后输出的顺序就依次对应a,
b, c, d, e, f ...... | | | n*****a
发帖数: 107 | 11 谢谢ls的解释，这样就明白了。
b
【在 q*****w 的大作中提到】
: 看到楼上EM都出来了，我觉得应该是楼主没说清楚题目．就在昨天在yahoo面试中考到
: 一模一样地题目。
: 应该是这样：
: 最初有一个list l1，这个list是经过字典排序过的，eg，“apple“， “boy”。现在
: 对l1做一个变换， 这个变换是一一映射。数学表示为f : a->e, p->d, l->f, e->o, b
: ->...... 这样就得到了变换后的list, l2, 假设是 eddfo, qxz。
: 题目是只给l2, 求映射关系。
: 题解：
: 因为顺序没有改变，所以可以得到 f-1(e) > f-1(q) 即e映射前对应字母在字典序中的
: 位置是大于q映射前，这样一直找下去。所有的两两关系是一个图，图中肯定是没有
| i*********e
发帖数: 90 | 12 题目是别的帖子里copy过来得，我也不大清楚。这个一一映射list2只见字母得排序完
全由list1决定得，本身毫无规律是么？那样的话需要所有字母得映射才行。难道我得
理解有误？
最初我以为是找list2得规律，比如list2得字母加减乘除某一个数字得到list1的字母y
＝f（x）之类的。
b
【在 q*****w 的大作中提到】
: 看到楼上EM都出来了，我觉得应该是楼主没说清楚题目．就在昨天在yahoo面试中考到
: 一模一样地题目。
: 应该是这样：
: 最初有一个list l1，这个list是经过字典排序过的，eg，“apple“， “boy”。现在
: 对l1做一个变换， 这个变换是一一映射。数学表示为f : a->e, p->d, l->f, e->o, b
: ->...... 这样就得到了变换后的list, l2, 假设是 eddfo, qxz。
: 题目是只给l2, 求映射关系。
: 题解：
: 因为顺序没有改变，所以可以得到 f-1(e) > f-1(q) 即e映射前对应字母在字典序中的
: 位置是大于q映射前，这样一直找下去。所有的两两关系是一个图，图中肯定是没有
| h*d
发帖数: 19309 | 13 用字典做Baysian, HMM之类的来推？
b
【在 q*****w 的大作中提到】
: 看到楼上EM都出来了，我觉得应该是楼主没说清楚题目．就在昨天在yahoo面试中考到
: 一模一样地题目。
: 应该是这样：
: 最初有一个list l1，这个list是经过字典排序过的，eg，“apple“， “boy”。现在
: 对l1做一个变换， 这个变换是一一映射。数学表示为f : a->e, p->d, l->f, e->o, b
: ->...... 这样就得到了变换后的list, l2, 假设是 eddfo, qxz。
: 题目是只给l2, 求映射关系。
: 题解：
: 因为顺序没有改变，所以可以得到 f-1(e) > f-1(q) 即e映射前对应字母在字典序中的
: 位置是大于q映射前，这样一直找下去。所有的两两关系是一个图，图中肯定是没有
| d******n
发帖数: 22 | 14 还是不是很明白，图的两两关系是指什么，如何进行的排序
可否再详细一点，谢谢
b
【在 q*****w 的大作中提到】
: 看到楼上EM都出来了，我觉得应该是楼主没说清楚题目．就在昨天在yahoo面试中考到
: 一模一样地题目。
: 应该是这样：
: 最初有一个list l1，这个list是经过字典排序过的，eg，“apple“， “boy”。现在
: 对l1做一个变换， 这个变换是一一映射。数学表示为f : a->e, p->d, l->f, e->o, b
: ->...... 这样就得到了变换后的list, l2, 假设是 eddfo, qxz。
: 题目是只给l2, 求映射关系。
: 题解：
: 因为顺序没有改变，所以可以得到 f-1(e) > f-1(q) 即e映射前对应字母在字典序中的
: 位置是大于q映射前，这样一直找下去。所有的两两关系是一个图，图中肯定是没有
| d******n
发帖数: 22 | 15
b
【在 q*****w 的大作中提到】
: 看到楼上EM都出来了，我觉得应该是楼主没说清楚题目．就在昨天在yahoo面试中考到
: 一模一样地题目。
: 应该是这样：
: 最初有一个list l1，这个list是经过字典排序过的，eg，“apple“， “boy”。现在
: 对l1做一个变换， 这个变换是一一映射。数学表示为f : a->e, p->d, l->f, e->o, b
: ->...... 这样就得到了变换后的list, l2, 假设是 eddfo, qxz。
: 题目是只给l2, 求映射关系。
: 题解：
: 因为顺序没有改变，所以可以得到 f-1(e) > f-1(q) 即e映射前对应字母在字典序中的
: 位置是大于q映射前，这样一直找下去。所有的两两关系是一个图，图中肯定是没有
| c******0
发帖数: 260 | 16 最近很多人被面到这题啊。不就是找字母顺序么？？
void ordering(string s[], int N){
unordered_map track;
char begin = s[0][0];
for(int i=0; i
int j=i+1;
int k=0;
while(k
k++;
}
track[s[i][k]] = s[j][k];
if(s[j][k] == begin) begin = s[i][k];
}
while(track.find( begin ) != track.end()){
cout<< begin << " ->" << track[begin] << " , ";
begin = track[begin];
}
}
int main() {
// your code goes here
string s[]={"wrt", "wrf", "er", "ett", "rftt","te","ba","bw","fw"};
ordering(s, 9);
return 0;
} | q****m
发帖数: 177 | 17 也就是题目都不告诉l1 是什么?
b
【在 q*****w 的大作中提到】
: 看到楼上EM都出来了，我觉得应该是楼主没说清楚题目．就在昨天在yahoo面试中考到
: 一模一样地题目。
: 应该是这样：
: 最初有一个list l1，这个list是经过字典排序过的，eg，“apple“， “boy”。现在
: 对l1做一个变换， 这个变换是一一映射。数学表示为f : a->e, p->d, l->f, e->o, b
: ->...... 这样就得到了变换后的list, l2, 假设是 eddfo, qxz。
: 题目是只给l2, 求映射关系。
: 题解：
: 因为顺序没有改变，所以可以得到 f-1(e) > f-1(q) 即e映射前对应字母在字典序中的
: 位置是大于q映射前，这样一直找下去。所有的两两关系是一个图，图中肯定是没有
| w*****e
发帖数: 1050 | 18
你这个算出来的是 映射后的字母的顺序
再跟abcd...z对比就是映射了
string letter="abcdefghigklmnopqrstuvwxyz";
int i=0;
while(track.find( begin ) != track.end()){
cout<< begin << " ->" << letter[i++] << " , ";
begin = track[begin];
}
【在 c******0 的大作中提到】
: 最近很多人被面到这题啊。不就是找字母顺序么？？
: void ordering(string s[], int N){
: unordered_map track;
: char begin = s[0][0];
: for(int i=0; i: int j=i+1;
: int k=0;
: while(k: k++;
: }
| f**********t
发帖数: 1001 | 19 #include "common.h"
void CS_(const vector &vs, size_t up, size_t down, size_t col,
map> &graph) {
size_t uu = up;
while (uu < down && vs[uu].size() <= col) {
++uu;
}
if (uu + 1 >= down) {
return;
}
char pre = vs[uu][col];
for (size_t dd = uu + 1; dd < down; ++dd) {
if (vs[dd].size() <= col) {
continue;
}
if (pre != vs[dd][col]) {
graph[pre].insert(vs[dd][col]);
if (uu + 1 < dd) {
CS_(vs, uu, dd, col + 1, graph);
}
pre = vs[dd][col];
uu = dd;
}
}
if (uu + 1 < down) {
CS_(vs, uu, down, col + 1, graph);
}
}
string TopoSort(map> &graph) {
map> revert;
for (auto pr : graph) {
for (char c : pr.second) {
revert[c].insert(pr.first);
}
}
queue qu;
string res;
for (auto pr : graph) {
if (revert.find(pr.first) == revert.end()) {
qu.push(pr.first);
}
}
while (!qu.empty()) {
char c = qu.front();
res.push_back(c);
qu.pop();
for (char child : graph[c]) {
revert[child].erase(c);
if (revert[child].empty()) {
qu.push(child);
}
}
}
return res;
}
string CharSequence(vector vs) {
map> graph;
CS_(vs, 0, vs.size(), 0, graph);
return TopoSort(graph);
}
void CharSequenceTest() {
cout << CharSequence({"dkc", "dbhhzz", "dbllbq"}) << endl;
}
【在 i*********e 的大作中提到】
: 在板上看到一个狗家面试题，但是没有看到解法。不明白这个用toposort怎么做。有大
: 侠解释一下吗？题目如下：
: 有一个字典因为某种原因每个字符都被替换成一个别的字符了（但还是一一对应)，但
: 是单词的顺序没有改变，比如
: cat
: coffee
: common
: 变成了
: dkc
: dbhhzz
| b******i
发帖数: 914 | 20 你说的这个是概率的，楼主的题目貌似是deterministic的一一对应的
不过你这个很有意思，原题是什么？
【在 n*****a 的大作中提到】
: 这个题是我上nlp课时的一个作业，当时给了一大串文本，也是像你这种编码的，然后
: 找出对应关系。这个decipher是个经典问题，网上应该有好多例子的。
: 如果没有其他的数据的话，应该是用EM算法来做的
: 首先random initialize两种probability， e代表英文字母，c代表密码字母：
: p(e_i|e_i-1) 一个字母出现在另一个字母之后的概率
: and p(c|e) 这个英文字母e，被编码成c的概率
: 然后用forward-backward algorithm，求fractional count。更新那两个概率值。
: 然后这样来回更新几次。
: 直到整体的概率值（forward algorithm的最后结果）不再增加了，就结束了。
|
|
