转载

这道机试题挺难的

三四月是每年换工作的黄金时期。但是今年由于疫情的原因，这个时期大家都太难了。面试基本都是电话面试，电话面试完了会有机试（编程题/算法题）。最近我也投了几份简历试了试，确实有点难。本着一个学习的心态，从哪里跌倒就从哪里爬起来。机试的考的是临场发挥，前提是平时要有积累才行。今天分享我前两天的一道机试题，30分的机试我一筹莫展！

二、这道机试题挺难的

2.1 题目

现有一个树控件的数据结构定义如下,认为该数据结构可以直接访问，例如 dataTree.name

[{
  "name": "小组1",
  "leaf": false,    // True 表示叶子节点
  "checked": false, // True 表示勾选状态
  "children": [
    {
      "name": "小组2",
      "leaf": false,
      "checked": false,
      "children": [
        {
          "name": "张三",
          "leaf": true,    
          "checked": false,
          "age": 28
        },
        {
          "name": "小组3",
          "leaf": false,
          "checked": false,
          "children": [
            {
              "name": "李四",
              "leaf": true,
              "checked": false,
              "age": 31
            },
            ...     // 可以有任意子节点
          ]
        },
        ...         // 可以有任意子节点
      ]
    }
  ]
},
{
  "name": "小组4",
  "leaf": false,
  "checked": false,
  "children": [
    {
      "name": "王五",
      "leaf": true,
      "checked": false,
      "age": 35
    },
    ...
  ]
}, ...]
复制代码

问题一：实现一个树控件的勾选事件响应函数，若一个节点下的任意一个叶子节点勾选则该节点与其所有的父节点都被勾选；若勾选的节点含有子节点，则自动勾选所有子节点。

// 勾选事件函数
// dataTreeList   如上所示的树状数据结构
// checkedName 本次事件勾选的节点名称
// isLeaf   True 表示本次勾选的节点是叶子节点
// 返回  直接修改dataTree中checked属性

// For Java
void onChecked(List<DataTree> dataTreeList, String checkedName, Boolean isLeaf) {}
复制代码

问题二：实现一个函数，求该组织中年龄最大的N个人。（其中保证叶子节点都是人）

// 求最大年龄函数
// dataTreeList   如上所示的树状数据结构
// N    N个人的定义，N=[1, 100]
// 返回最大N个人的名字数据，从大到小[name1,name2,…]
String[] getTopN(List<DataTree> dataTreeList, int N) {}
复制代码

给大家 30 分钟思考时间，不要写出的代码可以执行，整理的思路要正确。

2.2 思路分析

下面是我个人对本题目的分析，如果有讲的不对的地方，欢迎大家指正。下面的代码是通过 Java 语言实现的。

2.2.1 问题一解析

//1.获取所有节点，生成每个节点的父子关系parentId,将树形菜单转为列表（list）
//2.在列表中按照 checkedName 和 isLeaf 树形，匹配对应的节点（atchedChild）
//3.在转化后的所有节点的列表(list)中查找节点（matchedChild）的所有父节点名称，或者查找它的所有子节点名称
//4.通过名称匹配树形菜单的对应节点，设置选中状态
复制代码

节点对象 Children 代码如下：

public class Children {
	//名称
	private String name;
	//是否叶子节点
	private boolean leaf;
	//是否选中
	private boolean checked;
	//年龄
	private Integer age;
	
	//父节点id,问题一额外添加的树形
	private String parentId;
	//子节点
	private List<Children> children;
	
	public Children() {}
	
	public Children(String name, boolean leaf, boolean checked, Integer age) {
		this.name = name;
		this.leaf = leaf;
		this.checked = checked;
		this.age = age;
	}
}  
复制代码

步骤一的代码：

public void getAllNodes(List<Children> srcChildrenList, List<Children> resChildrenList, String parentId) {
  if(null != srcChildrenList && srcChildrenList.size() > 0) {
    for(int i=0;i< srcChildrenList.size();i++) {
      Children tempChild = srcChildrenList.get(i);
      tempChild.setParentId(parentId);
      if(tempChild.isLeaf()) { //叶子节点则设置parentId
        resChildrenList.add(tempChild);
      }else {
        //非叶子节点则继续遍历
        getAllNodes(tempChild.getChildren(), resChildrenList, tempChild.getName());
      }
    }
  }
}
复制代码

步骤二的代码：

Children matchedChild = allChildList.stream()
					.filter(c-> c.getName().equals(checkedName) && c.isLeaf() == isLeaf)
					.collect(Collectors.toList()).get(0);
复制代码

步骤三的代码：

List<String> getCheckedNodeNames(List<Children> allChildList, Children matchedChild){
  List<String> names = new ArrayList<>();
  names.add(matchedChild.getName());
  if(matchedChild.isLeaf()) {
    //叶子节点
    getParentNames(names, allChildList, matchedChild.getParentId());
  }else {
    //非叶子节点
    getChidrenNodeNames(names, allChildList, matchedChild.getParentId());
  }
  return names;
}

/**
 * 若为叶子节点则其所有父节点勾选
 * @param names
 */
void getParentNames(List<String> names, List<Children> allChildList, String parentId) {

  if(null != allChildList && allChildList.size() > 0) {
    Children parentNode = allChildList.stream().filter(c->c.getName().equals(parentId))
      .collect(Collectors.toList()).get(0);
    if(parentNode.getParentId().equals(ROOT_CATE)) {
      return;
    }else {
      names.add(parentNode.getName());
      getParentNames(names, allChildList, parentNode.getParentId());
    }

  }
}

/**
 *  若为非叶子节点，则勾选其下的所有子节点
 * @param names
 * @param allChildList
 * @param parentId
 */
void getChidrenNodeNames(List<String> names, List<Children> allChildList, String parentId) {

  if(null != allChildList && allChildList.size() > 0) {
    List<Children> childrenList = allChildList.stream().filter(c->c.getParentId().equals(parentId))
      .collect(Collectors.toList());

    childrenList.forEach(c->{
      if(c.isLeaf()) {
        names.add(c.getName());
      }else {
        getChidrenNodeNames(names, allChildList, c.getName());
      }
    });

  }
}
复制代码

步骤四的代码：

/**
 * 根据节点名称数组设置选中节点
 * @param childirenList
 */
void checkChildNodesByName(List<Children> childirenList,List<String> checkedNames) {
  if(null != childirenList && childirenList.size()> 0) {
    for(int i=0;i< childirenList.size();i++) {
      Children child = childirenList.get(i);
      for(int j=0;j<checkedNames.size();j++) {
        if(child.getName().equals(checkedNames.get(i))) {
          child.setChecked(true);
          if(!child.isLeaf()) {
            checkChildNodesByName(child.getChildren(), checkedNames.subList(1, checkedNames.size() - 1));
          }
        }	
      }
    }
  }
}
复制代码

2.2.2 问题二解析

//1.获取所有的叶子节点
//2.通过对象属性age进行排序
//3.返回最大N个人的名字
复制代码

步骤一的代码：

public void getLeafNodes(List<Children> srcChildrenList, List<Children> resChildrenList) {
  if(null != srcChildrenList && srcChildrenList.size() > 0) {
    for(int i=0;i< srcChildrenList.size();i++) {
      Children tempChild = srcChildrenList.get(i);
      if(tempChild.isLeaf()) { //叶子节点则添加到集合
        resChildrenList.add(tempChild);
      }else {
        //非叶子节点则继续遍历
        getLeafNodes(tempChild.getChildren(), resChildrenList);
      }
    }
  }
}
复制代码

步骤二的代码：

//Comparator.comparing 默认升序排列，这里需要反转一下，即为降序
List<Children> restChildrenList = leafList.stream().sorted(Comparator.comparing(Children::getAge).reversed()).collect(Collectors.toList());
复制代码

步骤三的代码：

if(restChildrenList.size() >= N) {
  for(int i=0;i< N;i++) {
    names[i] = restChildrenList.get(i).getName();
  }
}else {
  for(int i=0;i< restChildrenList.size();i++) {
    names[i] = restChildrenList.get(i).getName();
  }
}
复制代码