V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
unregister
V2EX  ›  Java

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

  •  
  •   unregister · 2022-02-09 22:23:05 +08:00 · 6586 次点击
    这是一个创建于 777 天前的主题,其中的信息可能已经有所发展或是发生改变。

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

    45 条回复    2022-02-15 17:56:19 +08:00
    unregister
        1
    unregister  
    OP
       2022-02-09 22:24:32 +08:00
    上家公司项目很简单,主要就是 crud 。
    corningsun
        2
    corningsun  
       2022-02-09 22:36:21 +08:00 via iPhone
    这不是 hard 吧,构造 一个 tree 对象就行了
    rabbbit
        3
    rabbbit  
       2022-02-09 22:38:06 +08:00
    原题是啥?看描述不是很难...
    unregister
        4
    unregister  
    OP
       2022-02-09 22:43:16 +08:00
    @rabbbit 就是有多个具有层级关系的城市对,比如"中国 浙江 杭州”,"中国“,"中国 广东","中国 广东 广州 越秀区”这样的 list 。把他转成树状结构的行政区树,以 Json 的形式输出。
    ufan0
        5
    ufan0  
       2022-02-09 22:43:42 +08:00
    这个描述让我想到了百家互联,校招终面给的算法题描述的还不如你说的,输入值是一大串 json 。

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

    面试官:你没见过 json 吗?

    我:可以使用 json 解析工具吗?

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

    然后我就挂了......
    whileFalse
        6
    whileFalse  
       2022-02-09 22:44:22 +08:00   ❤️ 5
    这……很难吗……
    unregister
        7
    unregister  
    OP
       2022-02-09 22:45:52 +08:00
    @corningsun 嗯,但是对递归这个概念理解的不是很清晰,树的数据结构了解的不是很透彻,具体实现起来还是有一定难度,主要是题目一开始没明白,后面我的思路始,取每一个 item 的最后两位,存入一个 map 。然后每一个节点里面有一个 List 子节点。
    unregister
        8
    unregister  
    OP
       2022-02-09 22:47:32 +08:00
    @whileFalse 297. 二叉树的序列化与反序列化 我看这里面的难度是困难。他的题目比较烦我觉得。
    unregister
        9
    unregister  
    OP
       2022-02-09 22:52:55 +08:00
    @ufan0 是的,提供的输入数据,这些城市对都不加双引号的,之间逗号也没有,就是空格。我问她,她说不是我作答,我觉得这道题也没有什么意义,正常行政区树直接查父级的行政区编号就行了吗?
    sagaxu
        10
    sagaxu  
       2022-02-09 23:03:06 +08:00   ❤️ 1
    这就是最简单的递归啊,十多年前 PHP 面试官们把这个叫做“无限分类”,“无限菜单”
    jmc891205
        11
    jmc891205  
       2022-02-09 23:04:12 +08:00
    构造一个 trie ?
    unregister
        12
    unregister  
    OP
       2022-02-09 23:16:16 +08:00
    @sagaxu 嗯,他没有 pid,id 只有行政区的名称,而且那个像这样的数据 中国 广东 广州 越秀区 感觉还要自己处理获取 parentName, name.不过吃一堑长一智。
    az467
        13
    az467  
       2022-02-09 23:17:45 +08:00   ❤️ 1
    再怎么卷外包也不会一面 hard 吧
    Keyi
        14
    Keyi  
       2022-02-09 23:23:33 +08:00 via Android   ❤️ 1
    我看这个描述,应该是想要按照空格拆开转成 Map 嵌套?
    interim
        15
    interim  
       2022-02-09 23:53:13 +08:00   ❤️ 1
    递归可解,Java 再怎么卷,外包也不至于 hard 难度连面试都没把...
    rabbbit
        16
    rabbbit  
       2022-02-09 23:55:50 +08:00
    试着写了一下,不知道是不是这个意思.
    我前端,写的可能有些丑...

    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
        17
    rabbbit  
       2022-02-09 23:59:35 +08:00
    唔,好像不太对.
    rabbbit
        18
    rabbbit  
       2022-02-10 00:05:14 +08:00   ❤️ 1
    这回对了

    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
        19
    rabbbit  
       2022-02-10 00:39:55 +08:00
    想到个问题,要是有不同省市地下有重名的就坏了,所以还是不对...
    Valid
        20
    Valid  
       2022-02-10 01:49:18 +08:00
    @rabbbit 所以为什么会有这种 cityList ,直接维护一个城市 json 不就好了
    xiadong1994
        21
    xiadong1994  
       2022-02-10 02:12:13 +08:00 via iPhone
    @unregister 序列化与反序列化是 hard 是因为给的输入是遍历的结果,你的这道题给的是从 root 到某一个 node 的 path ,提供了更多的 tree 结构信息,顶多是个 medium 。
    msg7086
        22
    msg7086  
       2022-02-10 06:56:36 +08:00   ❤️ 1
    撑死 medium ,我觉得算 easy 都可以。
    如果不懂递归,那至少懂面向对象吧。
    自己建一个类 Region ,然后类成员 List<Region> subRegions ,类方法 append(String fullRegionPath),把字符串的第一段切出来添加进 subRegions ,然后把剩下的交给 subRegion.append()不就行了。
    如果我是面试官,我更希望面试者用面向对象的方法去实现递归,而不是像上面一位老哥那样开个 for 循环去搞。
    kran
        23
    kran  
       2022-02-10 08:23:53 +08:00 via Android
    map+引用,单次循环就可以了
    VeryZero
        24
    VeryZero  
       2022-02-10 09:00:58 +08:00
    这就是最基本的递归啊,而且工作中很常用。比如分类树,目录树
    fpure
        25
    fpure  
       2022-02-10 09:39:04 +08:00
    @unregister 这个题我觉得递归都可以不用吧
    Junzhou
        26
    Junzhou  
       2022-02-10 09:44:32 +08:00
    @unregister 这个感觉没想象中的麻烦,可能力扣中等难度? 遍历这个列表,拿到每一条记录,通过字符分割,中国 广东 广州 越秀 ,拿到四个不同级别的行政区,然后处理下一个,中国 广东 深圳 南山 广东已经存在了,直接把深圳加入到广东的子节点,南山加到深圳的子节点,如果是 中国 广东 深圳 宝安 根据中国找到广东,找到深圳,宝安不存在,将宝安加入到深圳的子节点。以此类推?
    Junzhou
        27
    Junzhou  
       2022-02-10 09:45:53 +08:00
    @rabbbit 同名不影响,root 节点到 node 节点的路径都给你了。
    illuz
        28
    illuz  
       2022-02-10 09:46:45 +08:00 via Android
    水题,老哥多刷刷算法吧
    这种树状结构工程里还是挺常见的,这就 emo 说明水平一般
    fpure
        29
    fpure  
       2022-02-10 10:10:11 +08:00
    package com.example;

    import java.util.Arrays;
    import java.util.HashMap;
    import java.util.List;

    import com.google.gson.GsonBuilder;

    public class x {
    @SuppressWarnings("unchecked")
    public static void main(String[] args) {
    List<String> list = Arrays.asList("中国 广州", "中国 浙江 杭州");
    HashMap<String, Object> root = new HashMap<>();
    for (String s : list) {
    HashMap<String, Object> node = root;
    String[] ss = s.split(" ");
    for (int i = 0; i < ss.length; i++) {
    HashMap<String, Object> subNode = (HashMap<String, Object>) node.get(ss[i]);
    if (subNode == null) {
    subNode = new HashMap<>();
    node.put(ss[i], subNode);
    }
    node = subNode;
    }
    }
    System.out.println(new GsonBuilder()
    .setPrettyPrinting()
    .serializeNulls()
    .create().toJson(root));
    }
    }
    Vegetable
        30
    Vegetable  
       2022-02-10 10:16:00 +08:00
    这是 hard 吗...
    OldCarMan
        31
    OldCarMan  
       2022-02-10 10:23:11 +08:00   ❤️ 1
    @unregister #8 不知道我有没有理解错,这道题最终目的是以树状结构的 json 数据输出,而不是中间一定要套上树这种数据结构,如果是这样的话,直接用 map 多层嵌套+递归和判断 就行了,个人觉得(暗中观察够🐶)。
    dqzcwxb
        32
    dqzcwxb  
       2022-02-10 11:05:24 +08:00   ❤️ 1

    所有的递归都可以写成循环
    rabbbit
        33
    rabbbit  
       2022-02-10 11:06:30 +08:00
    @Junzhou 呃,我是说我写的那个不对啦.
    昨天太晚了,改成这样就好了.

    import java.util.*;

    public class App {
      public static void main(String[] args) {
       Map<String, Map> map = new HashMap();
       String[] cityList = {"中国 浙江 杭州","中国","中国 广东", "中国 广东 广州 越秀区", "中国 达拉崩吧 广州"};
       for (String cityStr: cityList) {
        Map<String, Map> parentMap = map;
        for (String key: cityStr.split(" ")) {
         Map mapOfKey = addMap(key, parentMap);
         parentMap = mapOfKey;
       }
      }
       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', ' ');
     }
    }
    cassyfar
        34
    cassyfar  
       2022-02-10 11:25:51 +08:00
    @rabbbit 你这个数据结构是错的吧,题主已经说明了最后要存进一个树里面。

    数据结构用这个,然后每查看一组,就遍历插入新节点即可。
    class Node {
    String id;
    List<Node> children ;
    }
    unregister
        35
    unregister  
    OP
       2022-02-10 11:26:19 +08:00
    @Junzhou 嗯,是我太水了
    @fpure 厉害了,完美啊。
    @rabbbit 厉害,学习了,达拉崩吧,很 happy 啊😂
    rabbbit
        36
    rabbbit  
       2022-02-10 11:32:07 +08:00
    @cassyfar
    这种面试题应该思路对了就行,没必要非得是 LeetCode 那种树结构.
    Map 表示能方便点, 子 List 还得遍历去搜.
    unregister
        37
    unregister  
    OP
       2022-02-10 11:33:11 +08:00
    @cassyfar 这个应该是用 Map 实现的,只是需要按照要求输出那个树状图就行了。
    Tianyan
        38
    Tianyan  
       2022-02-10 13:14:20 +08:00
    灵活就业者(失业者)超过 2 亿
    unregister
        39
    unregister  
    OP
       2022-02-10 13:32:06 +08:00
    @whileFalse 嗯,对我来说有一点,这也知道和别人的差距在哪里。
    aikilan
        40
    aikilan  
       2022-02-10 16:11:44 +08:00   ❤️ 1
    const data = ["中国 广州 深圳", "中国 广州 佛山", "中国 浙江 杭州"];

    const onStart = (data) => {
    const res = {};
    const onGen = (result, row) => {
    if(!row.length){
    return
    }
    const item = row[0];
    if(result[item]){
    onGen(result[item], row.slice(1))
    }else{
    result[item] = {};
    onGen(result[item], row.slice(1))
    }
    }
    for(let i in data){
    onGen(res, data[i].split(' '));
    }
    return res
    }
    onStart(data)

    //{ '中国': { '广州': { '深圳': {}, '佛山': {} }, '浙江': { '杭州': {} } } }
    Chinsung
        41
    Chinsung  
       2022-02-10 17:15:56 +08:00
    这种确定层级的,直接 map 塞就完事了吧,没必要非用树
    msg7086
        42
    msg7086  
       2022-02-10 17:24:51 +08:00 via Android
    ( map 嵌套就是树)
    Aganzo
        43
    Aganzo  
       2022-02-10 17:36:49 +08:00
    力扣也水了 1000 多题了,HARD 题一般会组合 DP 、UF 、单调栈、贪心、二分、划窗、Trie 、回溯等知识点中的一个或多个,按文中描述的题目内容评级应为 EASY
    jguo
        44
    jguo  
       2022-02-10 20:54:19 +08:00
    那就抓紧学,递归都搞不明白别说自己是程序员
    unregister
        45
    unregister  
    OP
       2022-02-15 17:56:19 +08:00
    @Aganzo 我愿称之你为大佬。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   3171 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 32ms · UTC 12:29 · PVG 20:29 · LAX 05:29 · JFK 08:29
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.