Você recebe um arquivo que contém todos os números possíveis em uma arquitetura de 32 bits. Faltam 4 números nesse arquivo. Encontre os 4 números que faltam

Esta é uma pergunta de entrevista que eu me deparei algumas vezes, e realmente não tenho certeza de como resolvê-la, pois faltam quatro números. Estou familiarizado com algoritmos para encontrar um ou dois números ausentes, mas não vejo uma maneira de generalizar nenhum deles para quatro.

Seja para uma entrevista ou para um trabalho real, sua primeira prioridade precisa ser uma solução funcional que faça sentido para você . Isso normalmente significa que você deve oferecer a primeira solução que você pode pensar que é simples e fácil para você explicar.

Para mim, isso significa classificar os números e procurar falhas. Mas trabalho em sistemas comerciais e aplicativos da web. Não brinco com pedaços, e não quero que minha equipe!

Se você estiver entrevistando para um trabalho de baixo nível e mais próximo do metal, a "classificação" provavelmente será vista com olhares em branco. Eles querem que você se sinta confortável com os bits e assim por diante. Sua primeira resposta deve ser "Ah, eu usaria um bitmap". (Ou matriz de bits ou conjunto de bits).

E então, de qualquer maneira - mesmo se você der uma solução "errada", se o entrevistador (ou o chefe!) Pressionar por isso , poderá sugerir algumas melhorias ou alternativas, concentrando-se na área de preocupação específica do gerente.

• RAM gravemente limitada? Menos de 512MB?
  Classifique-o no lugar, no disco. Você pode usar uma quantidade de RAM principalmente arbitrária para otimizar e / ou armazenar em buffer os blocos classificados.
• Tempo limitado?
  Use essa RAM! A classificação já está O(n*log(n)). (Ou O (n) para uma classificação de número inteiro!)
• Manutenção?
  O que poderia ser mais fácil do que classificar ?!
• Não demonstra conhecimento de sinalizadores / campos de bits? ( BitSet/ BitMap/ BitArray)
  Bem, OK ... vá em frente e use a BitArraypara sinalizar os "números encontrados". E então procure por 0.
• Complexidade previsível em "tempo real"?
  Use a solução de bitmap. É uma única passagem sobre o arquivo e outra sobre oBitArray/BitSet(para encontrar os0). Isso éO(n), eu acho!

Como queiras.

Aborde as preocupações que você realmente tem. Apenas resolva o problema primeiro, usando soluções ingênuas, se necessário. Não perca o tempo de todos abordando preocupações que ainda não existem.

Como é um arquivo, suponho que você tenha permissão para fazer várias passagens. Primeiro, crie uma matriz de 256 contadores, itere sobre o arquivo e para cada número incremente o contador indexado como o primeiro byte do número. Quando terminar, a maioria dos contadores deve estar em 2 ^ 24, mas 1 a 4 contadores devem ter valores mais baixos. Cada um desses índices representa um primeiro byte de um dos números ausentes (se houver menos de 4, é porque vários números ausentes compartilham o mesmo primeiro byte).

Para cada um desses índices, crie outra matriz de 256 contadores e faça uma segunda passagem no arquivo. Dessa vez, se o primeiro byte for um dos valores anteriores, aumente um contador em sua matriz com base no segundo byte. Quando terminar, procure novamente os contadores menores que 2 ^ 16 e você terá o segundo byte dos números ausentes, cada um correspondente ao primeiro byte.

Faça isso novamente para o terceiro byte (observe que você precisa de no máximo 4 matrizes em cada passagem, mesmo que cada byte possa ser seguido por até 4 bytes diferentes) e para o quarto byte, e você encontrou todos os números ausentes.

Complexidade do tempo - complexidade do O(n * log n)
espaço - constante !

Editar:

Na verdade, considerei o n=2^32parâmetro, mas o número de números ausentes k=4também é um parâmetro. Supondo que k<<nisso signifique a complexidade do espaço O(k).

Atualizar:

Apenas por diversão (e porque atualmente estou tentando aprender Rust), eu o implementei no Rust: https://gist.github.com/idanarye/90a925ebb2ea57de18f03f570f70ea1f . Optei por ter uma representação textual, já que on-one a executará com ~ 2 ^ 32 números ...

Se fosse Java, você poderia usar um BitSet. Bem, dois deles, porque eles não conseguem conter todos os números de 32 bits. Código esquelético, talvez com erros:

BitSet bitsetForPositives = new Bitset(2^31);  // obviously not 2^31 but you get the idea
BitSet bitsetForNegatives = new Bitset(2^31);

for (int value: valuesTheyPassInSomehow) {
  if ((value & 0x80000000) == 0)
     bitsetForPositives.set(value );
  else
     bitsetForNegatives.set(value & ~0x80000000);
}

Em seguida, use BitSet.nextClearBit()para encontrar quem está faltando.

Nota adicionada muito mais tarde:

Observe que, com esse algoritmo, é bastante fácil executar a parte demorada em paralelo . Digamos que o arquivo original tenha sido dividido em quatro partes aproximadamente iguais. Aloque 4 pares de BitSets (2 GB, ainda gerenciáveis).

1. Tenha quatro threads, em paralelo, cada processo um arquivo em seu próprio par de BitSets.
2. Quando terminar, volte para um único encadeamento, ou Bitsets (horário trivial), e chame nextClearBit quatro vezes (também bastante trivial).

Eu esperaria que a E / S ainda fosse a etapa de limitação da taxa, mas se magicamente todos os números estivessem na memória, você poderia realmente acelerar as coisas.

Esta questão pode ser resolvida usando uma matriz de bits (verdadeiro / falso). Essa deve ser a estrutura mais eficiente para armazenar as respostas para todos os números usando o índice da matriz para armazenar se esse número específico foi encontrado.

C #

var bArray = new BitArray(Int32.MaxValue);

//Assume the file has 1 number per line
using (StreamReader sr = File.OpenText(fileName))
{
        string s = String.Empty;
        while ((s = sr.ReadLine()) != null)
        {
            var n = int32.Parse(s);
            bArray[n] = true;
        }
}

Em seguida, basta percorrer a matriz e, para os valores que ainda são falsos, eles não estão no arquivo.

Você poderia dividir o arquivo em pedaços menores, mas eu consegui alocar uma matriz de tamanho máximo int32 total (2147483647) no meu laptop de 16,0 GB com Windows 7 (64 bits).

Mesmo se não estivesse executando 64 bits, eu poderia alocar matrizes de bits menores. Eu pré-processava o arquivo criando um conjunto de arquivos menores, cada um com um intervalo de [0-64000] [64001-128000] etc. números que seriam adequados para os recursos ambientais disponíveis. Percorra o arquivo grande e escreva cada número no arquivo definido correspondente. Em seguida, processe cada arquivo menor. Levaria um pouco mais de tempo por causa da etapa de pré-processamento, mas isso contornaria as limitações de recursos se houvesse recursos limitados.

Como se trata de uma pergunta de entrevista, eu mostraria ao entrevistador algum entendimento sobre as restrições. Então, o que significa "todos os números possíveis"? É realmente 0 ... 2 <(32-1) como todos imaginam? As arquiteturas comuns de 32 bits podem funcionar com muito mais do que números de 32 bits. É apenas uma questão de representação, obviamente.

Isso precisa ser resolvido em um sistema de 32 bits ou isso faz parte da restrição de números? Por exemplo, um sistema típico de 32 bits não poderá carregar o arquivo na RAM de uma só vez. Eu também mencionaria que um sistema de 32 bits geralmente não poderá ter um arquivo contendo todos os números devido à limitação do tamanho do arquivo. Bem, a menos que tenha alguma codificação inteligente, como "Todos os números, exceto os quatro", caso em que o problema é resolvido trivialmente.

Mas se você realmente deseja entender a pergunta como "Dado um arquivo com todos os números de 0 ... 2 ^ (32-1), exceto alguns, dê-me alguns que faltam" (e esse é um grande se !), Então existem muitas maneiras de resolvê-lo.

Trivial, mas inviável: para cada número possível, verifique o arquivo e verifique se ele está lá.

Com 512 MB de RAM e arquivo de passagem única: marque cada número (= bit definido nesse índice) lido no arquivo e depois passe a RAM uma vez e veja os que estão faltando.

Uma abordagem fácil de lembrar e articular em uma entrevista seria usar o fato de que, se você olhar para todos os números em N bits, cada bit será definido exatamente na metade desses valores e não na outra metade .

Se você iterar sobre todos os valores no arquivo e manter 32 contagens dos valores no final, você terá 32 valores exatamente (2 ^ 32/2) ou ligeiramente inferiores a esse valor. A diferença que máximo (2 ^ 32/2) e o total fornece o total de bits definido em cada posição dos valores ausentes.

Depois de ter isso, você pode determinar todos os conjuntos possíveis de 4 valores que poderiam fornecer esses totais. Dado isso, é possível revisar os valores no arquivo novamente, verificando os valores que fazem parte dessas combinações. Quando você encontra uma, as combinações que contêm esse valor são eliminadas como possibilidades. Depois de ter apenas uma combinação possível, você responde.

Por exemplo, usando um nibble, você tem os seguintes valores:

1010
0110
1111
0111
1101
1001
0100
0101
0001
1011
1100
1110

O total de bits definidos em cada posição é:

7867

Subtraindo os de 8 (4 ^ 2/2), obtemos:

1021

O que significa que existem os seguintes conjuntos possíveis de 4 valores:

1000
0000
0011
0010

1010
0001
0010
0000

(me perdoe se eu perdi alguma, estou apenas fazendo isso de vista)

E então, olhando para os números originais novamente, encontramos 1010 imediatamente, o que significa que o primeiro conjunto foi a resposta.

Supondo que o arquivo seja classificado por números crescentes:

Certifique-se de que o indeed contenha (2³²-4) números.
Agora, se o arquivo estiver completo (ou se os 4 números ausentes forem os últimos 4), a leitura de qualquer palavra no arquivo na posição N retornará o valor correspondente N.

Use uma pesquisa de dicotomia nas posições [0..2³²-4-1) para pesquisar e encontrar o primeiro número não esperado X1.
Depois de encontrar o primeiro número ausente, faça uma pesquisa de dicototomia novamente nas posições [X1 .. (2³²-4-1)] para encontrar o segundo ausente, X2: Desta vez, lendo uma palavra na posição N deve retornar o valor correspondente N-1 se não houvesse mais números ausentes (desde que você passou um número ausente).
Iterar da mesma forma para os dois números restantes. Na terceira iteração, a leitura da palavra na posição N deve retornar N-2 e, na quarta, deve retornar N-3.

Advertência: Eu não testei isso. Mas acho que deve funcionar. :)

Agora, na vida real, concordo com outras respostas: as primeiras perguntas seriam sobre o meio ambiente. Temos RAM disponível (quanto), é o arquivo em um dispositivo de armazenamento de acesso direto, é uma operação de tiro único (sem necessidade de otimização) ou crítica (cada contagem de ciclo), temos um utilitário de classificação externo disponível , etc.
Em seguida, encontre um compromisso aceitável para o contexto. Pelo menos isso mostra que você começa a analisar o problema antes de procurar um algoritmo.

Como em todas as perguntas padrão, a solução é pesquisá-las no Google antes da entrevista.

Esta pergunta e variações têm uma resposta 'correta' muito definida, envolvendo XOR em todos os números. É suposto mostrar que você entende índices em bancos de dados ou algo assim. Portanto, zero ponto para qualquer resposta "pode ​​funcionar, mas não o que está escrito no papel", está imenso.

No lado positivo, há um conjunto finito dessas perguntas. Uma revisão de algumas horas fará com que você pareça um gênio. Lembre-se de fingir que está trabalhando na sua cabeça.

Editar. Ahh, parece que para 4 existe uma abordagem diferente da XOR

http://books.google.com/books?id=415loiMd_c0C&lpg=PP1&dq=muthukrishnan%20data%20stream%20algorithms&hl=el&pg=PA1#v=onepage&q=muthukrishnan%20data%20stream%20algorithms&f=false

Editar. Downvoters: Esta é uma solução de livro publicado O (n) para o problema exato indicado no OP.