这是一道编程题目,结合了数据结构和简单算法(如递归等)。
考察点:
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))