r******n 发帖数: 170 | 1 Given a set of Social Network Users, for each two users: A follows B or B
follows A or A and B follow each other
Now sort the Users in the following order:
A->B->C->D
satisfying two requirements:
1. each User only show once in the list
2. A must follow B if A appears before B in the output list: A->B->C->D.
It doesn't matter if they are not adjacent to each other in the list.
我面试时说这样子的path不一定unique吧,面试官说任意一条都行。然后,我也没法简
单证明这样子的path必定存在。 |
f*******r 发帖数: 1086 | 2 这个应该就是有了graph结构之后做topological sorting吧,
但凡解决事件或者节点的先后顺序的时候,都可能和topological sorting相关。 |
l****i 发帖数: 2772 | 3 A and B follow each other
这种情况,拓扑排序不是有环了么 |
l***i 发帖数: 1309 | 4 Looks like proof by induction will show it. And the induction step works
like insertion sort.
In the example, after we have
A -> B -> C
then D comes. if C -> D, then A->B->C->D is a solution.
else we have D->C
then if B->D, we can use A->B->D->C
else we have D->B
now check A and D, either A->D or D->A,
we can use A->D->B->C if A->D, or use D->A->B->C if D->A. |
r******n 发帖数: 170 | 5 我当时也是这么想的,说做toposort,indegree最小的node作为起点,后来发现
toposort不太适用。
【在 f*******r 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 这个应该就是有了graph结构之后做topological sorting吧, : 但凡解决事件或者节点的先后顺序的时候,都可能和topological sorting相关。
|
P******r 发帖数: 1342 | |
l*********8 发帖数: 4642 | 7 step1: 首先从indegree最小的user开始。
step2: 把上一个user从图中删除; 在当前user follow的users中,选取indegree最小
者为下一个user.
repeat step2 until all users are visited.
【在 r******n 的大作中提到】![](/moin_static193/solenoid/img/up.png) : Given a set of Social Network Users, for each two users: A follows B or B : follows A or A and B follow each other : Now sort the Users in the following order: : A->B->C->D : satisfying two requirements: : 1. each User only show once in the list : 2. A must follow B if A appears before B in the output list: A->B->C->D. : It doesn't matter if they are not adjacent to each other in the list. : 我面试时说这样子的path不一定unique吧,面试官说任意一条都行。然后,我也没法简 : 单证明这样子的path必定存在。
|
e***l 发帖数: 710 | 8 其实就是给了偏序关系。sort 函数加个comparator就行了。自己写的话可用任意基于
比较的排序算法。
看过算法导论的可以进一步给出这个算法的下界是nlgn, 面试官估计就完全满意了 |
e***l 发帖数: 710 | 9 这显然错了。前面的插入排序可以
【在 l*********8 的大作中提到】![](/moin_static193/solenoid/img/up.png) : step1: 首先从indegree最小的user开始。 : step2: 把上一个user从图中删除; 在当前user follow的users中,选取indegree最小 : 者为下一个user. : repeat step2 until all users are visited.
|
l*********8 发帖数: 4642 | 10 偏序的排序是拓扑排序, 不能用sort函数吧?
而拓扑排序的结果不一定符合本题的要求。
【在 e***l 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 其实就是给了偏序关系。sort 函数加个comparator就行了。自己写的话可用任意基于 : 比较的排序算法。 : 看过算法导论的可以进一步给出这个算法的下界是nlgn, 面试官估计就完全满意了
|
|
|
l*********8 发帖数: 4642 | 11 这个算法是清晰可行的。
时间复杂度O(n^2)
【在 l***i 的大作中提到】![](/moin_static193/solenoid/img/up.png) : Looks like proof by induction will show it. And the induction step works : like insertion sort. : In the example, after we have : A -> B -> C : then D comes. if C -> D, then A->B->C->D is a solution. : else we have D->C : then if B->D, we can use A->B->D->C : else we have D->B : now check A and D, either A->D or D->A, : we can use A->D->B->C if A->D, or use D->A->B->C if D->A.
|
f******t 发帖数: 18 | 12 2. A must follow B if A appears before B in the output list: A->B->C->D.
我的理解是,如果A,B之间互相follow,那么A,B最后的顺序无论A在前还是B在前都是
对的。
这样的话,把所有互相follow的关系去掉(A->B和B->A两条边都删除),然后做拓扑排
序就是结果吧。有环则无解。 |
l*********8 发帖数: 4642 | 13 另外,这个不是偏序关系。 不满足反对称性。
【在 e***l 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 其实就是给了偏序关系。sort 函数加个comparator就行了。自己写的话可用任意基于 : 比较的排序算法。 : 看过算法导论的可以进一步给出这个算法的下界是nlgn, 面试官估计就完全满意了
|
S******1 发帖数: 216 | 14 List getOrder(Map> graph) {
List res = new ArrayList();
if (graph == null || graph.isEmpty())
return res;
Set traveled = new HashSet();
Iterator it = graph.keyset().iterator();
while (it.hasNext()) {
int id = it.next();
if (!traveled.contains(id)) {
getOrderHelper(id, graph, traveled, res);
}
}
Collections.reverse(res);
return res;
}
void getOrderHelper(int id, Map> graph, Set
traveled, List res) {
traveled.add(id);
if (graph.containsKey(id)) {
List followList = graph.get(id);
for (Integer fid : followList) {
if (!traveled.contains(fid)) {
getOrderHelper(fid, graph, traveled, res);
}
}
res.add(id);
}
} |
G***n 发帖数: 877 | 15 这题不是DFS吗?对每个节点search longest path,返回那个最长的path的所有节点不
就是sort了的序列吗? |
r******n 发帖数: 170 | 16 你这code错了吧,都没有维护traveled和res。
InDegree adjancy list:
A: [B, D]
B: [D]
C: [A, B, D]
D: []
Answer: D->B->A->C
InDegree adjancy list:
A: [B, C, D]
B: [C, D]
C: [A, B, D]
D: [C]
Answer: D->B->A->C/D->C->B->A
【在 S******1 的大作中提到】![](/moin_static193/solenoid/img/up.png) : List getOrder(Map> graph) { : List res = new ArrayList(); : if (graph == null || graph.isEmpty()) : return res; : : Set traveled = new HashSet(); : Iterator it = graph.keyset().iterator(); : while (it.hasNext()) { : int id = it.next(); : if (!traveled.contains(id)) {
|
x*********a 发帖数: 36 | 17 appear before 是指直接相邻么?
【在 r******n 的大作中提到】![](/moin_static193/solenoid/img/up.png) : Given a set of Social Network Users, for each two users: A follows B or B : follows A or A and B follow each other : Now sort the Users in the following order: : A->B->C->D : satisfying two requirements: : 1. each User only show once in the list : 2. A must follow B if A appears before B in the output list: A->B->C->D. : It doesn't matter if they are not adjacent to each other in the list. : 我面试时说这样子的path不一定unique吧,面试官说任意一条都行。然后,我也没法简 : 单证明这样子的path必定存在。
|