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 🖤

minha versão:

#!/usr/bin/env elixir
defmodule Batata do
  @moduledoc "sla gosto de batata"

  # pra ficar fácil de ler
  # o compilador ainda n usa de fato
  @type employee :: %{id: integer, name: String.t(), parent_id: integer}
  @type group :: %{integer => employee}
  @type leaf :: %{id: integer, name: String.t(), subordinates: list(node)}

  @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}
  ]

  @spec get_employees :: list(employee)
  def get_employees, do: @employees

  @spec make_tree(list(employee)) :: leaf
  def make_tree(employees) do
    parent_to_children = Enum.group_by(employees, & &1.parent_id)
    ceo = Enum.find(employees, &is_nil(&1.parent_id))

    ceo && make_subtree(ceo, parent_to_children)
  end

  @spec make_subtree(employee, group) :: leaf
  defp make_subtree(employee, parent_to_children) do
    maybe_children = Map.get(parent_to_children, employee.id)
    subordinates = take_subordinates(maybe_children, parent_to_children)

    employee
    |> Map.put(:subordinates, subordinates)
    |> Map.delete(:parent_id)
  end

  @spec take_subordinates(list(employee) | nil, group) :: list(leaf)
  defp take_subordinates(nil, _), do: []

  defp take_subordinates(children, group) do
    Enum.map(children, &make_subtree(&1, group))
  end
end

# só pra imprimir bonitinho ^-^
# tô redefinindo a implementação nativa do tipo Map - %{}
# daria pra criar um struct só pra isso, mas nha
defimpl Inspect, for: Map do
  def inspect(node, opts) do
    inspect_node(node, opts, 0)
  end

  defp inspect_node(%{name: name, id: id, subordinates: sub}, _opts, level) do
    indent = String.duplicate("  ", level)
    header = indent <> "#{name} (id: #{id})"

    if Enum.empty?(sub) do
      header
    else
      subordinates_inspect =
        sub
        |> Enum.map(&inspect_node(&1, nil, level + 1))
        |> Enum.join("\n")

      header <> "\n" <> subordinates_inspect
    end
  end
end

# testes yaya
ExUnit.start(autorun: false)

defmodule BatataTest do
  use ExUnit.Case

  alias Batata

  describe "make_tree/1" do
    test "builds the correct hierarchical tree from the employee list" do
      employees = Batata.get_employees()

      assert %{
               id: 1,
               subordinates: [
                 %{
                   id: 3,
                   subordinates: [%{id: 5, subordinates: [%{id: 6}]}]
                 },
                 %{
                   id: 2,
                   subordinates: [%{id: 4, subordinates: [%{id: 10}]}]
                 }
               ]
             } = Batata.make_tree(employees)
    end

    test "returns nil when there is no CEO (parent_id is nil)" do
      employees = [
        %{id: 2, name: "Employee A", parent_id: 1},
        %{id: 3, name: "Employee B", parent_id: 2}
      ]

      assert Batata.make_tree(employees) == nil
    end

    test "returns nil when employee list is empty" do
      assert Batata.make_tree([]) == nil
    end

    test "builds tree with single employee (CEO only)" do
      employees = [
        %{id: 1, name: "Founder & CEO", parent_id: nil}
      ]

      expected_tree = %{
        id: 1,
        name: "Founder & CEO",
        subordinates: []
      }

      assert Batata.make_tree(employees) == expected_tree
    end

    test "handles employees without subordinates correctly" do
      employees = [
        %{id: 1, name: "Founder & CEO", parent_id: nil},
        %{id: 2, name: "Lone Employee", parent_id: 1}
      ]

      expected_tree = %{
        id: 1,
        name: "Founder & CEO",
        subordinates: [
          %{
            id: 2,
            name: "Lone Employee",
            subordinates: []
          }
        ]
      }

      assert Batata.make_tree(employees) == expected_tree
    end

    test "handles multiple top-level employees (multiple CEOs)" do
      employees = [
        %{id: 1, name: "Founder & CEO", parent_id: nil},
        %{id: 2, name: "Co-Founder & CEO", parent_id: nil},
        %{id: 3, name: "Employee A", parent_id: 1},
        %{id: 4, name: "Employee B", parent_id: 2}
      ]

      # o algoritmo no momento paenas olha pra 1 única raiz
      # então o CEO vai ser apenas o 1˚ a ser considerado
      expected_tree = %{
        id: 1,
        name: "Founder & CEO",
        subordinates: [
          %{
            id: 3,
            name: "Employee A",
            subordinates: []
          }
        ]
      }

      actual_tree = Batata.make_tree(employees)

      assert actual_tree == expected_tree
    end

    test "handles cyclic references gracefully" do
      employees = [
        %{id: 1, name: "Employee A", parent_id: 2},
        %{id: 2, name: "Employee B", parent_id: 1}
      ]

      # deveria apenas ignorar e retornar nulo
      refute Batata.make_tree(employees)
    end
  end
end

# rodando
case System.argv() do
  ["--test"] ->
    ExUnit.run([BatataTest])

  _ ->
    Batata.get_employees()
    |> Batata.make_tree()
    |> IO.inspect()
end

Screen.Recording.2024-11-11.at.19.23.46.mov

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": [],
    #                         }
    #                     ],
    #                 }
    #             ],
    #         },
    #     ],
    # }