algorithm - preguntas - en un examen se da 20 puntos por respuesta correcta

La pregunta de la entrevista fácil se hizo más difícil: números dados 1..100, encuentre el número(s) que falta (30)

Tuve una interesante experiencia de entrevista de trabajo hace un tiempo. La pregunta comenzó muy fácil:

P1 : Tenemos una bolsa que contiene los números 1 , 2 , 3 , ..., 100 . Cada número aparece exactamente una vez, por lo que hay 100 números. Ahora se saca aleatoriamente un número de la bolsa. Encuentre el número perdido.

He escuchado esta pregunta de la entrevista antes, por supuesto, así que respondí muy rápidamente de la siguiente manera:

A1 : Bueno, la suma de los números 1 + 2 + 3 + … + N es (N+1)(N/2) (ver Wikipedia: suma de series aritméticas ). Para N = 100 , la suma es 5050 .
Por lo tanto, si todos los números están presentes en la bolsa, la suma será exactamente 5050 . Como falta un número, la suma será menor que esto, y la diferencia es ese número. Entonces podemos encontrar ese número faltante en el tiempo O(N) y en el espacio O(1) .

En este punto pensé que lo había hecho bien, pero de repente la pregunta dio un giro inesperado:

P2 : Eso es correcto, pero ahora, ¿cómo haría esto si faltan DOS números?

Nunca había visto / escuchado / considerado esta variación antes, por lo que entré en pánico y no pude responder la pregunta. El entrevistador insistió en conocer mi proceso de pensamiento, por lo que mencioné que tal vez podamos obtener más información comparando con el producto esperado, o tal vez hacer una segunda pasada después de haber recopilado información de la primera pasada, etc., pero realmente estaba disparando en la oscuridad, en lugar de tener un camino claro hacia la solución.

El entrevistador intentó animarme diciendo que tener una segunda ecuación es, de hecho, una forma de resolver el problema. En este punto estaba un poco molesto (por no saber la respuesta de antemano), y me preguntaron si esta es una técnica de programación general (lea: "útil"), o si es solo una respuesta truco / gotcha.

La respuesta del entrevistador me sorprendió: puede generalizar la técnica para encontrar 3 números faltantes. De hecho, puedes generalizarlo para encontrar k números faltantes.

Qk : Si faltan exactamente k números de la bolsa, ¿cómo lo encontraría de manera eficiente?

Esto fue hace unos meses, y todavía no podía entender qué es esta técnica. Obviamente hay un límite inferior de Ω(N) ya que debemos escanear todos los números al menos una vez, pero el entrevistador insistió en que la complejidad de TIEMPO y ESPACIO de la técnica de resolución (menos la exploración de entrada de tiempo O(N) ) se define en k no n .

Así que la pregunta aquí es simple:

¿Cómo resolverías Q2 ?
¿Cómo resolverías Q3 ?
¿Cómo resolverías Qk ?

Aclaraciones

En general, hay N números de 1 .. N , no solo 1..100.
No estoy buscando la solución obvia basada en conjuntos, por ejemplo, utilizando un conjunto de bits , codificando la presencia / ausencia de cada número por el valor de un bit designado, por lo tanto, utilizando bits O(N) en el espacio adicional. No podemos permitirnos ningún espacio adicional proporcional a N.
Tampoco estoy buscando el primer enfoque obvio. Vale la pena mencionar este y el enfoque basado en conjuntos en una entrevista (son fáciles de implementar y, dependiendo de N , puede ser muy práctico). Estoy buscando la solución del Santo Grial (que puede o no ser práctica de implementar, pero tiene las características asintóticas deseadas).

Entonces, nuevamente, debe escanear la entrada en O(N) , pero solo puede capturar una pequeña cantidad de información (definida en términos de k no N ), y luego debe encontrar los k números faltantes de alguna manera.

¿Puedes comprobar si existe cada número? Si es así, puedes probar esto:

S = suma de todos los números en la bolsa (S <5050)
Z = suma de los números faltantes 5050 - S

Si los números que faltan son xy yluego:

x = Z - y y
max (x) = Z - 1

Así que verifica el rango de 1a max(x)y encuentra el número

Aquí hay un resumen del link de Dimitris Andreou .

Recuerda la suma de i-th potencias, donde i = 1,2, .., k. Esto reduce el problema para resolver el sistema de ecuaciones.

a ₁ + a ₂ + ... + a _k = b ₁

a ₁ ² + a ₂ ² + ... + a _k ² = b ₂

...

a ₁ ^k + a ₂ ^k + ... + a _k ^k = b _k

Usando las identidades de Newton , sabiendo que b _i permite computar

c ₁ = a ₁ + a ₂ + ... a _k

c ₂ = a ₁ a ₂ + a ₁ a ₃ + ... + a _k-1 a _k

...

c _k = a ₁ a ₂ ... a _k

Si expande el polinomio (xa ₁ ) ... (xa _k ) los coeficientes serán exactamente c ₁ , ..., c _k - consulte las fórmulas de Viète . Dado que todos los factores polinomiales son únicos (el anillo de polinomios es un dominio euclidiano ), esto significa que a _i están determinados de forma única, hasta la permutación.

Esto termina una prueba de que recordar los poderes es suficiente para recuperar los números. Para k constante, este es un buen enfoque.

Sin embargo, cuando k es variable, el enfoque directo de computar c ₁ , ..., c _k es prohibitivamente caro, ya que, por ejemplo, c _k es el producto de todos los números faltantes, ¡magnitud n! / (Nk) !. Para superar esto, realice cálculos en el campo Z _q , donde q es un primo tal que n <= q <2n - existe por el postulado de Bertrand . No es necesario cambiar la prueba, ya que las fórmulas aún se mantienen y la factorización de los polinomios sigue siendo única. También necesita un algoritmo para la factorización en campos finitos, por ejemplo el de Berlekamp o Cantor-Zassenhaus .

Pseudocódigo de alto nivel para la constante k:

Calcular i-th potencias de números dados
Resta para obtener sumas de i-th potencias de números desconocidos. Llama las sumas b _i .
Usa las identidades de Newton para calcular los coeficientes de b _i ; llamalos c _i . Básicamente, c ₁ = b ₁ ; c ₂ = (c ₁ b ₁ - b ₂ ) / 2; ver Wikipedia para las fórmulas exactas
Factoriza el polinomio x ^k -c ₁ x ^k-1 + ... + c _k .
Las raíces del polinomio son los números necesarios a ₁ , ..., a _k .

Para variar k, encuentre una prima n <= q <2n utilizando, por ejemplo, Miller-Rabin, y realice los pasos con todos los números reducidos en módulo q.

Como comentó Heinrich Apfelmus, en lugar de un primo q puede usar q = 2 ^{⌈log n⌉} y realizar aritmética en un campo finito .

Aquí hay una solución que utiliza k bits de almacenamiento adicional, sin trucos inteligentes y sencillamente. Tiempo de ejecución O (n), espacio extra O (k). Solo para demostrar que esto se puede resolver sin tener que leer primero la solución o ser un genio:

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; }

Como @j_random_hacker señaló, esto es bastante similar a encontrar duplicados en el tiempo O (n) y en el espacio O (1) , y aquí también funciona una adaptación de mi respuesta.

Suponiendo que la "bolsa" está representada por una matriz basada en 1 A[] de tamaño N - k , podemos resolver Qk en tiempo O(N) y espacio adicional O(k) .

Primero, extendemos nuestra matriz A[] por k elementos, de modo que ahora sea de tamaño N Este es el espacio adicional O(k) . Luego ejecutamos el siguiente algoritmo de pseudo-có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

El primer bucle inicializa las k entradas adicionales al mismo que la primera entrada en la matriz (esto es solo un valor conveniente que sabemos que ya está presente en la matriz; después de este paso, cualquier entrada que faltaba en la matriz de tamaño inicial Nk todavía faltan en la matriz extendida).

El segundo bucle permuta la matriz extendida de modo que si el elemento x está presente al menos una vez, entonces una de esas entradas estará en la posición A[x] .

Tenga en cuenta que aunque tiene un bucle anidado, aún se ejecuta en tiempo O(N) : solo se produce un intercambio si hay un i tal que A[i] != i , y cada intercambio establece al menos un elemento tal que A[i] == i , donde eso no era cierto antes. Esto significa que el número total de swaps (y, por lo tanto, el número total de ejecuciones del cuerpo del bucle while) es a lo sumo N-1 .

El tercer bucle imprime los índices de la matriz i que no están ocupados por el valor i ; esto significa que debo haber faltado.

El problema con las soluciones basadas en sumas de números es que no tienen en cuenta el costo de almacenar y trabajar con números con grandes exponentes ... en la práctica, para que funcione para n muy grande, se usaría una biblioteca de números grandes . Podemos analizar la utilización del espacio para estos algoritmos.

Podemos analizar la complejidad de tiempo y espacio de los algoritmos de sdcvvc y Dimitris Andreou.

Almacenamiento:

l_j = ceil (log_2 (sum_{i=1}^n i^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}^n i)^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)`

Así que l_j /in /Theta(j log n)

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

Espacio utilizado: asumiendo que la computación a^j toma tiempo ceil(log_2 j) , tiempo 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^n i^i) + 1 t < kn log_2 (n) + 1 /in O(kn log n)

Tiempo total utilizado: /Theta(kn log n)

Si este tiempo y espacio son satisfactorios, puede usar un algoritmo recursivo simple. Sea b! I la entrada número i en la bolsa, n el número de números antes de las eliminaciones y k el número de eliminaciones. En la sintaxis 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..(n-k)] 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

Almacenamiento utilizado: O(k) para la lista, O(log(n)) para la pila: O(k + log(n)) Este algoritmo es más intuitivo, tiene la misma complejidad de tiempo y usa menos espacio.

Espera un minuto. Como se indica la pregunta, hay 100 números en la bolsa. No importa qué tan grande sea k, el problema puede resolverse en un tiempo constante porque puede usar un conjunto y eliminar números del conjunto en un máximo de 100 k iteraciones de un bucle. 100 es constante. El conjunto de números restantes es tu respuesta.

Si generalizamos la solución a los números del 1 al N, nada cambia excepto que N no es una constante, por lo que estamos en O (N - k) = O (N) tiempo. Por ejemplo, si usamos un conjunto de bits, establecemos los bits en 1 en tiempo O (N), iteramos a través de los números, establecemos los bits en 0 a medida que avanzamos (O (Nk) = O (N)) y luego tener la respuesta

Me parece que el entrevistador le estaba preguntando cómo imprimir los contenidos del conjunto final en tiempo O (k) en lugar de tiempo O (N). Claramente, con un bit establecido, debe iterar a través de todos los N bits para determinar si debe imprimir el número o no. Sin embargo, si cambia la forma en que se implementa el conjunto, puede imprimir los números en k iteraciones. Esto se hace colocando los números en un objeto para que se almacene en un conjunto hash y en una lista doblemente enlazada. Cuando elimina un objeto del conjunto hash, también lo elimina de la lista. Las respuestas se dejarán en la lista que ahora es de longitud k.

Le pedí a un niño de 4 años que resolviera este problema. Ordenó los números y luego siguió adelante. Esto tiene un requisito de espacio de O (piso de la cocina), y funciona igual de fácil, aunque faltan muchas bolas.

Lo encontrará leyendo el par de páginas de link . Muestra exactamente la generalización que estás buscando . Probablemente esto es lo que leyó su entrevistador y por qué hizo estas preguntas.

Ahora, si solo las personas pudieran comenzar a eliminar las respuestas que están subsumidas o reemplazadas por el tratamiento de Muthukrishnan, y hacer que este texto sea más fácil de encontrar. :)

También vea sdcvvc''s respuesta directamente relacionada con sdcvvc''s , que también incluye pseudocódigo (¡hurra! No hay necesidad de leer esas fórmulas matemáticas complicadas :)) (gracias, ¡excelente trabajo!).

No estoy seguro, si es la solución más eficiente, pero repasaría todas las entradas y utilizaría un conjunto de bits para recordar, qué números se establecen, y luego probar para 0 bits.

Me gustan las soluciones simples, e incluso creo que podría ser más rápido que calcular la suma, o la suma de cuadrados, etc.

No he revisado las matemáticas, pero sospecho que el cálculo de Σ(n^2) en el mismo paso que calculamos Σ(n) proporcionaría suficiente información para obtener dos números faltantes, Do Σ(n^3) también si hay tres, y así sucesivamente.

Para resolver la pregunta de 2 (y 3) números faltantes, puede modificar la quickselect , que en promedio se ejecuta en O(n) y usa memoria constante si la partición se realiza en el lugar.

Particione el conjunto con respecto a un pivote aleatorio p en las particiones l , que contienen números más pequeños que el pivote, r , que contienen números mayores que el pivote.
Determine en qué particiones están los 2 números faltantes comparando el valor de pivote con el tamaño de cada partición ( p - 1 - count(l) = count of missing numbers in l y n - count(r) - p = count of missing numbers in r )
a) Si a cada partición le falta un número, utilice el método de la diferencia de las sumas para encontrar cada número faltante.
(1 + 2 + ... + (p-1)) - sum(l) = missing #1 y ((p+1) + (p+2) ... + n) - sum(r) = missing #2
b) Si a una partición le faltan ambos números y la partición está vacía, entonces los números faltantes son (p-1,p-2) o (p+1,p+2) dependiendo de qué partición faltan los números.
Si a una partición le faltan 2 números pero no está vacía, recurra a esa partición.

Con solo 2 números faltantes, este algoritmo siempre descarta al menos una partición, por lo que conserva la complejidad de tiempo promedio O(n) de selección rápida. De manera similar, con 3 números faltantes, este algoritmo también descarta al menos una partición con cada paso (porque al igual que con 2 números faltantes, como máximo solo 1 partición contendrá varios números faltantes). Sin embargo, no estoy seguro de cuánto disminuye el rendimiento cuando se agregan más números faltantes.

Aquí hay una implementación que no utiliza la partición en el lugar, por lo que este ejemplo no cumple con el requisito de espacio pero ilustra los pasos del algoritmo:

<?php $list = range(1,100); unset($list[3]); unset($list[31]); findMissing($list,1,100); function findMissing($list, $min, $max) { if(empty($list)) { print_r(range($min, $max)); return; } $l = $r = []; $pivot = array_pop($list); foreach($list as $number) { if($number < $pivot) { $l[] = $number; } else { $r[] = $number; } } if(count($l) == $pivot - $min - 1) { // only 1 missing number use difference of sums print array_sum(range($min, $pivot-1)) - array_sum($l) . "/n"; } else if(count($l) < $pivot - $min) { // more than 1 missing number, recurse findMissing($l, $min, $pivot-1); } if(count($r) == $max - $pivot - 1) { // only 1 missing number use difference of sums print array_sum(range($pivot + 1, $max)) - array_sum($r) . "/n"; } else if(count($r) < $max - $pivot) { // mroe than 1 missing number recurse findMissing($r, $pivot+1, $max); } }

Demo

Podemos resolver Q2 sumando tanto los números mismos como los cuadrados de los números.

Entonces podemos reducir el problema a

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

Donde y son hasta qué punto las sumas están por debajo de los valores esperados.

Sustituir nos da:

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

Que luego podemos resolver para determinar nuestros números faltantes.

Creo que esto se puede generalizar así:

Indica S, M como los valores iniciales para la suma de las series aritméticas y la multiplicación.

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

Debería pensar en una fórmula para calcular esto, pero ese no es el punto. De todos modos, si falta un número, ya proporcionó la solución. Sin embargo, si faltan dos números, denotemos la nueva suma y el múltiplo total por S1 y M1, que serán los siguientes:

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

Como sabes S1, M1, M y S, la ecuación anterior se puede resolver para encontrar a y b, los números que faltan.

Ahora para los tres números que faltan:

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

Ahora tu desconocido es 3, mientras que solo tienes dos ecuaciones de las que puedes resolver.

Esto puede parecer estúpido, pero, en el primer problema que se le presenta, tendría que ver todos los números restantes en la bolsa para sumarlos y encontrar el número que falta usando esa ecuación.

Entonces, ya que puedes ver todos los números, solo busca el número que falta. Lo mismo ocurre cuando faltan dos números. Bastante simple, creo. No tiene sentido utilizar una ecuación cuando vea los números que quedan en la bolsa.

Intenta encontrar el producto de los números del 1 al 50:

Deje que el producto, P1 = 1 x 2 x 3 x ............. 50

Cuando saque los números uno por uno, multiplíquelos para obtener el producto P2. Pero aquí faltan dos números, por lo tanto P2 <P1.

El producto de los dos términos emergentes, axb = P1 - P2.

Ya conoces la suma, a + b = S1.

De las dos ecuaciones anteriores, resuelva para a y b mediante una ecuación cuadrática. ayb son los números que faltan.

No sé si esto es eficiente o no, pero me gustaría sugerir esta solución.

Calcular xor de los 100 elementos.
Calcular xor de los 98 elementos (después de que se eliminan los 2 elementos)
Ahora (resultado de 1) XOR (resultado de 2) le da el xor de los dos números faltantes i..ea XOR b si a y b son los elementos faltantes
4. Obtenga la suma de los números faltantes con su enfoque habitual de suma la fórmula diff y digamos que la diferencia es d.

Ahora ejecute un bucle para obtener los pares posibles (p, q) que se encuentran en [1, 100] y sumen a d.

Cuando se obtiene un par, verifique si (resultado de 3) XOR p = q y si es así, hemos terminado.

Corríjame si estoy equivocado y también comente sobre la complejidad del tiempo si esto es correcto

Otra forma más es mediante el filtrado de gráficos residuales.

Supongamos que tenemos los números 1 a 4 y falta 3. La representación binaria es la siguiente,

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

Y puedo crear un diagrama de flujo como el siguiente.

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

Tenga en cuenta que el diagrama de flujo contiene x nodos, mientras que x es el número de bits. Y el número máximo de aristas es (2 * x) -2.

Por lo tanto, para un entero de 32 bits tomará espacio O (32) o espacio O (1).

Ahora, si elimino la capacidad para cada número a partir de 1,2,4, entonces me quedo con un gráfico residual.

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

Finalmente voy a ejecutar un bucle como el siguiente,

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

Ahora el resultado está en resultcontiene números que no faltan también (falso positivo). Pero k <= (tamaño del resultado) <= n cuando kfaltan elementos.

Repasaré la lista dada una última vez para marcar el resultado que falta o no.

Entonces la complejidad del tiempo será O (n).

Finalmente, es posible reducir el número de falsos positivos (y el espacio necesario) mediante la adopción de nodos 00, 01, 11, 10en lugar de sólo 0y 1.

Para Q2, esta es una solución un poco más ineficiente que las otras, pero aún tiene tiempo de ejecución O (N) y ocupa espacio O (k).

La idea es ejecutar el algoritmo original dos veces. En el primero, obtienes un número total que falta, lo que te da un límite superior de los números que faltan. Llamemos a este número N. Usted sabe que los dos números que faltan van a sumar N, por lo que el primer número solo puede estar en el intervalo [1, floor((N-1)/2)]mientras que el segundo estará en [floor(N/2)+1,N-1].

Por lo tanto, repites todos los números nuevamente, descartando todos los números que no están incluidos en el primer intervalo. Los que están, llevas un registro de su suma. Finalmente, conocerá uno de los dos números que faltan y, por extensión, el segundo.

Tengo la sensación de que este método podría generalizarse y quizás varias búsquedas se ejecutan en "paralelo" durante una sola pasada sobre la entrada, pero todavía no he descubierto cómo.

Probablemente necesitarías una aclaración sobre lo que significa O (k).

Aquí hay una solución trivial para k arbitraria: para cada v en tu conjunto de números, acumula la suma de 2 ^ v. Al final, el bucle es de 1 a N. Si la suma módulo 2 ^ i es cero, entonces falta i.

Fácil, ¿verdad? O (N) tiempo, O (1) almacenamiento, y soporta k arbitrario.

Excepto que está calculando números enormes que en una computadora real cada uno requeriría un espacio O (N). De hecho, esta solución es idéntica a un vector de bits.

Así que podrías ser inteligente y calcular la suma y la suma de los cuadrados y la suma de los cubos ... hasta la suma de v ^ k, y hacer la matemática de fantasía para extraer el resultado. Pero esos son números grandes también, lo que plantea la pregunta: ¿de qué modelo abstracto de operación estamos hablando? ¿Cuánto cabe en el espacio O (1) y cuánto tiempo se tarda en resumir los números del tamaño que necesite?

Puede ser que este algoritmo funcione para la pregunta 1:

Preciso de xor de los primeros 100 enteros (val = 1 ^ 2 ^ 3 ^ 4 .... 100)
xo los elementos a medida que siguen viniendo del flujo de entrada (val1 = val1 ^ next_input)
respuesta final = val ^ val1

O mejor:

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

Este algoritmo puede de hecho expandirse para dos números faltantes. El primer paso sigue siendo el mismo. Cuando llamemos a GetValue con dos números faltantes, el resultado será uno de a1^a2los dos números faltantes. Digamos

val = a1^a2

Ahora, para eliminar a1 y a2 de val, tomamos cualquier bit establecido en val. Digamos que el ithbit se establece en val. Eso significa que a1 y a2 tienen paridad diferente en la ithposición del bit. Ahora hacemos otra iteración en la matriz original y mantenemos dos valores xor. Uno para los números que tienen el conjunto de bits i y otro que no tiene el conjunto de bits i. Ahora tenemos dos cubos de números, y está garantizado que a1 and a2estará en diferentes cubos. Ahora repita lo mismo que hicimos para encontrar un elemento faltante en cada uno de los cubos.

Puedes resolver Q2 si tienes la suma de ambas listas y el producto de ambas listas.

(l1 es el original, l2 es la lista modificada)

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

Podemos optimizar esto ya que la suma de una serie aritmética es n veces la media del primer y último término:

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

Ahora sabemos que (si a y b son los números eliminados):

a + b = d a * b = m

Para que podamos reorganizar a:

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

Y multiplicar:

-b^2 + s*b = m

Y reordenar de modo que el lado derecho sea cero:

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

Entonces podemos resolver con la fórmula cuadrática:

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

Código de muestra de 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

No conozco la complejidad de las funciones sqrt, reduce y sum, así que no puedo calcular la complejidad de esta solución (si alguien lo sabe, comente a continuación)

Tengo una idea, pero esto supone que el tamaño real de la matriz es 100 y los números que faltan se reemplazan con otra cosa (como -1).

Básicamente, haga una clasificación que sea una especie de versión modificada de una selección que intercambie la lista en el lugar. Creo que es O (n) el tiempo (corríjame si me equivoco) porque usamos el hecho de que ya sabemos los números que deberían existir. Intercambiamos el valor con la posición "correcta", hasta que el índice en el que estamos tenga el número correcto (o tenga -1).

Una vez que hayamos terminado con eso, simplemente hacemos un bucle en la lista de nuevo y el índice será básicamente los números que faltan

#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)

Creo que esto se puede hacer sin ninguna ecuación matemática y teorías complejas. A continuación se muestra una propuesta para una solución de complejidad de tiempo in situ y O (2n):

Asumir los supuestos del formulario:

# de números en la bolsa = n

# de números faltantes = k

Los números en la bolsa están representados por una matriz de longitud n

Longitud de la matriz de entrada para el algo = n

Las entradas que faltan en la matriz (números extraídos de la bolsa) se reemplazan por el valor del primer elemento de la matriz.

P.ej.Inicialmente, la bolsa se parece a [2,9,3,7,8,6,4,5,1,10]. Si se saca 4, el valor de 4 se convertirá en 2 (el primer elemento de la matriz). Por lo tanto, después de sacar 4 de la bolsa se verá como [2,9,3,7,8,6,2,5,1,10]

La clave de esta solución es etiquetar el ÍNDICE de un número visitado negando el valor en ese ÍNDICE cuando se recorre la matriz.

IEnumerable<int> GetMissingNumbers(int[] arrayOfNumbers) { List<int> missingNumbers = new List<int>(); 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; }

Creo que tengo un algoritmo de O(k)tiempo y O(log(k))espacio, dado que tienes disponibles las funciones floor(x)y log2(x)para enteros arbitrariamente grandes:

Tiene un kentero de un bit largo (de ahí el log8(k)espacio) donde agrega x^2, donde x es el siguiente número que encuentra en la bolsa: s=1^2+2^2+...esto lleva O(N)tiempo (lo cual no es un problema para el entrevistador). Al final, obtienes j=floor(log2(s))cuál es el número más grande que estás buscando. Entonces s=sjy vuelve a hacer lo anterior:

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

Ahora, por lo general, no tiene funciones de piso y log2 para 2756enteros de -bit, sino para los dobles. ¿Asi que? Simplemente, por cada 2 bytes (o 1, o 3, o 4) puede usar estas funciones para obtener los números deseados, pero esto agrega un O(N)factor a la complejidad del tiempo

Hay una forma general de generalizar algoritmos de transmisión como esta. La idea es usar un poco de aleatorización para "difundir" los kelementos en sub problemas independientes, donde nuestro algoritmo original resuelve el problema por nosotros. Esta técnica se utiliza en la reconstrucción de señales dispersas, entre otras cosas.

Hacer una matriz a, de tamaño u = k^2.
Escoja cualquier función hash universales , h : {1,...,n} -> {1,...,u}. (Como multiply-shift )
Para cada uno ien 1, ..., naumentoa[h(i)] += i
Para cada número xen el flujo de entrada, disminuya a[h(x)] -= x.

Si todos los números faltantes se han agrupado en diferentes cubos, los elementos distintos de cero de la matriz ahora contendrán los números faltantes.

La probabilidad de que un par en particular se envíe al mismo grupo es menor que 1/upor definición de una función hash universal. Como hay k^2/2pares, tenemos que la probabilidad de error es como máximo k^2/2/u=1/2. Es decir, tenemos éxito con una probabilidad de al menos el 50%, y si uaumentamos aumentamos nuestras posibilidades.

Observe que este algoritmo toma k^2 lognbits de espacio (Necesitamos lognbits por conjunto de matrices). Esto coincide con el espacio requerido por la respuesta de @Dimitris Andreou (En particular, el requisito de espacio de la factorización polinomial, que también es aleatorio). Este algoritmo también tiene una constante tiempo por actualización, en lugar de tiempo ken el caso de sumas de poder.

De hecho, podemos ser incluso más eficientes que el método de la suma de potencia utilizando el truco descrito en los comentarios.

Muy buen problema. Me gustaría usar una diferencia establecida para Qk. Muchos lenguajes de programación incluso tienen soporte para eso, como en Ruby:

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

Probablemente no sea la solución más eficiente, pero es una que usaría en la vida real si me enfrentara con una tarea en este caso (límites conocidos, límites bajos). Si el conjunto de números fuera muy grande, entonces consideraría un algoritmo más eficiente, por supuesto, pero hasta entonces la solución simple sería suficiente para mí.

Podemos hacer el Q1 y el Q2 en O (log n) la mayor parte del tiempo.

Supongamos que nuestra memory chipconsiste en una serie de nnúmeros de test tubes. Y un número xen el tubo de ensayo está representado por x milliliterquímico-líquido.

Supongamos que nuestro procesador es un laser light. Cuando encendemos el láser, atraviesa todos los tubos de forma perpendicular a su longitud. Cada vez que pasa a través del líquido químico, la luminosidad se reduce 1. Y pasar la luz a cierta marca de mililitros es una operación de O(1).

Ahora si encendemos nuestro láser en el centro del tubo de ensayo y obtenemos la salida de luminosidad

es igual a un valor precalculado (calculado cuando no faltaban números), entonces los números que faltan son mayores que n/2.
Si nuestra salida es más pequeña, entonces hay al menos un número faltante que es menor que n/2. También podemos comprobar si la luminosidad se reduce en 1o 2. si se reduce para 1entonces, un número faltante es más pequeño que n/2y otro es más grande que n/2. Si se reduce por 2entonces ambos números son más pequeños que n/2.

Podemos repetir el proceso anterior una y otra vez reduciendo nuestro dominio de problemas. En cada paso, hacemos el dominio más pequeño por la mitad. Y finalmente podemos llegar a nuestro resultado.

Los algoritmos paralelos que vale la pena mencionar (porque son interesantes),

la clasificación por algún algoritmo paralelo, por ejemplo, la fusión paralela se puede hacer a O(log^3 n)tiempo. Y luego el número que falta se puede encontrar por búsqueda binaria en el O(log n)tiempo.
Teóricamente, si tenemos nprocesadores, cada proceso puede verificar una de las entradas y establecer algún indicador que identifique el número (convenientemente en una matriz). Y en el siguiente paso, cada proceso puede verificar cada marca y finalmente dar salida al número que no está marcado. Todo el proceso llevará O(1)tiempo. Tiene un O(n)requisito de espacio / memoria adicional .

Tenga en cuenta que los dos algoritmos paralelos proporcionados anteriormente pueden necesitar espacio adicional como se menciona en el comentario .

Puede motivar la solución pensando en ella en términos de simetrías (grupos, en lenguaje matemático). No importa el orden del conjunto de números, la respuesta debe ser la misma. Si va a utilizar kfunciones para ayudar a determinar los elementos que faltan, debe pensar qué funciones tienen esa propiedad: simétrica. La función s_1(x) = x_1 + x_2 + ... + x_nes un ejemplo de una función simétrica, pero hay otras de mayor grado. En particular, considere las funciones simétricas elementales . La función simétrica elemental del grado 2 es s_2(x) = x_1 x_2 + x_1 x_3 + ... + x_1 x_n + x_2 x_3 + ... + x_(n-1) x_nla suma de todos los productos de dos elementos. Del mismo modo para las funciones simétricas elementales de grado 3 y superior. Obviamente son simétricos. Además, resulta que son los bloques de construcción para todas las funciones simétricas.

Puede construir las funciones simétricas elementales a medida que avanza observando eso s_2(x,x_(n+1)) = s_2(x) + s_1(x)(x_(n+1)). Un pensamiento adicional debería convencerlo s_3(x,x_(n+1)) = s_3(x) + s_2(x)(x_(n+1))y así sucesivamente, para que puedan computarse en una sola pasada.

¿Cómo podemos saber qué elementos faltaban en la matriz? Piensa en el polinomio (z-x_1)(z-x_2)...(z-x_n). Se evalúa 0si pones en alguno de los números x_i. Expandiendo el polinomio, obtienes z^n-s_1(x)z^(n-1)+ ... + (-1)^n s_n. Las funciones simétricas elementales aparecen aquí también, lo cual no es realmente sorprendente, ya que el polinomio debería permanecer igual si aplicamos cualquier permutación a las raíces.

Así que podemos construir el polinomio e intentar factorizarlo para averiguar qué números no están en el conjunto, como han mencionado otros.

Finalmente, si nos preocupa el exceso de memoria con números grandes (el n polinomio simétrico será del orden 100!), podemos hacer estos cálculos mod pdonde pes un número primo mayor que 100. En ese caso, evaluamos el polinomio mod py encontramos que vuelve a evaluar para 0cuando la entrada es un número en el conjunto, y se evalúa a un valor distinto de cero cuando la entrada es un número que no está en el conjunto. Sin embargo, como otros han señalado, para obtener los valores del polinomio en el tiempo que depende k, no Ntenemos que factorizar el polinomio mod p.

Puedes intentar usar un filtro Bloom . Inserte cada número en la bolsa en la floración, luego itere sobre el conjunto completo de 1-k hasta que no se encuentre cada uno. Esto puede no encontrar la respuesta en todos los escenarios, pero puede ser una solución lo suficientemente buena.

Tomaría un enfoque diferente a esa pregunta y probaría al entrevistador para obtener más detalles sobre el problema más grande que está tratando de resolver. Dependiendo del problema y de los requisitos que lo rodean, la solución obvia basada en conjuntos podría ser lo correcto y el enfoque de generar una lista y seleccionarlo después podría no serlo.

Por ejemplo, podría ser que el entrevistador vaya a enviar nmensajes y necesite saber lo kque no resultó en una respuesta y lo necesita en el menor tiempo de reloj de pared posible después de que nkllegue la respuesta. Digamos también que la naturaleza del canal de mensajes es tal que, incluso ejecutándose a pleno rendimiento, hay tiempo suficiente para realizar un procesamiento entre los mensajes sin tener un impacto en el tiempo que lleva producir el resultado final después de la última respuesta. Ese tiempo se puede utilizar para insertar una faceta de identificación de cada mensaje enviado en un conjunto y eliminarlo a medida que llegan las respuestas correspondientes. Una vez que llega la última respuesta, lo único que se debe hacer es eliminar su identificador del conjunto, que en las implementaciones típicas tomaO(log k+1). Después de eso, el conjunto contiene la lista de kelementos que faltan y no hay que realizar ningún procesamiento adicional.

Este ciertamente no es el enfoque más rápido para el procesamiento por lotes de bolsas de números pre-generados porque todo funciona O((log 1 + log 2 + ... + log n) + (log n + log n-1 + ... + log k)). Pero funciona para cualquier valor de k(incluso si no se conoce de antemano) y en el ejemplo anterior se aplicó de manera que minimiza el intervalo más crítico.