Pular para o conteúdo

Quórum de leitura dado o de escrita

Fácil#quorum#pigeonhole~10 min

A missão

Problema

Um armazenamento chave-valor replicado mantém cada chave em n réplicas. Uma escrita tem sucesso quando w réplicas a confirmam, e uma leitura consulta r réplicas e fica com a versão mais nova que encontrar. Uma leitura só tem a garantia de ver a última escrita bem-sucedida se todo conjunto de leitura possível compartilhar pelo menos uma réplica com todo conjunto de escrita possível. Dados n e w, retorne o menor r com essa propriedade, junto com quantas réplicas podem estar fora do ar enquanto leituras e escritas ainda conseguem ter sucesso.

Exemplos

Input:  n = 3, w = 2
Output: (2, 1)
Por quê: quaisquer 2 de 3 se sobrepõem a quaisquer outras 2 de 3, e 1 réplica pode ser perdida
Input:  n = 5, w = 3
Output: (3, 2)
Input:  n = 3, w = 3
Output: (1, 0)
Por quê: edge case: toda escrita chega a todas as réplicas, então uma réplica basta para ler, mas nenhuma pode falhar

Dicas

0 / 3

Tempo-alvo
O(1)
Espaço-alvo
O(1)

Travou na ideia, e não no código? Consistência e teorema CAP explica isso.

Python 3Ctrl+Enter executa
Caso de teste personalizado