目前辞职在家，想面试一下试试水，结果笔试题一做 emo 了

[unregister]

Java 转行，目前加起来 Java 开发经验一年多一点，HR 给我发了两道题，第一道是具有层级关系的城市，例如"中国 广州"，"中国 浙江 杭州" 一个 List 最后应该是转成树状图输出，最后还是没答完，后面去 leetcode 上看了一下，应该是属于 hard 难度的。想到前景越来越黯淡，emo 了。而且面的是外包，面试官都没见到。

[unregister]

上家公司项目很简单，主要就是 crud 。

[corningsun]

这不是 hard 吧，构造 一个 tree 对象就行了

[rabbbit]

原题是啥?看描述不是很难...

[unregister]

@rabbbit 就是有多个具有层级关系的城市对，比如"中国 浙江 杭州”,"中国“，"中国 广东","中国 广东 广州 越秀区”这样的 list 。把他转成树状结构的行政区树，以 Json 的形式输出。

[ufan0]

这个描述让我想到了百家互联，校招终面给的算法题描述的还不如你说的，输入值是一大串 json 。

我：输入值是已经定义的数据结构还是啥？

面试官：你没见过 json 吗？

我：可以使用 json 解析工具吗？

面试官：这是白板，如果你确定你能引入包，随便你用。

然后我就挂了......

[whileFalse]

这……很难吗……

[unregister]

@corningsun 嗯，但是对递归这个概念理解的不是很清晰，树的数据结构了解的不是很透彻，具体实现起来还是有一定难度，主要是题目一开始没明白，后面我的思路始，取每一个 item 的最后两位，存入一个 map 。然后每一个节点里面有一个 List 子节点。

[unregister]

@whileFalse 297. 二叉树的序列化与反序列化 我看这里面的难度是困难。他的题目比较烦我觉得。

[unregister]

@ufan0 是的，提供的输入数据，这些城市对都不加双引号的，之间逗号也没有，就是空格。我问她，她说不是我作答，我觉得这道题也没有什么意义，正常行政区树直接查父级的行政区编号就行了吗？

[sagaxu]

这就是最简单的递归啊，十多年前 PHP 面试官们把这个叫做“无限分类”，“无限菜单”

[jmc891205]

构造一个 trie ？

[unregister]

@sagaxu 嗯，他没有 pid,id 只有行政区的名称，而且那个像这样的数据 中国 广东 广州 越秀区 感觉还要自己处理获取 parentName, name.不过吃一堑长一智。

[az467]

再怎么卷外包也不会一面 hard 吧

[keifafa]

我看这个描述，应该是想要按照空格拆开转成 Map 嵌套？

[interim]

递归可解，Java 再怎么卷，外包也不至于 hard 难度连面试都没把...

[rabbbit]

试着写了一下,不知道是不是这个意思.
我前端,写的可能有些丑...

import java.util.*;

public class App {
　 public static Map<String, Map> map;
　 public static void main(String[] args) {
　　 map = new HashMap();
　　 String[] cityList = {"中国 浙江 杭州","中国","中国 广东", "中国 广东 广州 越秀区"};
　　 for (String cityStr: cityList) {
　　　 String[] itemList = cityStr.split(" ");
　　　 if(itemList.length > 0) {
　　　　 addMap(itemList[0], map);
　　　}
　　　 if(itemList.length > 1) {
　　　　 for (int i = 1; i < itemList.length; i++) {
　　　　　 String beforeKey = itemList[i - 1];
　　　　　 String key = itemList[i];
　　　　　 Map mapOfBeforeKey = addMap(beforeKey, map);
　　　　　 Map mapOfKey = addMap(key, map);
　　　　　 if(!mapOfBeforeKey.containsKey(key)) {
　　　　　　 mapOfBeforeKey.put(key, mapOfKey);
　　　　　}
　　　　}
　　　}
　　}

　　 for(String key: (ArrayList<String>)new ArrayList(map.keySet())) {
　　　 if(!key.equals("中国")) {
　　　　 map.remove(key);
　　　}
　　}
　　 System.out.println(toJSON(map, 2));
　}

　 public static Map<String, Map> addMap(String key,Map<String, Map> map ) {
　　 if(!map.containsKey(key)) {
　　　 map.put(key, new HashMap<String, Map>());
　　}
　　 return map.get(key);
　}

　 public static String toJSON(Map<String, Map> map, int intend) {
　　 String str = "{";
　　 List<String> keys = new ArrayList(map.keySet());
　　 if( keys.size() > 0) {
　　　 str += "\r\n";
　　}
　　 for (int i = 0; i < keys.size(); i++) {
　　　 str += "\r\n" + geneSpace(intend);
　　　 String key = keys.get(i);
　　　 str += geneSpace(intend) + key + ": " + toJSON(map.get(key), intend + 2);
　　　 if(i < keys.size() - 1) {
　　　　 str += ",";
　　　}
　　　 str += "\r\n";
　　}
　　 if( keys.size() > 0) {
　　　 str += geneSpace(intend);
　　}
　　 str += "}";
　　 return str;
　}

　 public static String geneSpace(int len) {
　　 return new String(new char[len]).replace('\0', ' ');
　}
}

[rabbbit]

唔,好像不太对.

[rabbbit]

这回对了

import java.util.*;

public class App {
　 public static Map<String, Map> map;
　 public static void main(String[] args) {
　　 map = new HashMap();
　　 String[] cityList = {"中国 浙江 杭州","中国","中国 广东", "中国 广东 广州 越秀区"};
　　 for (String cityStr: cityList) {
　　　 String[] itemList = cityStr.split(" ");
　　　 if(itemList.length > 0) {
　　　　 addMap(itemList[0], map);
　　　}
　　　 if(itemList.length > 1) {
　　　　 for (int i = 1; i < itemList.length; i++) {
　　　　　 String beforeKey = itemList[i - 1];
　　　　　 String key = itemList[i];
　　　　　 Map mapOfBeforeKey = addMap(beforeKey, map);
　　　　　 Map mapOfKey = addMap(key, map);
　　　　　 if(!mapOfBeforeKey.containsKey(key)) {
　　　　　　 mapOfBeforeKey.put(key, mapOfKey);
　　　　　}
　　　　}
　　　}
　　}

　　 for(String key: (ArrayList<String>)new ArrayList(map.keySet())) {
　　　 if(!key.equals("中国")) {
　　　　 map.remove(key);
　　　}
　　}
　　 System.out.println(toJSON(map, 0));
　}

　 public static Map<String, Map> addMap(String key,Map<String, Map> map ) {
　　 if(!map.containsKey(key)) {
　　　 map.put(key, new HashMap<String, Map>());
　　}
　　 return map.get(key);
　}

　 public static String toJSON(Map<String, Map> map, int intend) {
　　 String str = "{";
　　 List<String> keys = new ArrayList(map.keySet());
　　 if( keys.size() > 0) {
　　　 str += "\r\n";
　　}
　　 for (int i = 0; i < keys.size(); i++) {
　　　 String key = keys.get(i);
　　　 str += geneSpace(intend + 2) + key + ": " + toJSON(map.get(key), intend + 2);
　　　 if(i < keys.size() - 1) {
　　　　 str += ",";
　　　}
　　　 str += "\r\n";
　　}
　　 if( keys.size() > 0) {
　　　 str += geneSpace(intend);
　　}
　　 str += "}";
　　 return str;
　}

　 public static String geneSpace(int len) {
　　 return new String(new char[len]).replace('\0', ' ');
　}
}

输出

{
　中国: {
　　广东: {
　　　广州: {
　　　　越秀区: {}
　　　}
　　},
　　浙江: {
　　　杭州: {}
　　}
　}
}

[rabbbit]

想到个问题,要是有不同省市地下有重名的就坏了,所以还是不对...

[Valid]

@rabbbit 所以为什么会有这种 cityList ，直接维护一个城市 json 不就好了