A questão da entrevista fácil ficou mais difícil: dados números 1..100, encontre o (s) número (s) faltante (s)

Eu tive uma interessante experiência de entrevista de emprego há algum tempo. A questão começou muito fácil:

Q1 : Temos uma bolsa contendo números 1 , 2 , 3 ,…, 100 . Cada número aparece exatamente uma vez, portanto, há 100 números. Agora um número é escolhido aleatoriamente da sacola. Encontre o número que falta.

Eu ouvi essa pergunta da entrevista antes, claro, então eu respondi rapidamente ao longo das linhas de:

A1 : Bem, a sum dos números 1 + 2 + 3 + … + N é (N+1)(N/2) (ver Wikipedia: sum das séries aritméticas ). Para N = 100 , a sum é 5050 .

Assim, se todos os números estiverem presentes no saco, a sum será exatamente 5050 . Como um número está faltando, a sum será menor que isso, e a diferença é esse número. Assim, podemos encontrar o número que falta no tempo O(N) e no espaço O(1) .

Nesse ponto, achei que tinha ido bem, mas de repente a pergunta deu uma guinada inesperada:

Q2 : Isso está correto, mas agora como você faria isso se dois números estão faltando?

Eu nunca tinha visto / ouvido / considerado essa variação antes, então entrei em pânico e não pude responder à pergunta. O entrevistador insistiu em conhecer o meu processo de pensamento, então eu mencionei que talvez possamos obter mais informações comparando com o produto esperado, ou talvez fazendo um segundo passe depois de ter reunido algumas informações do primeiro passe, etc, mas eu realmente estava apenas atirando no escuro, em vez de realmente ter um caminho claro para a solução.

O entrevistador tentou me encorajar dizendo que ter uma segunda equação é de fato uma maneira de resolver o problema. Neste ponto eu fiquei meio chateado (por não saber a resposta antes da mão), e perguntei se esta é uma técnica de programação geral (leia-se: “útil”), ou se é apenas uma resposta de truque / pegadinha.

A resposta do entrevistador me surpreendeu: você pode generalizar a técnica para encontrar 3 números ausentes. Na verdade, você pode generalizá-lo para encontrar os números que faltam.

Qk : Se exatamente k números estão faltando na bolsa, como você vai encontrá-lo de forma eficiente?

Isso foi há alguns meses e ainda não consegui descobrir o que é essa técnica. Obviamente, existe um limite inferior de Ω(N) , já que devemos varrer todos os números pelo menos uma vez, mas o entrevistador insistiu que a complexidade TIME e SPACE da técnica de resolução (menos a varredura de input de tempo O(N) ) é definida em k não N.

Então a questão aqui é simples:

  • Como você resolveria o Q2 ?
  • Como você resolveria o Q3 ?
  • Como você resolveria Qk ?

Esclarecimentos

  • Geralmente existem N números de 1 .. N , não apenas 1..100.
  • Eu não estou olhando para a solução óbvia baseada em conjunto, por exemplo, usando um conjunto de bits , codificando a presença / ausência de cada número pelo valor de um bit designado, portanto, usando O(N) bits no espaço adicional. Não podemos arcar com nenhum espaço adicional proporcional ao N.
  • Eu também não estou procurando pela óbvia abordagem de ordenação inicial. Esta e a abordagem baseada em conjuntos merecem ser mencionadas em uma entrevista (elas são fáceis de implementar e, dependendo de N , podem ser muito práticas). Estou procurando a solução do Santo Graal (que pode ou não ser prática de implementar, mas tem as características assintóticas desejadas).

Então, novamente, é claro que você deve escanear a input em O(N) , mas você só pode capturar uma pequena quantidade de informação (definida em termos de k não N ), e então encontrar os k números que faltam de alguma forma.

Aqui está um resumo do link de Dimitris Andreou .

Lembre-se da sum dos i-és poderes, onde i = 1,2, .., k. Isso reduz o problema para resolver o sistema de equações

a 1 + a 2 + … + a k = b 1

a 1 2 + a 2 2 + … + a k 2 = b 2

a 1 k + a 2 k + … + a k k = b k

Usando as identidades de Newton , sabendo que eu posso computar

c 1 = a 1 + a 2 + … a k

c 2 = a 1 a 2 + a 1 a 3 + … + a k-1 a k

c k = a 1 a 2 … a k

Se você expandir o polinômio (xa 1 ) … (xa k ) os coeficientes serão exatamente c 1 , …, c k – veja as fórmulas de Viète . Como todos os fatores polinomiais são únicos (o anel de polinômios é um domínio euclidiano ), isso significa que os i são determinados unicamente até a permutação.

Isso termina com uma prova de que lembrar poderes é o suficiente para recuperar os números. Para k constante, essa é uma boa abordagem.

No entanto, quando k está variando, a abordagem direta de calcular c 1 , …, c k é proibitivamente cara, pois, por exemplo, c k é o produto de todos os números faltantes, magnitude n! / (Nk) !. Para superar isto, execute cálculos no campo Z q , onde q é um primo tal que n <= q <2n - existe pelo postulado de Bertrand . A prova não precisa ser alterada, pois as fórmulas ainda são válidas e a fatoração de polinômios ainda é única. Você também precisa de um algoritmo para fatoração sobre campos finitos, por exemplo, o de Berlekamp ou Cantor-Zassenhaus .

Pseudocódigo de alto nível para constante k:

  • Calcule i-és poderes de números dados
  • Subtraia para obter sums do i-ésimo poder de números desconhecidos. Ligue para as sums b i .
  • Use as identidades de Newton para calcular os coeficientes de b i ; chame-os c i . Basicamente, c 1 = b 1 ; c 2 = (c 1 b 1 – b 2 ) / 2; veja Wikipedia para fórmulas exatas
  • Fator o polinômio xk- c 1 x k-1 + … + c k .
  • As raízes do polinômio são os números necessários a 1 , …, a k .

Para variar k, encontre um primo n <= q <2n usando, por exemplo, Miller-Rabin, e execute os passos com todos os números reduzindo o módulo q.

Como Heinrich Apfelmus comentou, ao invés de um q primo você pode usar q = 2 ⌈log n⌉ e realizar aritmética no campo finito .

Você vai encontrá-lo lendo o par de páginas de Muthukrishnan – Algoritmos de Fluxo de Dados: Quebra-cabeça 1: Encontrando números em falta . Mostra exatamente a generalização que você está procurando . Provavelmente é isso que o entrevistador leu e por que ele fez essas perguntas.

Agora, se apenas as pessoas começassem a deletar as respostas que são subsumidas ou substituídas pelo tratamento de Muthukrishnan, e tornem este texto mais fácil de encontrar. 🙂


Veja também a resposta diretamente relacionada do sdcvvc , que também inclui o pseudocódigo (não é necessário ler essas fórmulas matemáticas complicadas :)) (obrigado, ótimo trabalho!).

Podemos resolver Q2 sumndo os números em si e os quadrados dos números.

Podemos então reduzir o problema para

 k1 + k2 = x k1^2 + k2^2 = y 

Onde x e y são quanto as sums estão abaixo dos valores esperados.

Substituir nos dá:

 (x-k2)^2 + k2^2 = y 

O que podemos resolver para determinar nossos números ausentes.

Como @j_random_hacker apontou, isso é bastante semelhante a Encontrar duplicatas em tempo O (n) e espaço O (1) , e uma adaptação da minha resposta também funciona aqui também.

Assumindo que o “bag” é representado por um array baseado em 1 A[] de tamanho N - k , podemos resolver Qk em tempo O(N) e O(k) espaço adicional.

Primeiro, estendemos nosso array A[] por k elementos, de modo que agora ele é do tamanho N Este é o espaço adicional O(k) . Em seguida, executamos o seguinte algoritmo de pseudocódigo:

 for i := n - k + 1 to n A[i] := A[1] end for for i := 1 to n - k while A[A[i]] != A[i] swap(A[i], A[A[i]]) end while end for for i := 1 to n if A[i] != i then print i end if end for 

O primeiro loop inicializa as k inputs extras para o mesmo que a primeira input na matriz (este é apenas um valor conveniente que sabemos que já está presente na matriz – após essa etapa, todas as inputs que estavam faltando na matriz inicial de tamanho) Nk ainda estão faltando na matriz estendida).

O segundo loop permede o array estendido de forma que se o elemento x estiver presente pelo menos uma vez, então uma dessas inputs estará na posição A[x] .

Observe que, embora tenha um loop nested, ele ainda é executado no tempo O(N) – uma troca ocorre apenas se houver um i tal que A[i] != i , e cada troca define pelo menos um elemento de modo que A[i] == i , onde isso não era verdade antes. Isso significa que o número total de trocas (e, portanto, o número total de execuções do corpo do loop while) é no máximo N-1 .

O terceiro loop imprime os índices da matriz i que não estão ocupados pelo valor i – isso significa que i devo ter estado ausente.

Eu pedi a uma criança de 4 anos para resolver este problema. Ele classificou os números e depois contou. Isso tem um requisito de espaço de O (piso da cozinha) e funciona da mesma forma que muitas bolas estão faltando.

Não tenho certeza, se é a solução mais eficiente, mas eu faria um loop em todas as inputs, e usaria um bitset para lembrar, quais números são definidos e, em seguida, teste para 0 bits.

Eu gosto de soluções simples – e eu até acredito que pode ser mais rápido do que calcular a sum ou a sum dos quadrados etc.

Eu não chequei a matemática, mas eu suspeito que computação Σ(n^2) na mesma passagem que nós calculamos Σ(n) forneceria informação suficiente para obter dois números perdidos, Do Σ(n^3) também se existem três e assim por diante.

O problema com soluções baseadas em sums de números é que elas não levam em conta o custo de armazenar e trabalhar com números com grandes expoentes … na prática, para trabalhar para números muito grandes, uma biblioteca de números grandes seria usada . Podemos analisar a utilização do espaço para esses algoritmos.

Podemos analisar a complexidade temporal e espacial dos algoritmos do sdcvvc e Dimitris Andreou.

Armazenamento:

 l_j = ceil (log_2 (sum_{i=1}^ni^j)) l_j > log_2 n^j (assuming n >= 0, k >= 0) l_j > j log_2 n \in \Omega(j log n) l_j < log_2 ((sum_{i=1}^ni)^j) + 1 l_j < j log_2 (n) + j log_2 (n + 1) - j log_2 (2) + 1 l_j < j log_2 n + j + c \in O(j log n)` 

Então, l_j \in \Theta(j log n)

Armazenamento total utilizado: \sum_{j=1}^k l_j \in \Theta(k^2 log n)

Espaço usado: assumindo que calcular a^j leva tempo ceil(log_2 j) , tempo total:

 t = k ceil(\sum_i=1^n log_2 (i)) = k ceil(log_2 (\prod_i=1^n (i))) t > k log_2 (n^n + O(n^(n-1))) t > k log_2 (n^n) = kn log_2 (n) \in \Omega(kn log n) t < k log_2 (\prod_i=1^ni^i) + 1 t < kn log_2 (n) + 1 \in O(kn log n) 

Tempo total usado: \Theta(kn log n)

Se esse tempo e espaço forem satisfatórios, você poderá usar um algoritmo recursivo simples. Seja b i a input na bolsa, n o número de números antes das remoções e k o número de remoções. Na syntax de Haskell ...

 let -- O(1) isInRange low high v = (v >= low) && (v <= high) -- O(n - k) countInRange low high = sum $ map (fromEnum . isInRange low high . (!)b) [1..(nk)] findMissing l low high krange -- O(1) if there is nothing to find. | krange=0 = l -- O(1) if there is only one possibility. | low=high = low:l -- Otherwise total of O(knlog(n)) time | otherwise = let mid = (low + high) `div` 2 klow = countInRange low mid khigh = krange - klow in findMissing (findMissing low mid klow) (mid + 1) high khigh in findMising 1 (n - k) k 

Armazenamento usado: O(k) para lista, O(log(n)) para pilha: O(k + log(n)) Esse algoritmo é mais intuitivo, tem a mesma complexidade de tempo e usa menos espaço.

Espere um minuto. Como a pergunta é declarada, existem 100 números na bolsa. Não importa quão grande seja, o problema pode ser resolvido em tempo constante, porque você pode usar um conjunto e remover números do conjunto em no máximo 100 k iterações de um loop. 100 é constante. O conjunto de números restantes é sua resposta.

Se generalizarmos a solução para os números de 1 a N, nada muda, exceto que N não é uma constante, então estamos no tempo O (N – k) = O (N). Por exemplo, se usarmos um bit set, definimos os bits para 1 em O (N) time, iteramos os números, definimos os bits como 0 à medida que vamos (O (Nk) = O (N)) e então tem a resposta.

Parece-me que o entrevistador estava perguntando a você como imprimir o conteúdo do conjunto final no tempo O (k) ao invés do tempo O (N). Claramente, com um pouco definido, você tem que percorrer todos os N bits para determinar se você deve imprimir o número ou não. No entanto, se você alterar a maneira como o conjunto é implementado, poderá imprimir os números em k iterações. Isso é feito colocando os números em um object para serem armazenados em um conjunto de hash e em uma lista duplamente vinculada. Quando você remove um object do conjunto de hash, também o remove da lista. As respostas serão deixadas na lista que é agora de comprimento k.

Aqui está uma solução que usa k bits de armazenamento extra, sem truques inteligentes e simples. Tempo de execução O (n), espaço extra O (k). Apenas para provar que isso pode ser resolvido sem antes ler a solução ou ser um gênio:

 void puzzle (int* data, int n, bool* extra, int k) { // data contains n distinct numbers from 1 to n + k, extra provides // space for k extra bits. // Rearrange the array so there are (even) even numbers at the start // and (odd) odd numbers at the end. int even = 0, odd = 0; while (even + odd < n) { if (data [even] % 2 == 0) ++even; else if (data [n - 1 - odd] % 2 == 1) ++odd; else { int tmp = data [even]; data [even] = data [n - 1 - odd]; data [n - 1 - odd] = tmp; ++even; ++odd; } } // Erase the lowest bits of all numbers and set the extra bits to 0. for (int i = even; i < n; ++i) data [i] -= 1; for (int i = 0; i < k; ++i) extra [i] = false; // Set a bit for every number that is present for (int i = 0; i < n; ++i) { int tmp = data [i]; tmp -= (tmp % 2); if (i >= odd) ++tmp; if (tmp <= n) data [tmp - 1] += 1; else extra [tmp - n - 1] = true; } // Print out the missing ones for (int i = 1; i <= n; ++i) if (data [i - 1] % 2 == 0) printf ("Number %d is missing\n", i); for (int i = n + 1; i <= n + k; ++i) if (! extra [i - n - 1]) printf ("Number %d is missing\n", i); // Restore the lowest bits again. for (int i = even; i < n; ++i) data [i] += 1; } 

Para resolver a questão dos números faltantes 2 (e 3), você pode modificar a quickselect , que em média é executada em O(n) e usa memory constante se o particionamento for feito no local.

  1. Particione o conjunto em relação a um pivot random p nas partições l , que contêm números menores que o pivô, e r , que contêm números maiores que o pivô.

  2. Determine em quais partições os 2 números perdidos estão comparando o valor de pivot ao tamanho de cada partição ( p - 1 - count(l) = count of missing numbers in l n - count(r) - p = count of missing numbers in r )

  3. a) Se cada partição estiver faltando um número, use a abordagem da diferença de sums para localizar cada número ausente.

    (1 + 2 + ... + (p-1)) - sum(l) = missing #1 e ((p+1) + (p+2) ... + n) - sum(r) = missing #2

    b) Se uma partição estiver faltando ambos os números e a partição estiver vazia, então os números que faltam são (p-1,p-2) ou (p+1,p+2) dependendo de qual partição está faltando os números.

    Se uma partição estiver faltando 2 números, mas não estiver vazia, então recorra a essa partição.

Com apenas dois números em falta, esse algoritmo sempre descarta pelo menos uma partição, de modo que retém a complexidade de tempo médio da seleção rápida. Da mesma forma, com 3 números em falta, este algoritmo também descarta pelo menos uma partição com cada passagem (porque, como acontece com dois números ausentes, no máximo apenas uma partição conterá vários números ausentes). No entanto, não tenho certeza de quanto o desempenho diminui quando mais números ausentes são adicionados.

Aqui está uma implementação que não usa particionamento no local, portanto, este exemplo não atende ao requisito de espaço, mas ilustra as etapas do algoritmo:

  

Demonstração

Você pode verificar se todos os números existem? Se sim, você pode tentar isto:

S = sum de todos os números na bolsa (S <5050)
Z = sum dos números faltantes 5050 – S

se os números que faltam são x e y então:

x = Z – y e
max (x) = Z – 1

Então você verifica o intervalo de 1 a max(x) e encontra o número

Você pode resolver o Q2 se tiver a sum das duas listas e o produto de ambas as listas.

(l1 é o original, l2 é a lista modificada)

 d = sum(l1) - sum(l2) m = mul(l1) / mul(l2) 

Podemos otimizar isso já que a sum de uma série aritmética é n vezes a média do primeiro e último termos:

 n = len(l1) d = (n/2)*(n+1) - sum(l2) 

Agora sabemos que (se aeb são os números removidos):

 a + b = d a * b = m 

Então podemos reorganizar para:

 a = s - b b * (s - b) = m 

E multiplique:

 -b^2 + s*b = m 

E reorganize de modo que o lado direito seja zero:

 -b^2 + s*b - m = 0 

Então podemos resolver com a fórmula quadrática:

 b = (-s + sqrt(s^2 - (4*-1*-m)))/-2 a = s - b 

Exemplo de código do Python 3:

 from functools import reduce import operator import math x = list(range(1,21)) sx = (len(x)/2)*(len(x)+1) x.remove(15) x.remove(5) mul = lambda l: reduce(operator.mul,l) s = sx - sum(x) m = mul(range(1,21)) / mul(x) b = (-s + math.sqrt(s**2 - (-4*(-m))))/-2 a = s - b print(a,b) #15,5 

I do not know the complexity of the sqrt, reduce and sum functions so I cannot work out the complexity of this solution (if anyone does know please comment below.)

May be this algorithm can work for question 1:

  1. Precompute xor of first 100 integers(val=1^2^3^4….100)
  2. xor the elements as they keep coming from input stream ( val1=val1^next_input)
  3. final answer=val^val1

Ou melhor ainda:

 def GetValue(A) for i=1 to 100 do val=val^i done for value in A: do val=val^value done return val 

This algorithm can in fact be expanded for two missing numbers. The first step remains the same. When we call GetValue with two missing numbers the result will be a a1^a2 are the two missing numbers. Lets say

val = a1^a2

Now to sieve out a1 and a2 from val we take any set bit in val. Lets say the ith bit is set in val. That means that a1 and a2 have different parity at ith bit position. Now we do another iteration on the original array and keep two xor values. One for the numbers which have the ith bit set and other which doesn’t have the ith bit set. We now have two buckets of numbers, and its guranteed that a1 and a2 will lie in different buckets. Now repeat the same what we did for finding one missing element on each of the bucket.

I think this can be done without any complex mathematical equations and theories. Below is a proposal for an in place and O(2n) time complexity solution:

Input form assumptions :

# of numbers in bag = n

# of missing numbers = k

The numbers in the bag are represented by an array of length n

Length of input array for the algo = n

Missing entries in the array (numbers taken out of the bag) are replaced by the value of the first element in the array.

Por exemplo. Initially bag looks like [2,9,3,7,8,6,4,5,1,10]. If 4 is taken out, value of 4 will become 2 (the first element of the array). Therefore after taking 4 out the bag will look like [2,9,3,7,8,6,2,5,1,10]

The key to this solution is to tag the INDEX of a visited number by negating the value at that INDEX as the array is traversed.

  IEnumerable GetMissingNumbers(int[] arrayOfNumbers) { List missingNumbers = new List(); int arrayLength = arrayOfNumbers.Length; //First Pass for (int i = 0; i < arrayLength; i++) { int index = Math.Abs(arrayOfNumbers[i]) - 1; if (index > -1) { arrayOfNumbers[index] = Math.Abs(arrayOfNumbers[index]) * -1; //Marking the visited indexes } } //Second Pass to get missing numbers for (int i = 0; i < arrayLength; i++) { //If this index is unvisited, means this is a missing number if (arrayOfNumbers[i] > 0) { missingNumbers.Add(i + 1); } } return missingNumbers; } 

For Q2 this is a solution that is a bit more inefficient than the others, but still has O(N) runtime and takes O(k) space.

The idea is to run the original algorithm two times. In the first one you get a total number which is missing, which gives you an upper bound of the missing numbers. Let’s call this number N . You know that the missing two numbers are going to sum up to N , so the first number can only be in the interval [1, floor((N-1)/2)] while the second is going to be in [floor(N/2)+1,N-1] .

Thus you loop on all numbers once again, discarding all numbers that are not included in the first interval. The ones that are, you keep track of their sum. Finally, you’ll know one of the missing two numbers, and by extension the second.

I have a feeling that this method could be generalized and maybe multiple searches run in “parallel” during a single pass over the input, but I haven’t yet figured out how.

Very nice problem. I’d go for using a set difference for Qk. A lot of programming languages even have support for it, like in Ruby:

 missing = (1..100).to_a - bag 

It’s probably not the most efficient solution but it’s one I would use in real life if I was faced with such a task in this case (known boundaries, low boundaries). If the set of number would be very large then I would consider a more efficient algorithm, of course, but until then the simple solution would be enough for me.

I’d take a different approach to that question and probe the interviewer for more details about the larger problem he’s trying to solve. Depending on the problem and the requirements surrounding it, the obvious set-based solution might be the right thing and the generate-a-list-and-pick-through-it-afterward approach might not.

For example, it might be that the interviewer is going to dispatch n messages and needs to know the k that didn’t result in a reply and needs to know it in as little wall clock time as possible after the nk th reply arrives. Let’s also say that the message channel’s nature is such that even running at full bore, there’s enough time to do some processing between messages without having any impact on how long it takes to produce the end result after the last reply arrives. That time can be put to use inserting some identifying facet of each sent message into a set and deleting it as each corresponding reply arrives. Once the last reply has arrived, the only thing to be done is to remove its identifier from the set, which in typical implementations takes O(log k+1) . After that, the set contains the list of k missing elements and there’s no additional processing to be done.

This certainly isn’t the fastest approach for batch processing pre-generated bags of numbers because the whole thing runs O((log 1 + log 2 + ... + log n) + (log n + log n-1 + ... + log k)) . But it does work for any value of k (even if it’s not known ahead of time) and in the example above it was applied in a way that minimizes the most critical interval.

You can motivate the solution by thinking about it in terms of symmetries (groups, in math language). No matter the order of the set of numbers, the answer should be the same. If you’re going to use k functions to help determine the missing elements, you should be thinking about what functions have that property: symmetric. The function s_1(x) = x_1 + x_2 + ... + x_n is an example of a symmetric function, but there are others of higher degree. In particular, consider the elementary symmetric functions . The elementary symmetric function of degree 2 is s_2(x) = x_1 x_2 + x_1 x_3 + ... + x_1 x_n + x_2 x_3 + ... + x_(n-1) x_n , the sum of all products of two elements. Similarly for the elementary symmetric functions of degree 3 and higher. They are obviously symmetric. Furthermore, it turns out they are the building blocks for all symmetric functions.

You can build the elementary symmetric functions as you go by noting that s_2(x,x_(n+1)) = s_2(x) + s_1(x)(x_(n+1)) . Further thought should convince you that s_3(x,x_(n+1)) = s_3(x) + s_2(x)(x_(n+1)) and so on, so they can be computed in one pass.

How do we tell which items were missing from the array? Think about the polynomial (z-x_1)(z-x_2)...(z-x_n) . It evaluates to 0 if you put in any of the numbers x_i . Expanding the polynomial, you get z^n-s_1(x)z^(n-1)+ ... + (-1)^n s_n . The elementary symmetric functions appear here too, which is really no surprise, since the polynomial should stay the same if we apply any permutation to the roots.

So we can build the polynomial and try to factor it to figure out which numbers are not in the set, as others have mentioned.

Finally, if we are concerned about overflowing memory with large numbers (the nth symmetric polynomial will be of the order 100! ), we can do these calculations mod p where p is a prime bigger than 100. In that case we evaluate the polynomial mod p and find that it again evaluates to 0 when the input is a number in the set, and it evaluates to a non-zero value when the input is a number not in the set. However, as others have pointed out, to get the values out of the polynomial in time that depends on k , not N , we have to factor the polynomial mod p .

You’d probably need clarification on what O(k) means.

Here’s a trivial solution for arbitrary k: for each v in your set of numbers, accumulate the sum of 2^v. At the end, loop i from 1 to N. If sum modulo 2^i is zero, then i is missing.

Easy, right? O(N) time, O(1) storage, and it supports arbitrary k.

Except that you’re computing enormous numbers that on a real computer would each require O(N) space. In fact, this solution is identical to a bit vector.

So you could be clever and compute the sum and the sum of squares and the sum of cubes… up to the sum of v^k, and do the fancy math to extract the result. But those are big numbers too, which begs the question: what abstract model of operation are we talking about? How much fits in O(1) space, and how long does it take to sum up numbers of whatever size you need?

There is a general way to generalize streaming algorithms like this. The idea is to use a bit of randomization to hopefully ‘spread’ the k elements into independent sub problems, where our original algorithm solves the problem for us. This technique is used in sparse signal reconstruction, among other things.

  • Make an array, a , of size u = k^2 .
  • Pick any universal hash function , h : {1,...,n} -> {1,...,u} . (Like multiply-shift )
  • For each i in 1, ..., n increase a[h(i)] += i
  • For each number x in the input stream, decrement a[h(x)] -= x .

If all of the missing numbers have been hashed to different buckets, the non-zero elements of the array will now contain the missing numbers.

The probability that a particular pair is sent to the same bucket, is less than 1/u by definition of a universal hash function. Since there are about k^2/2 pairs, we have that the error probability is at most k^2/2/u=1/2 . That is, we succeed with probability at least 50%, and if we increase u we increase our chances.

Notice that this algorithm takes k^2 logn bits of space (We need logn bits per array bucket.) This matches the space required by @Dimitris Andreou’s answer (In particular the space requirement of polynomial factorization, which happens to also be randomized.) This algorithm also has constant time per update, rather than time k in the case of power-sums.

In fact, we can be even more efficient than the power sum method by using the trick described in the comments.

You could try using a Bloom Filter . Insert each number in the bag into the bloom, then iterate over the complete 1-k set until reporting each one not found. This may not find the answer in all scenarios, but might be a good enough solution.

I believe I have a O(k) time and O(log(k)) space algorithm, given that you have the floor(x) and log2(x) functions for arbitrarily big integers available:

You have an k -bit long integer (hence the log8(k) space) where you add the x^2 , where x is the next number you find in the bag: s=1^2+2^2+... This takes O(N) time (which is not a problem for the interviewer). At the end you get j=floor(log2(s)) which is the biggest number you’re looking for. Then s=sj and you do again the above:

 for (i = 0 ; i < k ; i++) { j = floor(log2(s)); missing[i] = j; s -= j; } 

Now, you usually don't have floor and log2 functions for 2756 -bit integers but instead for doubles. Assim? Simply, for each 2 bytes (or 1, or 3, or 4) you can use these functions to get the desired numbers, but this adds an O(N) factor to time complexity

This might sound stupid, but, in the first problem presented to you, you would have to see all the remaining numbers in the bag to actually add them up to find the missing number using that equation.

So, since you get to see all the numbers, just look for the number that’s missing. The same goes for when two numbers are missing. Pretty simple I think. No point in using an equation when you get to see the numbers remaining in the bag.

I think this can be generalized like this:

Denote S, M as the initial values for the sum of arithmetic series and multiplication.

 S = 1 + 2 + 3 + 4 + ... n=(n+1)*n/2 M = 1 * 2 * 3 * 4 * .... * n 

I should think about a formula to calculate this, but that is not the point. Anyway, if one number is missing, you already provided the solution. However, if two numbers are missing then, let’s denote the new sum and total multiple by S1 and M1, which will be as follows:

 S1 = S - (a + b)....................(1) Where a and b are the missing numbers. M1 = M - (a * b)....................(2) 

Since you know S1, M1, M and S, the above equation is solvable to find a and b, the missing numbers.

Now for the three numbers missing:

 S2 = S - ( a + b + c)....................(1) Where a and b are the missing numbers. M2 = M - (a * b * c)....................(2) 

Now your unknown is 3 while you just have two equations you can solve from.

I don’t know whether this is efficient or not but I would like to suggest this solution.

  1. Compute xor of the 100 elements
  2. Compute xor of the 98 elements (after the 2 elements are removed)
  3. Now (result of 1) XOR (result of 2) gives you the xor of the two missing nos i..ea XOR b if a and b are the missing elements
    4.Get the sum of the missing Nos with your usual approach of the sum formula diff and lets say the diff is d.

Now run a loop to get the possible pairs (p,q) both of which lies in [1 , 100] and sum to d.

When a pair is obtained check whether (result of 3) XOR p = q and if yes we are done.

Please correct me if I am wrong and also comment on time complexity if this is correct

I have an idea, but this is assuming that the actual size of the array is 100 and the missing numbers are replaced with something else (like -1).

Basically, do a sort that’s kind of a modified version of a selection sort that swaps the list in-place. I believe this is O(n) time (correct me if I’m wrong though) because we make use of the fact we already know the numbers that should exist. We swap the value with the “correct” position, until the index we are at has the correct number (or has -1).

After we’re done with that, we just loop the list again and the index will basically be the missing numbers

 #Set up the input input = (1..100).to_a.shuffle input[rand(0..99)] = -1 input[rand(0..99)] = -1 def f(a) for i in 0..99 while (a[i] != i+1) && a[i] > 0 v1 = a[i] v2 = a[v1 - 1] a[i] = v2 a[v1 - 1] = v1 end end result = [] a.each_with_index do |value, index| if value < 0 result.push(index + 1) end end return result end #Returns the 2 missing numbers puts f(input) 

We can do the Q1 and Q2 in O(log n) most of the time.

Suppose our memory chip consists of array of n number of test tubes . And a number x in the the test tube is represented by x milliliter of chemical-liquid.

Suppose our processor is a laser light . When we light up the laser it traverses all the tubes perpendicularly to it’s length. Every-time it passes through the chemical liquid, the luminosity is reduced by 1 . And passing the light at certain milliliter mark is an operation of O(1) .

Now if we light our laser at the middle of the test-tube and get the output of luminosity

  • equals to a pre-calculated value(calculated when no numbers were missing), then the missing numbers are greater than n/2 .
  • If our output is smaller, then there is at least one missing number that is smaller than n/2 . We can also check if the luminosity is reduced by 1 or 2 . if it is reduced by 1 then one missing number is smaller than n/2 and other is bigger than n/2 . If it is reduced by 2 then both numbers are smaller than n/2 .

We can repeat the above process again and again narrowing down our problem domain. In each step, we make the domain smaller by half. And finally we can get to our result.

Parallel algorithms that are worth mentioning(because they are interesting),

  • sorting by some parallel algorithm, for example, parallel merge can be done in O(log^3 n) time. And then the missing number can be found by binary search in O(log n) time.
  • Theoretically, if we have n processors then each process can check one of the inputs and set some flag that identifies the number(conveniently in an array). And in the next step each process can check each flag and finally output the number that is not flagged. The whole process will take O(1) time. It has additional O(n) space/memory requirement.

Note, that the two parallel algorithms provided above may need additional space as mentioned in the comment .

Yet another way is using residual graph filtering.

Suppose we have numbers 1 to 4 and 3 is missing. The binary representation is the following,

1 = 001b, 2 = 010b, 3 = 011b, 4 = 100b

And I can create a flow-graph like the following.

  1 1 -------------> 1 | | 2 | 1 | 0 ---------> 1 ----------> 0 | | | | | 1 1 | | 0 ---------> 0 ----------> 0 | | | 1 | 1 | 1 ---------> 0 -------------> 1 

Note that the flow graph contains x nodes, while x being the number of bits. And the maximum number of edges are (2*x)-2 .

So for 32 bit integer it will take O(32) space or O(1) space.

Now if I remove capacity for each number starting from 1,2,4 then I am left with a residual graph.

 0 ----------> 1 ---------> 1 

Finally I shall run a loop like the following,

  result = [] for x in range(1,n): exists_path_in_residual_graph(x) result.append(x) 

Now the result is in result contains numbers that are not missing as well(false positive). But the k <= (size of the result) <= n when there are k missing elements.

I shall go through the given list one last time to mark the result missing or not.

So the time complexity will be O(n) .

Finally, it is possible to reduce the number of false positive(and the space required) by taking nodes 00 , 01 , 11 , 10 instead of just 0 and 1 .

Try to find the product of numbers from 1 to 50:

Let product, P1 = 1 x 2 x 3 x …………. 50

When you take out numbers one by one, multiply them so that you get the product P2. But two numbers are missing here, hence P2 < P1.

The product of the two mising terms, axb = P1 – P2.

You already know the sum, a + b = S1.

From the above two equations, solve for a and b through a quadratic equation. a and b are your missing numbers.