Descreva um algoritmo generalizado (inclua assinatura e pseudocódigo) que receba duas coleções de registros e…

Questão

Descreva um algoritmo generalizado (inclua assinatura e pseudocódigo) que receba duas coleções de registros e um parâmetro 'chave' para combinar registros (join). Explique como tratar registros sem correspondência e estime a complexidade.

✍️ Questão dissertativa: veja abaixo a resposta esperada e a explicação.

Resposta esperada

Assinatura: join(colecaoA: List<Record>, colecaoB: List<Record>, chave: String, includeUnmatched: Bool) -> List<Record> Pseudocódigo (hash-join): mapa <- novo dicionário para cada r em colecaoA: if r[chave] existe then mapa[r[chave]] <- mapa[r[chave]] ? [r] resultado <- lista vazia para cada s em colecaoB: chaveS <- s[chave] se chaveS existe em mapa: para cada r em mapa[chaveS]: resultado.adicionar(combinar(r,s)) senao se includeUnmatched: resultado.adicionar(combinar(null,s)) se includeUnmatched: para cada entradas em mapa sem correspondência: resultado.adicionar(combinar(r,null)) Tratamento de chaves ausentes: optar entre pular registros ou incluir pares com null conforme parâmetro includeUnmatched; registrar erros quando chave obrigatória estiver faltando. Complexidade: com tabela hash, tempo esperado O(n + m) e espaço O(n) (n = |colecaoA|, m = |colecaoB|). Alternativa ingênua (forças brutas) tem custo O(n·m).

Explicação

O algoritmo apresentado utiliza uma abordagem eficiente de hash-join, que permite combinar registros de duas coleções com base em uma chave, garantindo que a busca por correspondências seja rápida. A inclusão do parâmetro 'includeUnmatched' permite flexibilidade no tratamento de registros sem correspondência, permitindo ao usuário decidir se esses registros devem ser incluídos na saída. A análise de complexidade mostra que a abordagem hash é significativamente mais eficiente do que uma abordagem ingênua, especialmente para coleções grandes.

Raio-X da questão

Questões parecidas com resolução

• Crie e descreva um algoritmo, em linguagem simples ou pictográfica, que ajude uma criança a decidir se deve levar um…
• Crie um algoritmo em linguagem oral ou escrita que controle a rega de um vaso por 7 dias: diariamente verificar se…
• Projete em pseudocódigo um algoritmo que reconstrua uma mensagem a partir de pacotes recebidos onde cada pacote contém…
• Elabore em pseudocódigo um algoritmo que, dado um vetor de registros 'tarefas' (descricao, duracao_horas, prioridade) e…
• Elabore em pseudocódigo um algoritmo que, dado um array de registros 'alunos' com campos (nome, notas[4]…
• Projete um algoritmo e descreva as estruturas de dados para implementar operações de desfazer/refazer (undo/redo) em um…

Todas as questões de Algoritmos