Pregunta La pregunta fácil de la entrevista se hizo más difícil: dados los números 1..100, encuentre los números que faltan


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

Q1: Tenemos una bolsa que contiene números 1, 2, 3, ..., 100. Cada número aparece exactamente una vez, por lo que hay 100 números. Ahora se saca al azar 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 a lo largo de las líneas de:

A1: Bueno, la suma de los números 1 + 2 + 3 + … + N es (N+1)(N/2) (ver Wikipedia: suma de series aritméticas) por 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 esta, y la diferencia es ese número. Entonces podemos encontrar el número que falta en O(N) tiempo y O(1) espacio.

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

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

Nunca había visto / escuchado / considerado esta variación antes, así que entré en pánico y no pude responder la pregunta. El entrevistador insistió en conocer mi proceso de pensamiento, así que mencioné que tal vez podamos obtener más información comparando el producto esperado, o tal vez haciendo un segundo pase después de haber reunido algo de información desde el primer pase, etc., pero realmente solo estaba disparando en la oscuridad en lugar de tener un camino claro hacia la solución.

El entrevistador intentó alentarme 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 conocer la respuesta antes de la mano), y pregunté si esta es una técnica de programación general (léase: "útil"), o si solo es una respuesta truco / respuesta.

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

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

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

Entonces la pregunta aquí es simple:

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

Aclaraciones

  • Generalmente hay norte números de 1 ..norte, no solo 1..100.
  • No estoy buscando la solución obvia basada en conjuntos, p. usando un conjunto de bits, codificando la presencia / ausencia de cada número por el valor de un bit designado, por lo tanto usando O(N)bits en espacio adicional. No podemos permitirnos ningún espacio adicional proporcional a norte.
  • Tampoco estoy buscando el enfoque obvio de ordenar primero. Esto y el enfoque basado en conjuntos son dignos de mención en una entrevista (son fáciles de implementar y dependen de norte, puede ser muy práctico). Estoy buscando la solución del Santo Grial (que puede ser o no práctica de implementar, pero tiene las características asintóticas deseadas).

Así que de nuevo, por supuesto, 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 norte), y luego debe encontrar el k los números que faltan de alguna manera.


983
2017-08-16 10:26


origen


Respuestas:


Aquí hay un resumen de Dimitris Andreou enlazar.

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

un1 + a2 + ... + ak = b1

un12 + a22 + ... + ak2 = b2

...

un1k + a2k + ... + akk = bk

Utilizando Identidades de Newton, sabiendo byo permite calcular

do1 = a1 + a2 + ... ak

do2 = a1un2 + a1un3 + ... + ak-1unk

...

dok = a1un2 ... unk

Si expandes el polinomio (x-a1) ... (x-ak) los coeficientes serán exactamente c1, ..., ck - ver Las fórmulas de Viète. Dado que cada factor polinomial es único (el anillo de polinomios es un Dominio euclidiano), esto significa unyo 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 varía, el enfoque directo de calcular c1,...,dok es prohibitivamente caro, ya que p. dok es el producto de todos los números que faltan, magnitud n! / (n-k) !. Para superar esto, realice cálculos en Zq campo, donde q es un primo tal que n <= q <2n - existe por El postulado de Bertrand. La prueba no necesita ser modificada, ya que las fórmulas aún se mantienen, y la factorización de polinomios es aún única. También necesita un algoritmo para la factorización sobre campos finitos, por ejemplo, el de Berlekamp o Cantor-Zassenhaus.

Seudocódigo de alto nivel para constante k:

  • Calcule i-ésimo poder de números dados
  • Reste para obtener sumas de i-ésimas potencias de números desconocidos. Llamar a las sumas byo.
  • Usa las identidades de Newton para calcular los coeficientes de byo; llámalos cyo. Básicamente, c1 = b1; do2 = (c1segundo1 - b2) / 2; ver Wikipedia para fórmulas exactas
  • Factorizar el polinomio xk-do1Xk-1 + ... + ck.
  • Las raíces del polinomio son los números necesarios a1, ..., unk.

Para variar k, encuentre un primo n <= q <2n usando, p. Ej. Miller-Rabin, y realice los pasos con todos los números reducidos módulo q.

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


512
2017-08-16 12:13



Lo encontrará leyendo el par de páginas de Muthukrishnan - Algoritmos de flujo de datos: Puzzle 1: Encontrar números perdidos. Muestra exactamente la generalización que está buscando. Probablemente esto es lo que su entrevistador leyó y por qué planteó estas preguntas.

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


Ver también sdcvvc's respuesta directamente relacionada, que también incluye pseudocódigo (¡hurra! no hay necesidad de leer esas complicadas formulaciones matemáticas :)) (¡gracias, gran trabajo!).


226
2017-08-16 11:26



Podemos resolver Q2 sumando ambos números, y el cuadrícula de los números.

Entonces podemos reducir el problema a

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

Dónde x y y son qué tan lejos están las sumas por debajo de los valores esperados.

Sustituir nos da:

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

Que podemos resolver para determinar nuestros números faltantes.


159
2017-08-16 10:37



Como @j_random_hacker señaló, esto es bastante similar a Encontrar duplicados en O (n) tiempo y O (1) espacio, 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 O(N) tiempo y O(k) espacio adicional.

Primero, ampliamos nuestra matriz A[] por k elementos, por lo que ahora es de tamaño N. Este es el O(k) espacio adicional. A continuación, ejecutamos el siguiente 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

El primer bucle inicializa el k entradas adicionales a la misma que la primera entrada en la matriz (este es simplemente un valor conveniente que sabemos que ya está presente en la matriz - después de este paso, las entradas que faltaban en la matriz inicial de tamaño) N-k 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, luego una de esas entradas estará en posición A[x].

Tenga en cuenta que, aunque tiene un bucle anidado, aún se ejecuta en O(N) tiempo: un intercambio solo ocurre 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 intercambios (y, por lo tanto, el número total de ejecuciones de while cuerpo de bucle) es como máximo N-1.

El tercer ciclo imprime esos índices de la matriz i que no están ocupados por el valor i - esto significa que i debe haber estado perdido.


120
2018-04-22 04:32



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


114
2018-04-12 18:59



No estoy seguro, si es la solución más eficiente, pero haría un bucle en todas las entradas, y usaré un conjunto de bits para recordar, qué números están establecidos, y luego probaré 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.


30
2017-08-16 10:38



No he comprobado las matemáticas, pero sospecho que la informática Σ(n^2) en el mismo paso que calculamos Σ(n) proporcionaría suficiente información para obtener dos números que faltan, Σ(n^3) también si hay tres, y así sucesivamente.


29
2017-08-16 10:38



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 sdcvvc y los algoritmos de 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)`

Asi 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: suponiendo que la informática a^j toma ceil(log_2 j) tiempo, 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 simple recursivo algoritmo. Deja que yo sea la i-ésima entrada en la bolsa, n el número de números antes remociones, y k el número de remociones. 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.


12
2017-09-02 11:41