问个面试题 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

问个面试题

问个面试题# JobHunting - 待字闺中

c*h2013-09-05 07:09

1 楼

有很多pair，比如（a,b),(b,c),(a,c)。假设每个pair有依赖关系，a 依赖于b，b依赖
于c，a依赖于c。事实上（a,c)是多余的。现在要求剔除所有多余的pair。
现在只能想到构建个graph，然后找出所有loop，再断开它，接着遍历一篇。好像很复
杂，不知道有什么简单的方法来搞。。。

l*l2013-09-05 07:09

2 楼

放hashtable里面不停的删除？

d*k2013-09-05 07:09

3 楼

我说个暴利方法。
首先根据pair, 构建一个有向图。pair (a, b)代表一条从b到a的边。
对于每个pair (a, b), 删除边b->a，从b为起点做dfs，若a可达，则删除(a,b)。
时间复杂度为E*V，E为pair数，V为顶点数。
另一种方法
可以从每个顶点为起点遍历一次，例如做bfs，若对于每个位于层数大于1的节点，若有
起点到它的边，则删除。时间复杂度为V^2

g*o2013-09-05 07:09

4 楼

多余的定义是什么？
比如
（a,b),(b,c),(a,d),(d,c)
里面有多余的吗？
这里面也有loop

【在 c*******h 的大作中提到】

: 有很多pair，比如（a,b),(b,c),(a,c)。假设每个pair有依赖关系，a 依赖于b，b依赖
: 于c，a依赖于c。事实上（a,c)是多余的。现在要求剔除所有多余的pair。
: 现在只能想到构建个graph，然后找出所有loop，再断开它，接着遍历一篇。好像很复
: 杂，不知道有什么简单的方法来搞。。。

f*42013-09-05 07:09

5 楼

新增 x->y 时，检查y的直接前驱是否可达x，如果可达则删除该前驱

c*h2013-09-05 07:09

6 楼

这里没有多余的，这样的pair是单向的。举个例子，（a,b),(b,c),(c,d),(d,e),(a,c)
,(b,e)里面，(a,c)和（b,e)是多余的。

l*n2013-09-05 07:09

7 楼

应该是toposort的变体吧。
照toposort的算法走，先考虑入度为0的点，(a,b),(b,c),(c,d),(d,e),(a,c),(b,e)中
入读为0的点是a。a连接的是b和c，如果把a及其边删除，b的入度变为0，c的入度是1，
所以(a,c)就是多余的。
再比如(a,b),(b,c),(c,d),(d,e),(a,c),(a,e)，即a跟b,c,e相连。a及其边删除后，b
，c，e的入度分别为0,1,1,所以(a,c), (a,e)都是多余的。

e*t2013-09-05 07:09

8 楼

拓扑排序

【在 c*******h 的大作中提到】

S*t2013-09-05 07:09

9 楼

dfs做一遍，每个点存incoming edge, 如果第二次visit同一个点，前次存的次的edge
删掉并被替换为新的incoming edge

【在 c*******h 的大作中提到】

c*h2013-09-05 07:09

10 楼

想出来一个用hashtable + bfs的方法，用python写了一下。
from sets import Set
def create_pool(pool,maps,keys):
pool += keys
[ create_pool(pool, maps, maps[key]) for key in keys if maps.has_key(key
) ]
return pool
def findminimalpair(pairs):
keys = list(Set([item[0] for item in pairs ]))
maps = dict((key,[]) for key in keys)
for item in pairs:
maps[item[0]].append(item[1])
result = []
for key in keys:
values = maps[key]
pool = create_pool([],maps,[key])
pool.pop(0)
newvalues = [ val for val in values if pool.count(val)==1 ]
result += [(key,val) for val in newvalues]
return result

d*n2013-09-05 07:09

11 楼

有没有更简单直接的解法呢？

key

【在 c*******h 的大作中提到】

: 想出来一个用hashtable + bfs的方法，用python写了一下。
: from sets import Set
: def create_pool(pool,maps,keys):
: pool += keys
: [ create_pool(pool, maps, maps[key]) for key in keys if maps.has_key(key
: ) ]
: return pool
: def findminimalpair(pairs):
: keys = list(Set([item[0] for item in pairs ]))
: maps = dict((key,[]) for key in keys)