dfs加参数,amazon aws 别人的电面找到直接下属平均工资最高的manager

https://www.1point3acres.com/bbs/thread-785778-1-1.html

 

Coding:
1. 如果要设计一个公司的organizational report structure应该用什么数据结构? 回答: Tree, 然后写了一个TreeNode class, 包含 Title, Name, Salary, List<TreeNode> children
2. 找到直接下属平均工资最高的manager
很简单,秒了。dfs和bfs都写了。 不过他要我比较一下两者区别,说visit each node的次数不同;我一开始没搞懂。后来才明白他说的是,bfs要visit两次,一次是children list traversal, 一次是q.poll(); 而dfs只要visit 一次。

 

先给每个节点加上level
traverse(root.left, level + 1);
root 不处理
traverse(root.right, level + 1);

完成全部的标记之后,再次dfs一边
calculate(root.left)
if (root.left.level == root.level + 1)
   list.add(root.left);
//right同样
list求平均值
//add to mng list
calculate(root.left)

 

上一篇:AWS — AWS ECS


下一篇:一次比较奇葩的 AWS 面试