给定经理和员工在

Question

我在一次采访中被问到：

给定下属和经理，构造一个数据结构（或使用现有的数据结构），然后实现方法CountReport（雇员ID），以便它打印总的直接和间接报告。

我告诉我，我将通过构建一个图来解决它，然后计算每个顶点的in度，我告诉它时间复杂度为O（ve）。然后我被要求用计算机解决这个问题

/** 

subordinate, manager
A, C
B, C
C, F
D, E
E, F
F, F

countReports(employeeId) -> num // sum of direct and indirect reports for employee with id=employeeId

eg. 

A -> 0
C -> 2 // A, B
F -> 6 // C, E, F, A, B, D

Ask:
 * implement countReports
 
*/

Answer 1

根据你的描述，第一个结构出现在我的脑海中：

Map<String,List<String>> mapEmployee = new HashMap<String,List<String>>();

或

Map<String,Set<String>> mapEmployee = new HashMap<String,Set<String>>();

第一个循环，我们迭代输入列表并构建上述数据结构。复杂性：O（N）。

然后我们可以通过employeeId快速访问结果，复杂性：O（1）。

List<String> subordinates = mapEmployee.get(employee); O(1)
int result = subordinates.count(); // O(1)

注：添加多个下属时，使用LinkedList可能会加快速度。