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

• Você precisa armazenar uma coleção onde testar a existência de um elemento seja muito rápido e a ordem dos elementos não…
• Ao projetar um algoritmo que detecta padrões em uma sequência de eventos, qual estrutura de dados facilita buscas e…
• Em um algoritmo que processa uma lista de alunos como dados e precisa evitar registros duplicados, qual estrutura de…
• Um programa guarda muitos números, precisa inserir e remover números com frequência e fazer buscas rápidas, sem…
• Em um algoritmo que deve verificar rapidamente se um código de estudante já existe em uma grande coleção de dados, qual…
• Em um programa que simula um caixa eletrônico, é preciso consultar se um número de conta está cadastrado e impedir que…

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