某次面试的一道面试题

面试题

最近面试遇到面试官让我现场敲代码解决一个问题，具体问题是，给定多个节点，这些节点之间有依赖关系（不考虑循环依赖，可能认为是无环图），接着以随机的顺序给定一个这些节点的列表，要求输出这些节点，具体规则时某个节点不能在其依赖的节点之前先被输出。

比如下图：

节点关系

输出：

1
[A, B, D, C, E]

是正确的，但输出：

1
[B, A, D, C, E]

是错误的，因为B依赖于A，因此不能在A之前输出。

给出代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#!/usr/bin/python
#coding=utf-8

def fn(nodes):
    if nodes is None or len(nodes) == 0:
        return None
    
    d = {}
    for node in nodes:
        d[node[0]] = node

    outputs = []
    while nodes:
        node = nodes.pop(0)
        flag = True
        for parent in node[1]:
            if parent not in outputs:
                flag = False
        if flag:
            outputs.append(node[0])
        else:
            nodes.append(node)
    
    return [d[name] for name in outputs]

if __name__ == '__main__':
    A = ["A", []]
    B = ["B", ["A"]]
    C = ["C", ["A", "D"]]
    D = ["D", []]
    E = ["E", ["B", "D"]]

    inputs = [E, B, D, C, A]
    outputs = fn(inputs)
    print(outputs)
面试题