记一道B公司的一面面试题.md

米洛 2022/6/13 杂谈面试

大家好~我是米洛，咱们又见面了！

今天因为不是周末，所以来聊点儿不算轻松的话题。

# 周一的故事

一早儿刚开工，就收到了一位饭哥忠实粉丝的私信，由于和他同一天入职过一家公司，并且大家也比较聊得来。加上大家都是测试开发干货的铁粉，所以我们还经常会联系。

私信的内容是请教我一个问题，虽然用了我最害怕的方式:

毕竟在不清楚问题的情况下，万一要是把握不住，那不就翻车了么

所以我下意识地问了一下是啥问题。读完问题以后，我不禁想到了当初去某个BD公司面试的经历。

题目和他的问题类似，我们先来看看他的问题。

以下是完整数据

{
    "message": "Success",
    "result": {
        "root": [{
            "children": [{
                "children": [{
                    "children": [],
                    "id": 3877,
                    "name": "自动化测试组织0101"
                }],
                "id": 516,
                "name": "自动化测试组织01"
            }, {
                "children": [{
                    "children": [{
                        "children": [],
                        "id": 3879,
                        "name": "自动化测试组织020101"
                    }],
                    "id": 3878,
                    "name": "自动化测试组织0201"
                }],
                "id": 517,
                "name": "自动化测试组织02"
            }],
            "id": 3159,
            "name": "自动化测试专用机构",
        }]
    },
    "status": 0,
    "success": True
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

# BD原题

当时那位小哥给我找了张纸，在里面写了一个json数据，类似上文中的数据，让我根据name="xxx"去找他的title，title和name是平级的。可以说是相当重合了，和这道题。

不过我当时理解出了点问题，我直接根据目测的路径，用.get取到了那一层，并返回了对应的title。

小哥看完之后也是一脸懵逼，然后对我说，不是这个意思。不过算了，继续下一个问题吧。

我也不好说啥，只能顺水推舟绕过了这题。

# 回到正题

那我们要怎么做才能达到根据数据里面的name，找到他的id呢？

如果感兴趣的朋友，可以先不看我这块内容，把数据复制下来，自己写写看，然后补充一些测试用例给自己测一下看看。因为它毕竟也是瘦死的骆驼头部互联网公司的一面面试题。

# 解决方案

我们把这个问题拆分为2个部分，第一个部分是取root数据，第二个部分是编写递归方法，并查找对应的name。

Round 1 Ready Go!

编写入口方法

根据data里面的success字段判断是否拿到了数据，拿到了我们就取出字典里面的root数据。

这样我们只需要去root里面搜刮一顿，调用find_id_by_name方法拿到最终id即可，注意这里先假设name不重复。

Round 2 编写递归方法

代码很简短

for r in root，如果root为空数组的话，那么会直接不走for循环，return None
当r.get("name")与我们传入的name相等的话，直接返回这一层的id
能走到children这一步，说明这一层没有咱们想要的
获取children
接着我们把children这一层当作root，继续调用find_id_by_name方法

如果我们以文件夹里面搜索文件为例子的话，根目录有10个文件夹，我们搜索没找到对应的，接着我们去第一个文件夹里面搜索，假设第一个文件夹里面有2个文件夹，我们此时的children对应的就是第一个文件夹的2个文件夹。

想一下，他是不是也是一个文件夹，你把它当做根目录来看的话，是不是又可以继续按照根目录的方式去搜刮？递归就是这样的道理。

搜索根目录的时候，我们的基准是以根路径为基准，搜索第1个文件夹的时候，基准又成了第一个文件夹，并以此类推。

搜索到的结果如果不是None，说明在这个文件夹下面找到了数据，直接return即可停止继续搜索。

假设这个时候层次很深，已经搜索到 fange/wudige/cc/hehe这么深的目录了，那么有的同学会问，一个return能跳出来吗？

想想一下，在cc层调用find_id_by_name(hehe),这是hehe这一层return了，值为result，cc这一层判断result不是None，cc也return了，cc的上一层wudige也收到了cc的return，这样就达到了最终退出递归方法的效果。

# 递归可能存在的问题

不慎的话容易死循环

但这不是递归的错，就算是while，你不改变循环条件，也会死循环。

堆栈太长

这个是递归被人诟病的地方，如果遇到深度几千万层的数据，递归最终会引起内存不足，导致程序崩溃。

# 怎么避免

第二个问题，如果是层级很深的情况，不建议使用递归。

第一个问题的话，我们一定要注意递归结束的条件。在上述例子里面，递归结束的条件就是找到name，也就是result不为空，很好理解，因为为空说明没找到，不把整个文件夹给你翻个底朝天就不会停止。

其实还有一个隐形的条件，就是for r in root，这里有一个隐形的条件是root为空数组，这样的话，这个递归方法也会结束，直接return None。

# 大家一起来写写吧

源代码我就不放上了，建议大家动起手来~

假设大家正在面试，在白纸上写黑字，看看自己能否一遍过呀。其实那次面试也跪在总监手里了，也是挺玄学的吧~

不过还是那句话，学到了！

米洛的小窝

Choose mode