n7的3G板子# PDA - 掌中宝
f*i
1 楼
z*r
2 楼
是自己插sim卡的还是自带？突然想起来，俺可以换个3g板子，正好手上有个多余的sim
卡，只有出差的时候用，可以提高一下利用率，否则每个月$45刀白交了。
卡，只有出差的时候用，可以提高一下利用率，否则每个月$45刀白交了。
s*n
4 楼
你真有钱，花月费从来不用？
g*k
5 楼
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
: 有的可能组合....30分钟实在是不够阿....算了,move on了.
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
: 有的可能组合....30分钟实在是不够阿....算了,move on了.
z*r
6 楼
显然不是俺花钱啊，否则俺不吃饱了撑的
【在 s******n 的大作中提到】
: 你真有钱，花月费从来不用？
【在 s******n 的大作中提到】
: 你真有钱，花月费从来不用？
g*k
7 楼
貌似输出所有的排序，因为是partial order所以有很多种?
没看懂输出的是什么...
【在 g**e 的大作中提到】
: 没看懂输出的是什么...
没看懂输出的是什么...
【在 g**e 的大作中提到】
: 没看懂输出的是什么...
t*n
8 楼
太实在了。。。
【在 z**r 的大作中提到】
: 显然不是俺花钱啊，否则俺不吃饱了撑的
【在 z**r 的大作中提到】
: 显然不是俺花钱啊，否则俺不吃饱了撑的
g*k
9 楼
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?
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
10 楼
所有能判断顺序的字母之间连上一条有向边，最后会生成一个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
: 有的可能组合....30分钟实在是不够阿....算了,move on了.
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
: 有的可能组合....30分钟实在是不够阿....算了,move on了.
r*y
11 楼
bless
onsite到底是全面考察 problem solving 的能力
还是全面考察你是否能融入到这个team的能力？
【在 f*********i 的大作中提到】
: 一个arraylist,里面有很多string,它们按照未知的alphabetical顺序排列,要求输出所
: 有可能的alphabetical order,(后来又问了如何判断是否有conflict)
: 例子:it is a good day today,
: it
: 有的可能组合....30分钟实在是不够阿....算了,move on了.
onsite到底是全面考察 problem solving 的能力
还是全面考察你是否能融入到这个team的能力？
【在 f*********i 的大作中提到】
: 一个arraylist,里面有很多string,它们按照未知的alphabetical顺序排列,要求输出所
: 有可能的alphabetical order,(后来又问了如何判断是否有conflict)
: 例子:it is a good day today,
: it
: 有的可能组合....30分钟实在是不够阿....算了,move on了.
i*e
12 楼
从你那个例子：
"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
: 有的可能组合....30分钟实在是不够阿....算了,move on了.
"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
: 有的可能组合....30分钟实在是不够阿....算了,move on了.
b*2
13 楼
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
: 有的可能组合....30分钟实在是不够阿....算了,move on了.
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
: 有的可能组合....30分钟实在是不够阿....算了,move on了.
f*i
14 楼
两个星期没有消息,发信HR,被拒了. 发现google只要onsite后一个星期不联系你,大部
分情况就黄了.
DAG的方法好像也不太行阿,我当时就是说从图的角度来找所有可能性.他们一直纠结于
图的起点问题,我回答说所有的节点都有一个出度和一个入度,任意一个入度为0的节点
都可以作为开始节点,他们不满意.
还有,当merge的时候是要输出所有的可能,这个基本上是O(n^2)的复杂度,因为两个
independent的链表merge有up to N^2种可能,同时还要考虑他们是否部分重合.
到现在回想起来都是一头汗.....
分情况就黄了.
DAG的方法好像也不太行阿,我当时就是说从图的角度来找所有可能性.他们一直纠结于
图的起点问题,我回答说所有的节点都有一个出度和一个入度,任意一个入度为0的节点
都可以作为开始节点,他们不满意.
还有,当merge的时候是要输出所有的可能,这个基本上是O(n^2)的复杂度,因为两个
independent的链表merge有up to N^2种可能,同时还要考虑他们是否部分重合.
到现在回想起来都是一头汗.....
d*l
15 楼
最后图可能是不连通的，没有依赖关系的字母看做单个的节点。可以添加一个指向所有
字母的辅助节点，然后从它开始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 的算法：
字母的辅助节点，然后从它开始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 的算法：
h*n
17 楼
看看我的方法行不？
【在 d*******l 的大作中提到】
: 最后图可能是不连通的，没有依赖关系的字母看做单个的节点。可以添加一个指向所有
: 字母的辅助节点，然后从它开始DFS
【在 d*******l 的大作中提到】
: 最后图可能是不连通的，没有依赖关系的字母看做单个的节点。可以添加一个指向所有
: 字母的辅助节点，然后从它开始DFS
g*s
18 楼
yes. that's right. 其实就是始终遍历度为0的点。
【在 h*********n 的大作中提到】
: 看看我的方法行不？
【在 h*********n 的大作中提到】
: 看看我的方法行不？
g*u
19 楼
请问：
如果同时有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
20 楼
大牛， 讲讲为什么可以产生所有的合法的组合， 谢了
【在 g***s 的大作中提到】
: yes. that's right. 其实就是始终遍历度为0的点。
g*k
21 楼
对所有的inDeg是0的点依次枚举啊，这样就保证所有的可能。
【在 g**u 的大作中提到】
:
: 大牛， 讲讲为什么可以产生所有的合法的组合， 谢了
【在 g**u 的大作中提到】
:
: 大牛， 讲讲为什么可以产生所有的合法的组合， 谢了
v*s
22 楼
貌似topological sort只会输出一种可能的排列。
【在 b*********n 的大作中提到】
: this is toplogical sort, isn't it?
【在 b*********n 的大作中提到】
: this is toplogical sort, isn't it?
h*n
23 楼
that's the point of undo the deletion and recurse next point with inDeg = 0
【在 v*s 的大作中提到】
: 貌似topological sort只会输出一种可能的排列。
【在 v*s 的大作中提到】
: 貌似topological sort只会输出一种可能的排列。
g*u
24 楼
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
25 楼
删除点的时候更新这个集合。
他那句话我也没有明白。但整个算法是对的。基于拓扑排序的的方法。
【在 g**u 的大作中提到】
:
: 0
: 还有个问题没有解决啊， 你的node_inDeg=0的node所组成的集合没有更新
: 还有， 没看明白 你说的 “每个list按顺序concatenate，每个list内部随便排列”
: 可以详细说一下么？
: 谢了
他那句话我也没有明白。但整个算法是对的。基于拓扑排序的的方法。
【在 g**u 的大作中提到】
:
: 0
: 还有个问题没有解决啊， 你的node_inDeg=0的node所组成的集合没有更新
: 还有， 没看明白 你说的 “每个list按顺序concatenate，每个list内部随便排列”
: 可以详细说一下么？
: 谢了
g*u
26 楼
还是有一点不明白，比如说有下面一个简单的 图
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
27 楼
去掉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这个状态呢？
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
28 楼
问题的关键是每当前面单词选定一个字母，后面就不能重复了。
（不知道相邻单词能不能取同一个字母，假设不能）
那就是一个不复杂的递归问题了。
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.
（不知道相邻单词能不能取同一个字母，假设不能）
那就是一个不复杂的递归问题了。
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
29 楼
那句话是错的。。。忽略之就可以了
=
【在 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这个状态呢？
=
【在 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
30 楼
一个比较显然的结论是，首字母是按照递增序排列的，所以你两两看就是给自己增加混
乱了
直接应该就写出来
i然后考察有相同prefix的string，把它们确定的关系insert到上面的序列里面
像上面就是
i应该可以recursive的做
【在 f*********i 的大作中提到】
: 一个arraylist,里面有很多string,它们按照未知的alphabetical顺序排列,要求输出所
: 有可能的alphabetical order,(后来又问了如何判断是否有conflict)
: 例子:it is a good day today,
: it
: 有的可能组合....30分钟实在是不够阿....算了,move on了.
g*k
34 楼
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
: 有的可能组合....30分钟实在是不够阿....算了,move on了.
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
: 有的可能组合....30分钟实在是不够阿....算了,move on了.
g*k
35 楼
貌似输出所有的排序，因为是partial order所以有很多种?
没看懂输出的是什么...
【在 g**e 的大作中提到】
: 没看懂输出的是什么...
没看懂输出的是什么...
【在 g**e 的大作中提到】
: 没看懂输出的是什么...
g*k
36 楼
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?
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
37 楼
所有能判断顺序的字母之间连上一条有向边，最后会生成一个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
: 有的可能组合....30分钟实在是不够阿....算了,move on了.
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
: 有的可能组合....30分钟实在是不够阿....算了,move on了.
r*y
38 楼
bless
onsite到底是全面考察 problem solving 的能力
还是全面考察你是否能融入到这个team的能力？
【在 f*********i 的大作中提到】
: 一个arraylist,里面有很多string,它们按照未知的alphabetical顺序排列,要求输出所
: 有可能的alphabetical order,(后来又问了如何判断是否有conflict)
: 例子:it is a good day today,
: it
: 有的可能组合....30分钟实在是不够阿....算了,move on了.
onsite到底是全面考察 problem solving 的能力
还是全面考察你是否能融入到这个team的能力？
【在 f*********i 的大作中提到】
: 一个arraylist,里面有很多string,它们按照未知的alphabetical顺序排列,要求输出所
: 有可能的alphabetical order,(后来又问了如何判断是否有conflict)
: 例子:it is a good day today,
: it
: 有的可能组合....30分钟实在是不够阿....算了,move on了.
i*e
39 楼
从你那个例子：
"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
: 有的可能组合....30分钟实在是不够阿....算了,move on了.
"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
: 有的可能组合....30分钟实在是不够阿....算了,move on了.
b*2
40 楼
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
: 有的可能组合....30分钟实在是不够阿....算了,move on了.
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
: 有的可能组合....30分钟实在是不够阿....算了,move on了.
f*i
41 楼
两个星期没有消息,发信HR,被拒了. 发现google只要onsite后一个星期不联系你,大部
分情况就黄了.
DAG的方法好像也不太行阿,我当时就是说从图的角度来找所有可能性.他们一直纠结于
图的起点问题,我回答说所有的节点都有一个出度和一个入度,任意一个入度为0的节点
都可以作为开始节点,他们不满意.
还有,当merge的时候是要输出所有的可能,这个基本上是O(n^2)的复杂度,因为两个
independent的链表merge有up to N^2种可能,同时还要考虑他们是否部分重合.
到现在回想起来都是一头汗.....
分情况就黄了.
DAG的方法好像也不太行阿,我当时就是说从图的角度来找所有可能性.他们一直纠结于
图的起点问题,我回答说所有的节点都有一个出度和一个入度,任意一个入度为0的节点
都可以作为开始节点,他们不满意.
还有,当merge的时候是要输出所有的可能,这个基本上是O(n^2)的复杂度,因为两个
independent的链表merge有up to N^2种可能,同时还要考虑他们是否部分重合.
到现在回想起来都是一头汗.....
d*l
42 楼
最后图可能是不连通的，没有依赖关系的字母看做单个的节点。可以添加一个指向所有
字母的辅助节点，然后从它开始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 的算法：
字母的辅助节点，然后从它开始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 的算法：
h*n
44 楼
看看我的方法行不？
【在 d*******l 的大作中提到】
: 最后图可能是不连通的，没有依赖关系的字母看做单个的节点。可以添加一个指向所有
: 字母的辅助节点，然后从它开始DFS
【在 d*******l 的大作中提到】
: 最后图可能是不连通的，没有依赖关系的字母看做单个的节点。可以添加一个指向所有
: 字母的辅助节点，然后从它开始DFS
g*s
45 楼
yes. that's right. 其实就是始终遍历度为0的点。
【在 h*********n 的大作中提到】
: 看看我的方法行不？
【在 h*********n 的大作中提到】
: 看看我的方法行不？
g*u
46 楼
请问：
如果同时有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
47 楼
大牛， 讲讲为什么可以产生所有的合法的组合， 谢了
【在 g***s 的大作中提到】
: yes. that's right. 其实就是始终遍历度为0的点。
g*k
48 楼
对所有的inDeg是0的点依次枚举啊，这样就保证所有的可能。
【在 g**u 的大作中提到】
:
: 大牛， 讲讲为什么可以产生所有的合法的组合， 谢了
【在 g**u 的大作中提到】
:
: 大牛， 讲讲为什么可以产生所有的合法的组合， 谢了
h*n
49 楼
that's the point of undo the deletion and recurse next point with inDeg = 0
【在 v*s 的大作中提到】
: 貌似topological sort只会输出一种可能的排列。
【在 v*s 的大作中提到】
: 貌似topological sort只会输出一种可能的排列。
g*u
50 楼
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
51 楼
删除点的时候更新这个集合。
他那句话我也没有明白。但整个算法是对的。基于拓扑排序的的方法。
【在 g**u 的大作中提到】
:
: 0
: 还有个问题没有解决啊， 你的node_inDeg=0的node所组成的集合没有更新
: 还有， 没看明白 你说的 “每个list按顺序concatenate，每个list内部随便排列”
: 可以详细说一下么？
: 谢了
他那句话我也没有明白。但整个算法是对的。基于拓扑排序的的方法。
【在 g**u 的大作中提到】
:
: 0
: 还有个问题没有解决啊， 你的node_inDeg=0的node所组成的集合没有更新
: 还有， 没看明白 你说的 “每个list按顺序concatenate，每个list内部随便排列”
: 可以详细说一下么？
: 谢了
g*u
52 楼
还是有一点不明白，比如说有下面一个简单的 图
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
53 楼
去掉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这个状态呢？
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
54 楼
问题的关键是每当前面单词选定一个字母，后面就不能重复了。
（不知道相邻单词能不能取同一个字母，假设不能）
那就是一个不复杂的递归问题了。
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.
（不知道相邻单词能不能取同一个字母，假设不能）
那就是一个不复杂的递归问题了。
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
55 楼
那句话是错的。。。忽略之就可以了
=
【在 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这个状态呢？
=
【在 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
56 楼
一个比较显然的结论是，首字母是按照递增序排列的，所以你两两看就是给自己增加混
乱了
直接应该就写出来
i然后考察有相同prefix的string，把它们确定的关系insert到上面的序列里面
像上面就是
i应该可以recursive的做
【在 f*********i 的大作中提到】
: 一个arraylist,里面有很多string,它们按照未知的alphabetical顺序排列,要求输出所
: 有可能的alphabetical order,(后来又问了如何判断是否有conflict)
: 例子:it is a good day today,
: it
: 有的可能组合....30分钟实在是不够阿....算了,move on了.
B*1
60 楼
还好吧？ 建图，然后topsort。
比版上那哥们电话phone就要写word ladder的好多了吧。
【在 q****x 的大作中提到】
: 这题写代码有点二逼。
比版上那哥们电话phone就要写word ladder的好多了吧。
【在 q****x 的大作中提到】
: 这题写代码有点二逼。
g*x
61 楼
你算法的主要思想是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
: }
解对吗？
【在 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
62 楼
哪里看出backtracking啊？
就是topsort吧。
【在 g***x 的大作中提到】
: 你算法的主要思想是topsort+backtracking来打印出所有的topsort的可能性。我的理
: 解对吗？
就是topsort吧。
【在 g***x 的大作中提到】
: 你算法的主要思想是topsort+backtracking来打印出所有的topsort的可能性。我的理
: 解对吗？
c*n
63 楼
哪里看出backtracking啊？就是topsort吧。
★ Sent from iPhone App: iReader Mitbbs 7.28 - iPad Lite
【在 B*******1 的大作中提到】
: 哪里看出backtracking啊？
: 就是topsort吧。
e*m
64 楼
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, "");
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
65 楼
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<
}
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);
}
{
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<
}
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
66 楼
这题如果叫你在半小时内写出代码你可以给那个面试官说:
FUCK OFF !!!!!!!!!!!
FUCK OFF !!!!!!!!!!!
f*t
67 楼
对于搞ACM竞赛的人这种题半小时写出差不多的代码应该没压力。。
【在 w****x 的大作中提到】
: 这题如果叫你在半小时内写出代码你可以给那个面试官说:
: FUCK OFF !!!!!!!!!!!
【在 w****x 的大作中提到】
: 这题如果叫你在半小时内写出代码你可以给那个面试官说:
: FUCK OFF !!!!!!!!!!!
w*x
69 楼
不信没压力, 我第二次写28分钟, 第二次那可是有了思路和知道了所有要注意的地方的
情况下呀~~ 这题30分钟要求code出来是不是要求太过了, 明显是刁难, 伪代码或讲思
路还差不多
情况下呀~~ 这题30分钟要求code出来是不是要求太过了, 明显是刁难, 伪代码或讲思
路还差不多
相关阅读
fire tv 启动沙发桌面的简单方法淘宝上的多功能行车记录仪靠谱吗？ (转载)求教，怎样可以看到微信电话的选项？Letv U3送的一年会员，有激活码这类的吗？下歌用啥啊？ringplus打国际电话谁弄过？发现这些年贬值最快的是纸质的书S版iphone5s解锁？chrome browser可以push notification了手机终极方案还是有50块左右的安卓板子推荐吗SURFboard SBG6782AC 怎么样？Exp Deals Hotel iOS App 正式上线 (半价订酒店 App)黑莓Priv现在299了，算deal不？$200一下，什么音响听中文流行音乐的效果最好今天ebay $15 off $75+置顶的老大电视盒子是不是比较老的型号乐视超级手机怎么样？lte band 还挺多fire tv stick 还是roku streaming stickios上那个app可以用Google calendar？