Conteúdo do curso Lição 76 de 148 · Limites ímpares
Limites ímpares

Primeiro offline

Por que isso importa "Envie a lista toda, a última escrita vence" funciona até dois dispositivos editarem enquanto estiverem offline. Então as edições de uma pessoa somem silenciosamente, e ninguém consegue dizer para onde elas foram.

O app de lista de compras

A deve funcionar no subsolo de um supermercado sem sinal. Cada dispositivo mantém um log do que fez. Quando os dispositivos se reconectam, os dois logs são mesclados em uma única lista. Ambos os logs começam com o mesmo histórico compartilhado (tudo sincronizado antes de ficarem offline), depois cada um tem suas próprias edições.

Log de operação: um registro das mudanças feitas (adicione isso, remova aquilo), em vez de uma cópia do resultado. Logs podem ser mesclados; cópias só podem sobrescrever.

("add", "milk", "p7")             # tag p7 is unique to this add
("remove", "milk", ["p7", "s2"])  # removes exactly the adds this device had seen
Sua vez

Escreva merge(log_a, log_b) e retorne a lista ordenada de itens na lista de compras mesclada (cada item uma vez). Um log é uma lista de operações: ("add", item, tag), onde cada add tem uma tag única, e ("remove", item, tags), onde tags lista os adds daquele item que o dispositivo pôde ver quando o removeu.

Limits. Nenhuma edição pode ser perdida: um item está na lista se pelo menos um de seus adds nunca foi removido. Um remove cancela apenas as tags que ele lista, então um add que o outro dispositivo fez enquanto estava offline sobrevive. Ambos os logs podem conter as mesmas operações compartilhadas (conte-as uma vez). merge(a, b) deve ser igual a merge(b, a).

Viu um problema nesta lição? Reporte-o · Pergunte sobre esta lição

Este exercício abre em breve

Termine a lição anterior para que esta seja desbloqueada. O curso inteiro é gratuito, não precisa de conta, e você pode ler esta lição agora mesmo.