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 的大作中提到】
: 这个应该就是有了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 的大作中提到】
: 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 的大作中提到】
: step1: 首先从indegree最小的user开始。
: step2: 把上一个user从图中删除; 在当前user follow的users中，选取indegree最小
: 者为下一个user.
: repeat step2 until all users are visited.
|
l*********8
发帖数: 4642 | 10 偏序的排序是拓扑排序， 不能用sort函数吧？
而拓扑排序的结果不一定符合本题的要求。
【在 e***l 的大作中提到】
: 其实就是给了偏序关系。sort 函数加个comparator就行了。自己写的话可用任意基于
: 比较的排序算法。
: 看过算法导论的可以进一步给出这个算法的下界是nlgn, 面试官估计就完全满意了
|
|
|
l*********8
发帖数: 4642 | 11 这个算法是清晰可行的。
时间复杂度O(n^2)
【在 l***i 的大作中提到】
: 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 的大作中提到】
: 其实就是给了偏序关系。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 的大作中提到】
: 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 的大作中提到】
: 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必定存在。
|
