LintCode题解| Hulu 面试题:Print Organization Chart

842 阅读2分钟

九章算法 | Hulu 面试题:Print Organization Chart

题目描述

按员工姓名,上一级姓名,职位,年份给出一系列企业中员工的关系,输出企业成员组织结构图。


思路点拨

按员工关系表建立一棵树,然后先序遍历这棵树,注意树的每一层要进行排序。


考点分析

本题主要考察了树的构造与树的遍历,首先根据每位员工上一级的信息构造出树结构,再对这颗树进行先序遍历,即可以得到答案,值得注意的是每一级员工要按名字的字典序进行排序。


九章参考程序

www.jiuzhang.com/solution/pr…

/**
* 本参考程序来自九章算法,由 @华助教 提供。版权所有,转发请注明出处。
* - 九章算法致力于帮助更多中国人找到好的工作,教师团队均来自硅谷和国内的一线大公司在职工程师。
* - 现有的面试培训课程包括:九章算法班,系统设计班,算法强化班,Java入门与基础算法班,Android 项目实战班,
* - Big Data 项目实战班,算法面试高频题班, 动态规划专题班
* - 更多详情请见官方网站:http://www.jiuzhang.com/?source=code
*/ 

public class Solution {
    /**
     * @param relationship: the relationship
     * @return: the organization chart
     */
    List<List<Integer>> graph;
    List<String> nameList;
    List<String> ans;
    HashMap<String, Integer> nameMap;
    void dfs(int x, int depth, List<List<String>> relationship) {
        String ins = "";
        for (int i = 0; i < depth; i++) {
            ins = ins + "-";
        }
        ins = ins + relationship.get(x).get(0) + " (" + relationship.get(x).get(2) + ") " + relationship.get(x).get(3);
        ans.add(ins);
        for (int i = 0; i < graph.get(x).size(); i++) {
            dfs(graph.get(x).get(i), depth + 1, relationship);
        }
    }
    class Cmp implements Comparator<Integer> {
        public int compare(Integer a, Integer b) {
            return nameList.get(a).compareTo(nameList.get(b));
        }
    }
    public List<String> getOrganization(List<List<String>> relationship) {
        // Write your code here
        nameList = new ArrayList<String>();
        for (int i = 0; i < relationship.size(); i++) {
            nameList.add(relationship.get(i).get(0));
        }
        int root = 0;
        graph = new ArrayList<List<Integer>>();
        nameMap = new HashMap<String, Integer>();
        for (int i = 0; i < relationship.size(); i++) {
            graph.add(new ArrayList<Integer>());
        }
        for (int i = 0; i < relationship.size(); i++) {
            if (relationship.get(i).get(1).equals("NULL")) {
                root = i;
            }
            nameMap.put(relationship.get(i).get(0), i);
        }
        for (int i = 0; i < relationship.size(); i++) {
            if (!relationship.get(i).get(1).equals("NULL")) {
                int x = nameMap.get(relationship.get(i).get(0));
                int y = nameMap.get(relationship.get(i).get(1));
                graph.get(y).add(x);
            }
        }
        for (int i = 0; i < graph.size(); i++) {
            Collections.sort(graph.get(i), new Cmp());
        }
        ans = new ArrayList<String>();
        dfs(root, 0, relationship);
        return ans;
    }
}