shaoxyz

你看上去像是体面人

0%

将包含父子关系值的列表转为树状嵌套字典

发表于 分类于 阅读次数： Valine：

记录一道笔试题

题目

假设前端同学通过接口向后端传了天猫的行业信息，例如：

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
industry_list = [
  {
     "parent_ind" : "女装",
     "name" : "连衣裙"
  },
  {
     "name": "女装"
  },
  {
     "parent_ind" : "女装",
     "name" : "半身裙"
  },
  {
     "parent_ind" : "女装",
     "name" : "A字裙"
  },
  {
     "name": "数码"
  },
  {
    "parent_ind" : "数码",
     "name": "电脑配件"
  },
  {
    "parent_ind" : "电脑配件",
     "name": "内存"
  },
]

为了取用方便，我们希望可以将其转换为树状格式，例如：

1
2
3
4
5
6
7
8
9
10
11
12
{
  "数码": {
    "电脑配件": {
        "内存" : {}
     }
  },
  "女装" : {
     "连衣裙": {},
    "半身裙": {},
    "A字裙": {}
  }
}

实现一个方法完成这个转换,时间复杂度请控制在O(n)

1
2
def convert_format(data):
       pass

考察的知识点

1.数据类型，Python里set的查找效率比list高
2.字典推导，更Pythonic的写法
3.对象引用，Python的赋值是给值贴上标签，而不是把值放入盒子

思路

  • 先根据industry_list构建一个包含所有项的字典data_dict；
  • 遍历industry_list并利用对象引用的特点自动更新data_dict的嵌套关系；
  • 最后过滤掉那些只存在于嵌套之内的值；

代码

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
# -*- coding: utf-8 -*-
"""
@author: shaoxyz
@file: convert_format.py
@time: 2020-07-20 11:09
@desc:
"""
from typing import List
industry_list = [
    {"parent_ind": "女装", "name": "连衣裙"},
    {"name": "女装"},
    {"parent_ind": "女装", "name": "半身裙"},
    {"parent_ind": "女装", "name": "A字裙"},
    {"parent_ind": "数码", "name": "电脑配件"},
    {"parent_ind": "电脑配件", "name": "内存"},
    {"name": "数码"},
]

expect_output = {
    "数码": {
        "电脑配件": {
            "内存": {}
        }
    }, 
    "女装": {
        "连衣裙": {}, 
        "半身裙": {}, 
        "A字裙": {}
    }
}


def convert_format(data: List[dict]) -> dict:
    """
    将包含父子关系值的列表 转换为 嵌套字典
    """

    data_dict = {i.get("name"): {} for i in data}
    has_parent = set()

    for i in data:
        parent_ind = i.get("parent_ind")
        name = i.get("name")
        if parent_ind:
            has_parent.add(name)
        if parent_ind in data_dict:
            data_dict[parent_ind][name] = data_dict[name]  # KEY

    # Filter
    res = {key: val for key, val in data_dict.items() if key not in has_parent}

    return res


def test_convert_format():
    res = convert_format(industry_list)
    assert res == expect_output
    print("well done")