阿里云技术面试真题公开-编程实现 DAG（有向无环图）的 DeepCopy

这是一道编程题目，结合了数据结构和简单算法（如递归等）。

考察点：

1. 候选人应该明确什么是 DeepCopy 并主动沟通

2. 候选人应该清楚的定义数据结构 这个问题里面，需要定义节点，节点只要有 {value, Collection neighbors} 就可以 了，增加别的成员一般是不合理的。

候选人应该意识到需要定义数据结构，如果不清楚定义（是个扣分项）需要提醒候 选人。

图的话可以不定义单独的数据结构，有 Collection 所有节点集合就可以了。当然专门 定义也可以。

有的候选人会有 Collection 和 Collection 定义（Node 里面没有 edge），或者有的候 选人用二维链接矩阵，这也 OK。

数据结构定义合理性检查： 例如包含一些算法需要的 mutable variable 在数据结构里面，破坏结构定义封装以 及 immutability 和 thread safety 的话，对于有经验的候选人是个比较大的减分项， 对于学生一般是 OK 的。

3. 编程实现 一般来说比较方便的是用递归 /DFS 实现，候选人也可以选择其他算法（如 BFS） 以 JAVA 为例：

4. 其他

这个编程的过程，经常出现的是递归的方法和 wrApper 方法之间划分不清，出现大 量的重复代码，候选人这里花多少时间解决也是一个能力的表现。

还有经常有候选人意识不到 DeepCopy 里面需要保持图的结构因此想不到用 Map， 这个也是不行的。

当然如果要求不高，可以直接把题目编程 DeepCopy 一个树，这 样就没有去重的需求了。

能够正确完成的，可以 follow up：如线程安全，问一下候选人方法是否是线程安全 的（如果在 Node 节点里面存一些临时变量，或者把 Map 作为全局变量等就不是 了），可以问如何改造成线程安全之类的问题。

另外 Follow up Big(O)：时间复杂度（O（V) + O(E))