desafio de estrutura de dados recursiva

challenge.md

Desafio: Transforme uma Lista de Funcionários em uma Estrutura Hierárquica

O que você vai fazer

Você vai receber uma lista de funcionários, onde cada funcionário tem um ID, um nome e um parent_id que indica quem é seu supervisor. Seu objetivo é transformar essa lista em uma estrutura hierárquica (como uma árvore), onde cada funcionário contém uma lista de seus subordinados. Além disso, o desafio enfatiza o uso de estruturas de dados imutáveis e programação funcional.

Como está a lista

Aqui está um exemplo da lista de funcionários em diferentes linguagens de programação:

JavaScript

const employees = [
    { id: 10, name: "Marketing Specialist", parent_id: 4 },
    { id: 3, name: "Head of Engineering", parent_id: 1 },
    { id: 1, name: "Founder & CEO", parent_id: null },
    { id: 2, name: "Chief Technology Officer", parent_id: 1 },
    { id: 4, name: "Marketing Manager", parent_id: 2 },
    { id: 5, name: "Engineering Lead", parent_id: 3 },
    { id: 6, name: "Software Engineer", parent_id: 5 },
];

Python

employees = [
    { "id": 10, "name": "Marketing Specialist", "parent_id": 4 },
    { "id": 3, "name": "Head of Engineering", "parent_id": 1 },
    { "id": 1, "name": "Founder & CEO", "parent_id": None },
    { "id": 2, "name": "Chief Technology Officer", "parent_id": 1 },
    { "id": 4, "name": "Marketing Manager", "parent_id": 2 },
    { "id": 5, "name": "Engineering Lead", "parent_id": 3 },
    { "id": 6, "name": "Software Engineer", "parent_id": 5 },
]

Elixir

employees = [
    %{id: 10, name: "Marketing Specialist", parent_id: 4},
    %{id: 3, name: "Head of Engineering", parent_id: 1},
    %{id: 1, name: "Founder & CEO", parent_id: nil},
    %{id: 2, name: "Chief Technology Officer", parent_id: 1},
    %{id: 4, name: "Marketing Manager", parent_id: 2},
    %{id: 5, name: "Engineering Lead", parent_id: 3},
    %{id: 6, name: "Software Engineer", parent_id: 5}
]

O que deve ser feito

Escreva um código que:

1. Receba a lista de funcionários. Não precisa se preocupar com stdin, copie e cole a estrutura acima
2. Crie uma estrutura hierárquica onde cada funcionário inclui uma lista de seus subordinados chamados subordinates.
3. Mantenha a imutabilidade das estruturas de dados durante a transformação.
4. Retorne essa estrutura organizada.
5. Teste manualmente ou de preferência com testes automatizados.

Exemplo de Resultado

A estrutura final deve parecer com esse formato (em JS):

{
    id: 1,
    name: "Founder & CEO",
    subordinates: [
        {
            id: 2,
            name: "Chief Technology Officer",
            subordinates: [
                {
                    id: 4,
                    name: "Marketing Manager",
                    subordinates: [
                        {
                            id: 10,
                            name: "Marketing Specialist",
                            subordinates: []
                        }
                    ]
                }
            ]
        },
        {
            id: 3,
            name: "Head of Engineering",
            subordinates: [
                {
                    id: 5,
                    name: "Engineering Lead",
                    subordinates: [
                        {
                            id: 6,
                            name: "Software Engineer",
                            subordinates: []
                        }
                    ]
                }
            ]
        }
    ]
}

Dicas para Resolver

• Identifique o CEO: É o funcionário cujo parent_id é nulo.
• Construa a estrutura de forma imutável: Evite modificar a lista original. Em vez disso, crie novas estruturas à medida que constrói a hierarquia.
• Use funções puras: Prefira funções que não causam efeitos colaterais, facilitando a manutenção e testabilidade do código.
• Utilize estruturas auxiliares: Pode ser útil usar um dicionário ou mapa para acessar rapidamente os funcionários pelo ID.

Referências Úteis

• Estruturas de Dados:

  • Árvore (Estrutura de Dados)
  • Mapas e Dicionários

• Algoritmos:

  • Recursão
  • Algoritmos de Busca e Inserção em Árvores

• Programação Funcional e Imutabilidade:

  • Princípios de Programação Funcional

Bom Desafio!

Divirta-se resolvendo esse desafio! Se tiver dúvidas ou precisar de ajuda, pergunte neste gist!

haapy hacking 🖤

Um pythin 🐍 das massas, pra diversao

from functools import reduce

if __name__ == "__main__":
    employees = [
        {"id": 10, "name": "Marketing Specialist", "parent_id": 4},
        {"id": 3, "name": "Head of Engineering", "parent_id": 1},
        {"id": 1, "name": "Founder & CEO", "parent_id": None},
        {"id": 2, "name": "Chief Technology Officer", "parent_id": 1},
        {"id": 4, "name": "Marketing Manager", "parent_id": 2},
        {"id": 5, "name": "Engineering Lead", "parent_id": 3},
        {"id": 6, "name": "Software Engineer", "parent_id": 5},
    ]

    def hierarchy(acc, cur):
        if not cur["parent_id"]:
            return {"id": cur["id"], "name": cur["name"], "subordinates": []}
        if acc.get("id") == cur["parent_id"]:
            return {
                **acc,
                "subordinates": [
                    *acc.get("subordinates", []),
                    *[{"id": cur["id"], "name": cur["name"], "subordinates": []}],
                ],
            }
        return {
            **acc,
            "subordinates": sorted(
                list(map(lambda sub: hierarchy(sub, cur), acc.get("subordinates", []))), key=lambda e: e["id"]
            ),
        }

    k = reduce(hierarchy, sorted(employees, key=lambda e: e["parent_id"] or 0), {})
    print(k)

    # {
    #     "id": 1,
    #     "name": "Founder & CEO",
    #     "subordinates": [
    #         {
    #             "id": 2,
    #             "name": "Chief Technology Officer",
    #             "subordinates": [
    #                 {
    #                     "id": 4,
    #                     "name": "Marketing Manager",
    #                     "subordinates": [
    #                         {
    #                             "id": 10,
    #                             "name": "Marketing Specialist",
    #                             "subordinates": [],
    #                         }
    #                     ],
    #                 }
    #             ],
    #         },
    #         {
    #             "id": 3,
    #             "name": "Head of Engineering",
    #             "subordinates": [
    #                 {
    #                     "id": 5,
    #                     "name": "Engineering Lead",
    #                     "subordinates": [
    #                         {
    #                             "id": 6,
    #                             "name": "Software Engineer",
    #                             "subordinates": [],
    #                         }
    #                     ],
    #                 }
    #             ],
    #         },
    #     ],
    # }