Visto
Programação
Google
Gemini 2.5 Flash
VS
OpenAI
GPT-5.2
Implemente uma Skip List Concorrente Sem Bloqueios com Consultas por Intervalo
Design e implemente uma estrutura de dados skip list concorrente em uma linguagem de sua escolha (C++, Java, Rust, Go ou Python) que suporte as seguintes operações:
1. **insert(key, value)** – Insere um par chave-valor. Se a chave já existir, atualize o valor de forma atômica. Retorna true se uma nova chave foi inserida, false se foi atualizada.
2. **remove(key)** – Remove logicamente o par chave-valor. Retorna true se a chave foi encontrada e removida, false caso contrário.
3. **find(key)** – Retorna o valor associado à chave, ou indica ausência.
4. **range_query(low, high)** – Retorna todos os pares chave-valor onde low <= key <= high, como uma lista ordenada por chave. O resultado deve ser um snapshot consistente: não deve incluir chaves que nunca estiveram simultaneamente presentes durante a execução da operação.
5. **size()** – Retorna o número aproximado de elementos ativos (não deletados).
Requisitos e restrições:
- A skip list deve ser segura para uso concorrente por múltiplas threads realizando qualquer combinação das operações acima simultaneamente, sem um bloqueio global único. Você pode usar bloqueios de granularidade fina, técnicas sem bloqueio (CAS) ou uma combinação.
- Exclusão preguiçosa é aceitável: nós podem ser marcados logicamente como deletados antes da remoção física.
- A geração de nível probabilística deve usar uma distribuição geométrica padrão com p=0.5 e nível máximo de 32.
- Chaves são inteiros de 64 bits; valores são strings.
- Inclua considerações adequadas sobre segurança de memória. Se usar uma linguagem sem coleta de lixo, explique ou implemente sua estratégia de recuperação (por exemplo, recuperação baseada em épocas, hazard pointers).
Entregáveis:
1. Código-fonte completo e compilável/executável com comentários explicando sua estratégia de concorrência.
2. Um teste ou demonstração que lance múltiplas threads realizando inserções, exclusões, buscas e consultas por intervalo concorrentes, e valide a correção (por exemplo, sem atualizações perdidas, sem leituras fantasmas em consultas por intervalo, sem travamentos).
3. Uma seção de análise breve (como comentários ou uma docstring) discutindo:
- As garantias de linearizabilidade (ou isolamento por snapshot) que sua implementação fornece.
- A complexidade de tempo esperada de cada operação.
- Limitações conhecidas ou possíveis problemas ABA e como você os aborda.
Sua solução será avaliada com base na correção sob concorrência, clareza do código, robustez da estratégia de concorrência, qualidade do mecanismo de snapshot para consultas por intervalo e completude da análise.
