f*********i
发帖数: 197 | 1 一个arraylist,里面有很多string,它们按照未知的alphabetical顺序排列,要求输出所
有可能的alphabetical order,(后来又问了如何判断是否有conflict)
例子:it is a good day today,
it
is
a
good
day
我觉得有两个难点,一个是如何把多个一一对应的大小关系merge,另一个是如何输出所
有的可能组合....30分钟实在是不够阿....算了,move on了.
期待高人解答. |
g**e
发帖数: 6127 | 2 没看懂输出的是什么...
【在 f*********i 的大作中提到】
: 一个arraylist,里面有很多string,它们按照未知的alphabetical顺序排列,要求输出所
: 有可能的alphabetical order,(后来又问了如何判断是否有conflict)
: 例子:it is a good day today,
: it: is: a: good: day: 我觉得有两个难点,一个是如何把多个一一对应的大小关系merge,另一个是如何输出所
: 有的可能组合....30分钟实在是不够阿....算了,move on了.
|
g*****k
发帖数: 623 | 3 Build a tree?
If it is DAG, then no conflict and then do the DFS to output the topological
order?
【在 f*********i 的大作中提到】
: 一个arraylist,里面有很多string,它们按照未知的alphabetical顺序排列,要求输出所
: 有可能的alphabetical order,(后来又问了如何判断是否有conflict)
: 例子:it is a good day today,
: it: is: a: good: day: 我觉得有两个难点,一个是如何把多个一一对应的大小关系merge,另一个是如何输出所
: 有的可能组合....30分钟实在是不够阿....算了,move on了.
|
g*****k
发帖数: 623 | 4 貌似输出所有的排序，因为是partial order所以有很多种?
没看懂输出的是什么...
【在 g**e 的大作中提到】
: 没看懂输出的是什么...
|
g*****k
发帖数: 623 | 5 and if you want all orders, then permute all children and get different DFS
topological
【在 g*****k 的大作中提到】
: Build a tree?
: If it is DAG, then no conflict and then do the DFS to output the topological
: order?
|
h*********n
发帖数: 11319 | 6 所有能判断顺序的字母之间连上一条有向边，最后会生成一个dag，然后
void printAllOrders(graph G, string order){
if（G not empty）{
for each node in G{
if(node.inDeg==0){
G.delete(node)；
order.append(node);
printAllOrders(G, order);
G.addback(node);//together with deleted edges
}
}
}
else
print order
}
printAllOrders(graph G, "");
把每个list按顺序concatenate，每个list内部随便排列
【在 f*********i 的大作中提到】
: 一个arraylist,里面有很多string,它们按照未知的alphabetical顺序排列,要求输出所
: 有可能的alphabetical order,(后来又问了如何判断是否有conflict)
: 例子:it is a good day today,
: it: is: a: good: day: 我觉得有两个难点,一个是如何把多个一一对应的大小关系merge,另一个是如何输出所
: 有的可能组合....30分钟实在是不够阿....算了,move on了.
|
r*******y
发帖数: 1081 | 7 bless
onsite到底是全面考察 problem solving 的能力
还是全面考察你是否能融入到这个team的能力？
【在 f*********i 的大作中提到】
: 一个arraylist,里面有很多string,它们按照未知的alphabetical顺序排列,要求输出所
: 有可能的alphabetical order,(后来又问了如何判断是否有conflict)
: 例子:it is a good day today,
: it: is: a: good: day: 我觉得有两个难点,一个是如何把多个一一对应的大小关系merge,另一个是如何输出所
: 有的可能组合....30分钟实在是不够阿....算了,move on了.
|
i**********e
发帖数: 1145 | 8 从你那个例子：
"it is a good day today"
可以建个链表，t->s, i->a->g->d->t
然后 merge 成：i->a->g->d->t->s
怎么打印所有 alphabetical order 的可能性如果只有一个链表写个 dfs 就好了.
但如果是这样的情况似乎很复杂啊:
c->a, s->b->a
这题是不是要有对图论有很深的知识才能答出来？
还是有一些 trick 在里面？
这里有介绍 DAG 的算法：
http://allisons.org/ll/AlgDS/Graph/DAG/
一些常见面试题的答案与总结 -
http://www.ihas1337code.com
【在 f*********i 的大作中提到】
: 一个arraylist,里面有很多string,它们按照未知的alphabetical顺序排列,要求输出所
: 有可能的alphabetical order,(后来又问了如何判断是否有conflict)
: 例子:it is a good day today,
: it: is: a: good: day: 我觉得有两个难点,一个是如何把多个一一对应的大小关系merge,另一个是如何输出所
: 有的可能组合....30分钟实在是不够阿....算了,move on了.
|
b**********2
发帖数: 1923 | 9 btw, how do u know u are rejected? does the recruiter contact u and tell u
that u are rejected? how many days after ur onsite?
【在 f*********i 的大作中提到】
: 一个arraylist,里面有很多string,它们按照未知的alphabetical顺序排列,要求输出所
: 有可能的alphabetical order,(后来又问了如何判断是否有conflict)
: 例子:it is a good day today,
: it: is: a: good: day: 我觉得有两个难点,一个是如何把多个一一对应的大小关系merge,另一个是如何输出所
: 有的可能组合....30分钟实在是不够阿....算了,move on了.
|
f*********i
发帖数: 197 | 10 两个星期没有消息,发信HR,被拒了. 发现google只要onsite后一个星期不联系你,大部
分情况就黄了.
DAG的方法好像也不太行阿,我当时就是说从图的角度来找所有可能性.他们一直纠结于
图的起点问题,我回答说所有的节点都有一个出度和一个入度,任意一个入度为0的节点
都可以作为开始节点,他们不满意.
还有,当merge的时候是要输出所有的可能,这个基本上是O(n^2)的复杂度,因为两个
independent的链表merge有up to N^2种可能,同时还要考虑他们是否部分重合.
到现在回想起来都是一头汗..... |
|
|
d*******l
发帖数: 338 | 11 最后图可能是不连通的，没有依赖关系的字母看做单个的节点。可以添加一个指向所有
字母的辅助节点，然后从它开始DFS
【在 i**********e 的大作中提到】
: 从你那个例子：
: "it is a good day today"
: 可以建个链表，t->s, i->a->g->d->t
: 然后 merge 成：i->a->g->d->t->s
: 怎么打印所有 alphabetical order 的可能性如果只有一个链表写个 dfs 就好了.
: 但如果是这样的情况似乎很复杂啊:
: c->a, s->b->a
: 这题是不是要有对图论有很深的知识才能答出来？
: 还是有一些 trick 在里面？
: 这里有介绍 DAG 的算法：
|
b*********n
发帖数: 1258 | 12 this is toplogical sort, isn't it?
【在 f*********i 的大作中提到】
: 一个arraylist,里面有很多string,它们按照未知的alphabetical顺序排列,要求输出所
: 有可能的alphabetical order,(后来又问了如何判断是否有conflict)
: 例子:it is a good day today,
: it: is: a: good: day: 我觉得有两个难点,一个是如何把多个一一对应的大小关系merge,另一个是如何输出所
: 有的可能组合....30分钟实在是不够阿....算了,move on了.
|
h*********n
发帖数: 11319 | 13 看看我的方法行不？
【在 d*******l 的大作中提到】
: 最后图可能是不连通的，没有依赖关系的字母看做单个的节点。可以添加一个指向所有
: 字母的辅助节点，然后从它开始DFS
|
g***s
发帖数: 3811 | 14 yes. that's right. 其实就是始终遍历度为0的点。
【在 h*********n 的大作中提到】
: 看看我的方法行不？
|
g**u
发帖数: 583 | 15
请问：
如果同时有2个或者2个以上的node的inDeg是0的话，怎样可以保证输出了所有可能的组
合呢？
谢谢
【在 h*********n 的大作中提到】
: 所有能判断顺序的字母之间连上一条有向边，最后会生成一个dag，然后
: void printAllOrders(graph G, string order){
: if（G not empty）{
: for each node in G{
: if(node.inDeg==0){
: G.delete(node)；
: order.append(node);
: printAllOrders(G, order);
: G.addback(node);//together with deleted edges
: }
|
g**u
发帖数: 583 | 16
大牛， 讲讲为什么可以产生所有的合法的组合， 谢了
【在 g***s 的大作中提到】
: yes. that's right. 其实就是始终遍历度为0的点。
|
g*****k
发帖数: 623 | 17 对所有的inDeg是0的点依次枚举啊，这样就保证所有的可能。
【在 g**u 的大作中提到】
:
: 大牛， 讲讲为什么可以产生所有的合法的组合， 谢了
|
v*s
发帖数: 946 | 18 貌似topological sort只会输出一种可能的排列。
【在 b*********n 的大作中提到】
: this is toplogical sort, isn't it?
|
h*********n
发帖数: 11319 | 19 that's the point of undo the deletion and recurse next point with inDeg = 0
【在 v*s 的大作中提到】
: 貌似topological sort只会输出一种可能的排列。
|
g**u
发帖数: 583 | 20
0
还有个问题没有解决啊， 你的node_inDeg=0的node所组成的集合没有更新
还有， 没看明白 你说的 “每个list按顺序concatenate，每个list内部随便排列”
可以详细说一下么？
谢了
【在 h*********n 的大作中提到】
: that's the point of undo the deletion and recurse next point with inDeg = 0
|
|
|
g***s
发帖数: 3811 | 21 删除点的时候更新这个集合。
他那句话我也没有明白。但整个算法是对的。基于拓扑排序的的方法。
【在 g**u 的大作中提到】
:
: 0
: 还有个问题没有解决啊， 你的node_inDeg=0的node所组成的集合没有更新
: 还有， 没看明白 你说的 “每个list按顺序concatenate，每个list内部随便排列”
: 可以详细说一下么？
: 谢了
|
g**u
发帖数: 583 | 22
还是有一点不明白，比如说有下面一个简单的 图
1-》2
1-》3
2-》4
3-》4
有2个排列：
1 2 3 4或者 1 3 2 4
比较纠结的是
在那个算法里面 输出 1 2 3 4之后，如何回退到 1 3 2这个状态呢？
谢谢
【在 g***s 的大作中提到】
: 删除点的时候更新这个集合。
: 他那句话我也没有明白。但整个算法是对的。基于拓扑排序的的方法。
|
g***s
发帖数: 3811 | 23 去掉1以后，变成
2-》4
3-》4
所以在第二层上，度为0的点是2，3。分别遍历，所以就是
1，2，3，4
1，3，2，4
【在 g**u 的大作中提到】
:
: 还是有一点不明白，比如说有下面一个简单的 图
: 1-》2
: 1-》3
: 2-》4
: 3-》4
: 有2个排列：
: 1 2 3 4或者 1 3 2 4
: 比较纠结的是
: 在那个算法里面 输出 1 2 3 4之后，如何回退到 1 3 2这个状态呢？
|
o*****e
发帖数: 99 | 24 问题的关键是每当前面单词选定一个字母，后面就不能重复了。
（不知道相邻单词能不能取同一个字母，假设不能）
那就是一个不复杂的递归问题了。
My pseudo code,
String array size n
S0 ~ Sn-1
Output out[0 ~ n-1]
void func(S[], out[], k) {
if (k==n) {
print(out);
return;
}
for(i in 0 ~ strlen(S[k]-1){
if (S[k][i] not in Out[0 ~ k-1]) {
out[k] = S[k][i];
func(S, out, k+1);
}
}
}
main:
func(S, out, 0)
How to design efficiency algorithm to find whether
char S[k][i] is in string Out[0 ~ k-1]
A simple hash map should do it. |
h*********n
发帖数: 11319 | 25 那句话是错的。。。忽略之就可以了
=
【在 g**u 的大作中提到】
:
: 还是有一点不明白，比如说有下面一个简单的 图
: 1-》2
: 1-》3
: 2-》4
: 3-》4
: 有2个排列：
: 1 2 3 4或者 1 3 2 4
: 比较纠结的是
: 在那个算法里面 输出 1 2 3 4之后，如何回退到 1 3 2这个状态呢？
|
k****n
发帖数: 369 | 26
一个比较显然的结论是，首字母是按照递增序排列的，所以你两两看就是给自己增加混
乱了
直接应该就写出来
i
然后考察有相同prefix的string，把它们确定的关系insert到上面的序列里面
像上面就是
i
应该可以recursive的做
【在 f*********i 的大作中提到】
: 一个arraylist,里面有很多string,它们按照未知的alphabetical顺序排列,要求输出所
: 有可能的alphabetical order,(后来又问了如何判断是否有conflict)
: 例子:it is a good day today,
: it: is: a: good: day: 我觉得有两个难点,一个是如何把多个一一对应的大小关系merge,另一个是如何输出所
: 有的可能组合....30分钟实在是不够阿....算了,move on了.
|
g***s
发帖数: 3811 | 27 I could not understand what you said.
"it is A"
t < s
i < A
then?
【在 k****n 的大作中提到】
:
: 一个比较显然的结论是，首字母是按照递增序排列的，所以你两两看就是给自己增加混
: 乱了
: 直接应该就写出来
: i: 然后考察有相同prefix的string，把它们确定的关系insert到上面的序列里面
: 像上面就是
: i: 应该可以recursive的做
|
f*********i
发帖数: 197 | 28 一个arraylist,里面有很多string,它们按照未知的alphabetical顺序排列,要求输出所
有可能的alphabetical order,(后来又问了如何判断是否有conflict)
例子:it is a good day today,
it
is
a
good
day
我觉得有两个难点,一个是如何把多个一一对应的大小关系merge,另一个是如何输出所
有的可能组合....30分钟实在是不够阿....算了,move on了.
期待高人解答. |
g**e
发帖数: 6127 | 29 没看懂输出的是什么...
【在 f*********i 的大作中提到】
: 一个arraylist,里面有很多string,它们按照未知的alphabetical顺序排列,要求输出所
: 有可能的alphabetical order,(后来又问了如何判断是否有conflict)
: 例子:it is a good day today,
: it: is: a: good: day: 我觉得有两个难点,一个是如何把多个一一对应的大小关系merge,另一个是如何输出所
: 有的可能组合....30分钟实在是不够阿....算了,move on了.
|
g*****k
发帖数: 623 | 30 Build a tree?
If it is DAG, then no conflict and then do the DFS to output the topological
order?
【在 f*********i 的大作中提到】
: 一个arraylist,里面有很多string,它们按照未知的alphabetical顺序排列,要求输出所
: 有可能的alphabetical order,(后来又问了如何判断是否有conflict)
: 例子:it is a good day today,
: it: is: a: good: day: 我觉得有两个难点,一个是如何把多个一一对应的大小关系merge,另一个是如何输出所
: 有的可能组合....30分钟实在是不够阿....算了,move on了.
|
|
|
g*****k
发帖数: 623 | 31 貌似输出所有的排序，因为是partial order所以有很多种?
没看懂输出的是什么...
【在 g**e 的大作中提到】
: 没看懂输出的是什么...
|
g*****k
发帖数: 623 | 32 and if you want all orders, then permute all children and get different DFS
topological
【在 g*****k 的大作中提到】
: Build a tree?
: If it is DAG, then no conflict and then do the DFS to output the topological
: order?
|
h*********n
发帖数: 11319 | 33 所有能判断顺序的字母之间连上一条有向边，最后会生成一个dag，然后
void printAllOrders(graph G, string order){
if（G not empty）{
for each node in G{
if(node.inDeg==0){
G.delete(node)；
order.append(node);
printAllOrders(G, order);
G.addback(node);//together with deleted edges
}
}
}
else
print order
}
printAllOrders(graph G, "");
【在 f*********i 的大作中提到】
: 一个arraylist,里面有很多string,它们按照未知的alphabetical顺序排列,要求输出所
: 有可能的alphabetical order,(后来又问了如何判断是否有conflict)
: 例子:it is a good day today,
: it: is: a: good: day: 我觉得有两个难点,一个是如何把多个一一对应的大小关系merge,另一个是如何输出所
: 有的可能组合....30分钟实在是不够阿....算了,move on了.
|
r*******y
发帖数: 1081 | 34 bless
onsite到底是全面考察 problem solving 的能力
还是全面考察你是否能融入到这个team的能力？
【在 f*********i 的大作中提到】
: 一个arraylist,里面有很多string,它们按照未知的alphabetical顺序排列,要求输出所
: 有可能的alphabetical order,(后来又问了如何判断是否有conflict)
: 例子:it is a good day today,
: it: is: a: good: day: 我觉得有两个难点,一个是如何把多个一一对应的大小关系merge,另一个是如何输出所
: 有的可能组合....30分钟实在是不够阿....算了,move on了.
|
i**********e
发帖数: 1145 | 35 从你那个例子：
"it is a good day today"
可以建个链表，t->s, i->a->g->d->t
然后 merge 成：i->a->g->d->t->s
怎么打印所有 alphabetical order 的可能性如果只有一个链表写个 dfs 就好了.
但如果是这样的情况似乎很复杂啊:
c->a, s->b->a
这题是不是要有对图论有很深的知识才能答出来？
还是有一些 trick 在里面？
这里有介绍 DAG 的算法：
http://allisons.org/ll/AlgDS/Graph/DAG/
一些常见面试题的答案与总结 -
http://www.ihas1337code.com
【在 f*********i 的大作中提到】
: 一个arraylist,里面有很多string,它们按照未知的alphabetical顺序排列,要求输出所
: 有可能的alphabetical order,(后来又问了如何判断是否有conflict)
: 例子:it is a good day today,
: it: is: a: good: day: 我觉得有两个难点,一个是如何把多个一一对应的大小关系merge,另一个是如何输出所
: 有的可能组合....30分钟实在是不够阿....算了,move on了.
|
b**********2
发帖数: 1923 | 36 btw, how do u know u are rejected? does the recruiter contact u and tell u
that u are rejected? how many days after ur onsite?
【在 f*********i 的大作中提到】
: 一个arraylist,里面有很多string,它们按照未知的alphabetical顺序排列,要求输出所
: 有可能的alphabetical order,(后来又问了如何判断是否有conflict)
: 例子:it is a good day today,
: it: is: a: good: day: 我觉得有两个难点,一个是如何把多个一一对应的大小关系merge,另一个是如何输出所
: 有的可能组合....30分钟实在是不够阿....算了,move on了.
|
f*********i
发帖数: 197 | 37 两个星期没有消息,发信HR,被拒了. 发现google只要onsite后一个星期不联系你,大部
分情况就黄了.
DAG的方法好像也不太行阿,我当时就是说从图的角度来找所有可能性.他们一直纠结于
图的起点问题,我回答说所有的节点都有一个出度和一个入度,任意一个入度为0的节点
都可以作为开始节点,他们不满意.
还有,当merge的时候是要输出所有的可能,这个基本上是O(n^2)的复杂度,因为两个
independent的链表merge有up to N^2种可能,同时还要考虑他们是否部分重合.
到现在回想起来都是一头汗..... |
d*******l
发帖数: 338 | 38 最后图可能是不连通的，没有依赖关系的字母看做单个的节点。可以添加一个指向所有
字母的辅助节点，然后从它开始DFS
【在 i**********e 的大作中提到】
: 从你那个例子：
: "it is a good day today"
: 可以建个链表，t->s, i->a->g->d->t
: 然后 merge 成：i->a->g->d->t->s
: 怎么打印所有 alphabetical order 的可能性如果只有一个链表写个 dfs 就好了.
: 但如果是这样的情况似乎很复杂啊:
: c->a, s->b->a
: 这题是不是要有对图论有很深的知识才能答出来？
: 还是有一些 trick 在里面？
: 这里有介绍 DAG 的算法：
|
b*********n
发帖数: 1258 | 39 this is toplogical sort, isn't it?
【在 f*********i 的大作中提到】
: 一个arraylist,里面有很多string,它们按照未知的alphabetical顺序排列,要求输出所
: 有可能的alphabetical order,(后来又问了如何判断是否有conflict)
: 例子:it is a good day today,
: it: is: a: good: day: 我觉得有两个难点,一个是如何把多个一一对应的大小关系merge,另一个是如何输出所
: 有的可能组合....30分钟实在是不够阿....算了,move on了.
|
h*********n
发帖数: 11319 | 40 看看我的方法行不？
【在 d*******l 的大作中提到】
: 最后图可能是不连通的，没有依赖关系的字母看做单个的节点。可以添加一个指向所有
: 字母的辅助节点，然后从它开始DFS
|
|
|
g***s
发帖数: 3811 | 41 yes. that's right. 其实就是始终遍历度为0的点。
【在 h*********n 的大作中提到】
: 看看我的方法行不？
|
g**u
发帖数: 583 | 42
请问：
如果同时有2个或者2个以上的node的inDeg是0的话，怎样可以保证输出了所有可能的组
合呢？
谢谢
【在 h*********n 的大作中提到】
: 所有能判断顺序的字母之间连上一条有向边，最后会生成一个dag，然后
: void printAllOrders(graph G, string order){
: if（G not empty）{
: for each node in G{
: if(node.inDeg==0){
: G.delete(node)；
: order.append(node);
: printAllOrders(G, order);
: G.addback(node);//together with deleted edges
: }
|
g**u
发帖数: 583 | 43
大牛， 讲讲为什么可以产生所有的合法的组合， 谢了
【在 g***s 的大作中提到】
: yes. that's right. 其实就是始终遍历度为0的点。
|
g*****k
发帖数: 623 | 44 对所有的inDeg是0的点依次枚举啊，这样就保证所有的可能。
【在 g**u 的大作中提到】
:
: 大牛， 讲讲为什么可以产生所有的合法的组合， 谢了
|
h*********n
发帖数: 11319 | 45 that's the point of undo the deletion and recurse next point with inDeg = 0
【在 v*s 的大作中提到】
: 貌似topological sort只会输出一种可能的排列。
|
g**u
发帖数: 583 | 46
0
还有个问题没有解决啊， 你的node_inDeg=0的node所组成的集合没有更新
还有， 没看明白 你说的 “每个list按顺序concatenate，每个list内部随便排列”
可以详细说一下么？
谢了
【在 h*********n 的大作中提到】
: that's the point of undo the deletion and recurse next point with inDeg = 0
|
g***s
发帖数: 3811 | 47 删除点的时候更新这个集合。
他那句话我也没有明白。但整个算法是对的。基于拓扑排序的的方法。
【在 g**u 的大作中提到】
:
: 0
: 还有个问题没有解决啊， 你的node_inDeg=0的node所组成的集合没有更新
: 还有， 没看明白 你说的 “每个list按顺序concatenate，每个list内部随便排列”
: 可以详细说一下么？
: 谢了
|
g**u
发帖数: 583 | 48
还是有一点不明白，比如说有下面一个简单的 图
1-》2
1-》3
2-》4
3-》4
有2个排列：
1 2 3 4或者 1 3 2 4
比较纠结的是
在那个算法里面 输出 1 2 3 4之后，如何回退到 1 3 2这个状态呢？
谢谢
【在 g***s 的大作中提到】
: 删除点的时候更新这个集合。
: 他那句话我也没有明白。但整个算法是对的。基于拓扑排序的的方法。
|
g***s
发帖数: 3811 | 49 去掉1以后，变成
2-》4
3-》4
所以在第二层上，度为0的点是2，3。分别遍历，所以就是
1，2，3，4
1，3，2，4
【在 g**u 的大作中提到】
:
: 还是有一点不明白，比如说有下面一个简单的 图
: 1-》2
: 1-》3
: 2-》4
: 3-》4
: 有2个排列：
: 1 2 3 4或者 1 3 2 4
: 比较纠结的是
: 在那个算法里面 输出 1 2 3 4之后，如何回退到 1 3 2这个状态呢？
|
o*****e
发帖数: 99 | 50 问题的关键是每当前面单词选定一个字母，后面就不能重复了。
（不知道相邻单词能不能取同一个字母，假设不能）
那就是一个不复杂的递归问题了。
My pseudo code,
String array size n
S0 ~ Sn-1
Output out[0 ~ n-1]
void func(S[], out[], k) {
if (k==n) {
print(out);
return;
}
for(i in 0 ~ strlen(S[k]-1){
if (S[k][i] not in Out[0 ~ k-1]) {
out[k] = S[k][i];
func(S, out, k+1);
}
}
}
main:
func(S, out, 0)
How to design efficiency algorithm to find whether
char S[k][i] is in string Out[0 ~ k-1]
A simple hash map should do it. |
|
|
h*********n
发帖数: 11319 | 51 那句话是错的。。。忽略之就可以了
=
【在 g**u 的大作中提到】
:
: 还是有一点不明白，比如说有下面一个简单的 图
: 1-》2
: 1-》3
: 2-》4
: 3-》4
: 有2个排列：
: 1 2 3 4或者 1 3 2 4
: 比较纠结的是
: 在那个算法里面 输出 1 2 3 4之后，如何回退到 1 3 2这个状态呢？
|
k****n
发帖数: 369 | 52
一个比较显然的结论是，首字母是按照递增序排列的，所以你两两看就是给自己增加混
乱了
直接应该就写出来
i
然后考察有相同prefix的string，把它们确定的关系insert到上面的序列里面
像上面就是
i
应该可以recursive的做
【在 f*********i 的大作中提到】
: 一个arraylist,里面有很多string,它们按照未知的alphabetical顺序排列,要求输出所
: 有可能的alphabetical order,(后来又问了如何判断是否有conflict)
: 例子:it is a good day today,
: it: is: a: good: day: 我觉得有两个难点,一个是如何把多个一一对应的大小关系merge,另一个是如何输出所
: 有的可能组合....30分钟实在是不够阿....算了,move on了.
|
g***s
发帖数: 3811 | 53 I could not understand what you said.
"it is A"
t < s
i < A
then?
【在 k****n 的大作中提到】
:
: 一个比较显然的结论是，首字母是按照递增序排列的，所以你两两看就是给自己增加混
: 乱了
: 直接应该就写出来
: i: 然后考察有相同prefix的string，把它们确定的关系insert到上面的序列里面
: 像上面就是
: i: 应该可以recursive的做
|
r*******g
发帖数: 1335 | 54 没看懂题，输出难道不是一个整体的string？
【在 f*********i 的大作中提到】
: 一个arraylist,里面有很多string,它们按照未知的alphabetical顺序排列,要求输出所
: 有可能的alphabetical order,(后来又问了如何判断是否有conflict)
: 例子:it is a good day today,
: it: is: a: good: day: 我觉得有两个难点,一个是如何把多个一一对应的大小关系merge,另一个是如何输出所
: 有的可能组合....30分钟实在是不够阿....算了,move on了.
|
q****x
发帖数: 7404 | 55 这题写代码有点二逼。
【在 f*********i 的大作中提到】
: 一个arraylist,里面有很多string,它们按照未知的alphabetical顺序排列,要求输出所
: 有可能的alphabetical order,(后来又问了如何判断是否有conflict)
: 例子:it is a good day today,
: it: is: a: good: day: 我觉得有两个难点,一个是如何把多个一一对应的大小关系merge,另一个是如何输出所
: 有的可能组合....30分钟实在是不够阿....算了,move on了.
|
B*******1
发帖数: 2454 | 56 还好吧？ 建图，然后topsort。
比版上那哥们电话phone就要写word ladder的好多了吧。
【在 q****x 的大作中提到】
: 这题写代码有点二逼。
|
g***x
发帖数: 494 | 57 你算法的主要思想是topsort+backtracking来打印出所有的topsort的可能性。我的理
解对吗？
【在 h*********n 的大作中提到】
: 所有能判断顺序的字母之间连上一条有向边，最后会生成一个dag，然后
: void printAllOrders(graph G, string order){
: if（G not empty）{
: for each node in G{
: if(node.inDeg==0){
: G.delete(node)；
: order.append(node);
: printAllOrders(G, order);
: G.addback(node);//together with deleted edges
: }
|
B*******1
发帖数: 2454 | 58 哪里看出backtracking啊？
就是topsort吧。
【在 g***x 的大作中提到】
: 你算法的主要思想是topsort+backtracking来打印出所有的topsort的可能性。我的理
: 解对吗？
|
c*******n
发帖数: 72 | 59
哪里看出backtracking啊？就是topsort吧。
★ Sent from iPhone App: iReader Mitbbs 7.28 - iPad Lite
【在 B*******1 的大作中提到】
: 哪里看出backtracking啊？
: 就是topsort吧。
|
e*****m
发帖数: 171 | 60 void printAllOrders(graph G, string order){
if（G not empty）{
for each node in G{
if(node.inDeg==0){
G.delete(node)；
order.append(node); //请问这一句是不是有错啊？我觉得
应该是删掉这一句，并在下一句中写printAllOrders(G,order+node.toString()), 否则
order不是
一直在append，越来越长么(假设是java，按引用传递)
printAllOrders(G, order);
G.addback(node);//together with deleted edges
}
}
}
else
print order
}
printAllOrders(graph G, ""); |
|
|
w****x
发帖数: 2483 | 61 void MarkMap(const char* szStrs[], int n, int nBegIndex, bool chrMap[26][26])
{
assert(szStrs && nBegIndex >= 0 && n >= 0);
if (n <= 1) return;
int nDiv = -1;
for (int i = 0; i < n-1; i++)
{
char tmp1 = *(szStrs[i] + nBegIndex);
char tmp2 = *(szStrs[i+1] + nBegIndex);
assert(((tmp1 >= 'a' && tmp1 <= 'z') || tmp1 == 0));
assert(((tmp2 >= 'a' && tmp2 <= 'z') || tmp2 == 0));
if (tmp1 != 0 && nDiv < 0)
nDiv = i;
if (tmp1 == 0 || tmp1 == tmp2)
continue;
MarkMap(szStrs + nDiv, i + 1 - nDiv, nBegIndex + 1, chrMap);
nDiv = i+1;
chrMap[tmp1 - 'a'][tmp2 - 'a'] = true;
}
MarkMap(szStrs + nDiv, n - nDiv, nBegIndex + 1, chrMap);
}
void PrintComb(bool bRec[26], bool chrMap[26][26], char szTmp[26], int nBeg)
{
if (nBeg == 26)
{
for (int i = 0; i < 26; i++)
cout<
cout<
return;
}
for (int i = 0; i < 26; i++)
{
if (bRec[i])
continue;
int j = 0;
for (; j < 26; j++)
{
if (!bRec[j] && chrMap[j][i])
break;
}
if (j >= 26)
{
bRec[i] = true;
szTmp[nBeg] = 'a' + i;
PrintComb(bRec, chrMap, szTmp, nBeg + 1);
bRec[i] = false;
}
}
}
void PrintAllPossible(const char* szStrs[], int n)
{
assert(szStrs && n > 0);
bool chrMap[26][26];
memset(chrMap, 0, sizeof(chrMap));
MarkMap(szStrs, n, 0, chrMap);
bool bRec[26];
memset(bRec, 0, sizeof(bRec));
char szTmp[26];
PrintComb(bRec, chrMap, szTmp, 0);
} |
w****x
发帖数: 2483 | 62 这题如果叫你在半小时内写出代码你可以给那个面试官说:
FUCK OFF !!!!!!!!!!! |
f*******t
发帖数: 7549 | 63 对于搞ACM竞赛的人这种题半小时写出差不多的代码应该没压力。。
【在 w****x 的大作中提到】
: 这题如果叫你在半小时内写出代码你可以给那个面试官说:
: FUCK OFF !!!!!!!!!!!
|
y***d
发帖数: 2330 | 64 阿，似乎不难，我是不是申请一下 google...
【在 f*********i 的大作中提到】
: 一个arraylist,里面有很多string,它们按照未知的alphabetical顺序排列,要求输出所
: 有可能的alphabetical order,(后来又问了如何判断是否有conflict)
: 例子:it is a good day today,
: it: is: a: good: day: 我觉得有两个难点,一个是如何把多个一一对应的大小关系merge,另一个是如何输出所
: 有的可能组合....30分钟实在是不够阿....算了,move on了.
|
w****x
发帖数: 2483 | 65 不信没压力, 我第二次写28分钟, 第二次那可是有了思路和知道了所有要注意的地方的
情况下呀~~ 这题30分钟要求code出来是不是要求太过了, 明显是刁难, 伪代码或讲思
路还差不多 |
