Num fluxo contínuo de dados com memória limitada, deseja-se testar rapidamente se um dado já apareceu…

Questão

Num fluxo contínuo de dados com memória limitada, deseja-se testar rapidamente se um dado já apareceu, aceitando alguns falsos positivos mas sem falsos negativos. Qual estrutura técnica é indicada?

1. A) Armazenar dados em uma árvore binária para testes rápidos.
2. B) Utilizar um hashmap para rastrear a frequência de dados.
3. C) Implementar uma lista de verificação simples em vez de filtro de Bloom.
4. D) Usar um filtro de Bloom configurado com k funções de hash.
5. E) Usar um conjunto tradicional para armazenar dados já vistos.

✅ Resposta correta: alternativa D

Resolução passo a passo

1. O enunciado pede uma estrutura para testar rapidamente se um dado já apareceu, em fluxo contínuo, com memória limitada, aceitando falsos positivos e não aceitando falsos negativos. Passo 2: Essa combinação de requisitos é exatamente a característica do filtro de Bloom, que usa um vetor de bits e k funções de hash. Se o elemento foi inserido, todos os k bits estarão ligados, então nunca ocorre falso negativo; porém, bits ligados por outros elementos podem gerar falso positivo. Passo 3: Por isso a alternativa D está correta e corresponde ao gabarito oficial. Passo 4: A alternativa A está errada porque uma árvore binária armazena os dados inteiros, consumindo muita memória em fluxos contínuos, e não oferece a relação probabilística pedida. Passo 5: A alternativa B está errada porque um hashmap guarda cada chave e a frequência, exigindo memória proporcional ao número de dados, o que conflita com a restrição de memória limitada. Passo 6: A alternativa C está errada porque uma lista de verificação simples guarda todos os itens, cresce sem limite e não é uma solução de espaço reduzido. Passo 7: A alternativa E está errada porque um conjunto tradicional também armazena todos os dados já vistos, sendo exato, mas sem controle de memória. Passo 8: Conclusão: o único método que equilibra memória limitada, ausência de falsos negativos e tolerância a falsos positivos é o filtro de Bloom com k funções de hash.

💡 Dica: Considere as características das estruturas de dados em computação.

Alternativa por alternativa

Raio-X da questão

Questões parecidas com resolução

• Após chuvas intensas, um ponto comunitário passou a organizar entregas de kits de higiene para famílias cadastradas. Os…
• “Uma fala apagada por engano não pode desaparecer do acervo”, observou a responsável pela digitalização de depoimentos…
• — Se fecharmos a válvula errada, o posto de saúde fica sem água — alertou a técnica durante a revisão do sistema…
• — Meu número é 12, mas há pessoas com atendimento prioritário antes de mim — observou uma moradora durante um mutirão de…
• — A fila está dobrando a esquina — avisou um voluntário da cozinha comunitária, enquanto outra pessoa anotava, em um…
• Uma professora quer calcular o total de pontos de cada aluno e percebe que a planilha atualiza os resultados quando o…

Todas as questões de Programação - Projetos com programação