您当前的位置:首页 > 电脑百科 > 程序开发 > 程序员

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

时间:2020-08-06 11:30:37  来源:  作者:

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

考察点:

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

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

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

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

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

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

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

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

 

4. 其他

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

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

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

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

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



Tags:阿里云 面试   点击:()  评论:()
声明:本站部分内容来自互联网,转载是出于传递更多信息之目的,内容观点仅代表作者本人,如有任何标注错误或版权侵犯请与我们联系,我们将及时更正、删除,谢谢。
▌相关评论
发表评论 共有条评论
用户名: 密码:
验证码: 匿名发表
▌相关推荐
这是一道编程题目,结合了数据结构和简单算法(如递归等)。考察点:1. 候选人应该明确什么是 DeepCopy 并主动沟通2. 候选人应该清楚的定义数据结构 这个问题里面,需要定义节点,节点...【详细内容】
2020-08-06   阿里云 面试  点击:(11)  评论:(0)  加入收藏
最新更新
栏目热门
栏目头条