Estás dado un array de N enteros de 64 bits. N puede ser muy grande. Usted sabe que cada entero 1..N aparece una vez en la matriz, excepto que hay un número de desaparecidos y un número duplicado.

Escribir un algoritmo de tiempo lineal para encontrar a los desaparecidos y se duplican los números. Además, el algoritmo debe ejecutarse en el pequeño espacio continuo y salir de la matriz de la virgen.

Fuente: http://maxschireson.com/2011/04/23/want-a-job-working-on-mongodb-your-first-online-interview-is-in-this-post/

  • Creo que usted encontrará útil esta información: stackoverflow.com/questions/3492302/…
  • En realidad que es diferente. Aquí se obtienen las ecuaciones de la forma suma de^k – suma de b^k = s, mientras que la que tiene suma a^k + suma de b^k = s, lo que nos permite el uso de Newton Identica. No parece obvio que si podemos utilizar los Newtoniano Identica aquí también. De hecho, esto parece más relevante: stackoverflow.com/questions/5249985/…
  • y es por eso que yo le dije que pensaba que iba a encontrar que es útil, en lugar de votar a cerca de la pregunta como un duplicado.
  • Me estaba diciendo que podría no ser tan útil como uno podría pensar. No estaba hablando de engañar o nada. De todos modos…
InformationsquelleAutor KushalP | 2011-04-23

8 Comentarios

  1. 37

    Si todos los números estaban presentes en la matriz de la suma sería de N(N+1)/2.

    Determinar la suma real, al sumar todos los números en la matriz de O(n), este Sum(Actual).

    Un número que falta, este j y un número se duplica, este k. Eso significa que

    Suma(Real) = N(N+1)/2 + k – j

    deriva de que

    k = Suma(Real) -N(N+1)/2 + j

    También podemos calcular la suma de los cuadrados de la matriz, que se resumen a
    n3/3 + n2/2 + n/6. si todos los números estaban presentes.

    Ahora podemos calcular la suma real de las plazas que en O(n), este Sum(Actual Squares).

    Suma(Real Cuadrados) =n3/3 +
    n2/2 + n/6 + k2
    – j2

    Ahora tenemos dos ecuaciones con las que se puede determinar j y k.

    • Buen análisis. Yo generalizada a m<N incógnitas.
    • con ‘N tal vez muy grande», las necesidades de este tipo bigInt apoyo
  2. 29

    El XOR truco funciona en dos pasos con un sólo lectura de la matriz.

    Esto evita el problema de posibles desbordamientos de enteros que la suma y la suma de los cuadrados de la solución.

    Dejar que los dos números sean x y y, uno de los cuales es el número que falta y el otro repetido.

    XOR de todos los elementos de la matriz, junto con 1,2,...,N.

    El resultado es w = x XOR y.

    Ahora ya x y y son distintos, w es distinto de cero.

    Elegir cualquier no-bit cero de w. x y y difieren en este bit. Dicen que la posición de los bits es k.

    Ahora considere la posibilidad de una división de la matriz (y los números 1,2,...,N) en dos grupos, en función de si el bit en la posición k es 0 o 1.

    Ahora si calculamos el XOR (por separado) de los elementos de los dos conjuntos, el resultado tiene que ser x y y.

    Ya que los criterios para la división es sólo la comprobación de si un bit está establecido en no, se pueden calcular los dos XORs de los dos conjuntos por hacer otro pase a través de la matriz y el hecho de tener dos variables, cada una de las cuales contiene el XOR de los elementos vistos hasta ahora (y 1,2,...N), para cada conjunto. Al final, cuando hayamos terminado, estas dos variables se mantenga x y y.

    Relacionados con:

    • Hay una teoría/ libro de escritura que puede elaborar sobre esto?
  3. 6

    El uso de la idea básica de un relacionada con la pregunta de la entrevista usted podría hacer:

    • Suma de todos los números (vamos a llamar a esto S1) y sus plazas (S2)
    • Calcule la suma de los números, sin modificaciones, es decir, E1 = n*(n+1)/2 y E2 = n*(n+1)*(2n+1)/6
    • Ahora usted sabe que E1 - S1 = d - m y E2 - S2 = d^2 - m^2, donde d es el duplicado del número y m falta.
    • Resolver este sistema de ecuaciones y usted encontrará que:

      m = 1/2 ((E2 - S2)/(E1 - S1) - (E1 - S1))
      d = 1/2 ((E2 - S2)/(E1 - S1) + (E1 - S1)) //or even simpler: d = m + (E1 - S1)
      

    .

    $S1 = $S2 = 0;
    foreach ($nums as $num) {
        $S1 += $num;
        $S2 += $num * $num;
    }
    
    $D1 = $n * ($n + 1) /2                - $S1;
    $D2 = $n * ($n + 1) * (2 * $n + 1) /6 - $S2;
    
    $m = 1/2 * ($D2/$D1 - $D1);
    $d = 1/2 * ($D2/$D1 + $D1);
    
    • Excepto que en realidad no se O(n) si los números son 1..n en lugar de 1..100.
    • ¿Por qué no es? Bucle a través de n valores es O(n) ¿no? Y los demás cálculos se O(1).
    • porque el resultado de la adición de n números de 64 bits no es necesariamente un 64-bit número, por lo que usted necesita escribir el código de manejar grandes enteros. Que el código no se ejecuta en tiempo constante. El cuadrado n es también no O(1) – aviso que n no tiene límite superior. No es que su solución es malo ni nada, yo no creo que sea posible hacerlo en el OP restricciones, solo estoy diciendo que no es lineal.
    • No veo ningún problema. Usted necesita un constante cantidad de 191 bits de la suma de cuadrados y 128 bits para la suma normal.
    • el acto de añadir o multipling (cuadratura) de 64 bits número es constante en el tiempo. El resultado de esta operación es en la mayoría de los 128 bits de número, y el resultado de la suma de todos los posibles números de 128 bits juntos es en la mayoría de 256 bits número. Hay una constante de límite superior de 256 bits número, y desde el tiempo que se necesita para operar en los números está relacionado con la longitud de los números, para los que hay un límite superior, es una operación constante.
    • Creo que se puede eliminar la necesidad de >64 bits por completo el uso de la aritmética modular…

  4. 5

    Aquí es una implementación Java basadas en @Aryabhatta ‘s idea:

    Entrada:[3 1 2 5 3]

    Salida:[3, 4]

    public ArrayList<Integer> repeatedNumber(final List<Integer> A) {
        ArrayList<Integer> ret = new ArrayList<>();
        int xor = 0, x = 0, y = 0;
        for(int i=0; i<A.size(); i++) {
            xor ^= A.get(i);
        }
        for(int i=1; i<=A.size(); i++) {
            xor ^= i;
        }
    
        int setBit = xor & ~(xor-1);
        for(int i=0; i<A.size(); i++) {
            if((A.get(i) & setBit) != 0) {
                x ^= A.get(i);
            } else {
                y ^= A.get(i);
            }
        }
        for(int i=1; i<=A.size(); i++) {
            if((i & setBit) != 0) {
                x ^= i;
            } else {
                y ^= i;
            }
        }
    
        for(int i=0; i<A.size(); i++) {
            if(A.get(i) == x) {
                ret.add(x);
                ret.add(y);
                return ret;
            } 
    
            if(A.get(i) == y) {
                ret.add(y);
                ret.add(x);
                return ret;
            }
        }
    
        return ret;
    }
    
  5. 3

    La solución propuesta por BrokenGlass cubre el caso de dos incógnitas (correspondiente a un número duplicado y la falta de un solo número), a través de dos fórmulas:

    Encontrar a los desaparecidos y elementos duplicados de un array en el tiempo lineal y constante de espacio

    y

    Encontrar a los desaparecidos y elementos duplicados de un array en el tiempo lineal y constante de espacio

    Las fórmulas de rendimiento de la generalizada número armónico de pedidos n -1 y -2, respectivamente. (El poder de la serie)

    Esta solución es generalizable para 3 incógnitas, incluyendo el valor de la generalizada número armónico de orden n de -3.

    Encontrar a los desaparecidos y elementos duplicados de un array en el tiempo lineal y constante de espacio

    Para resolver m incógnitas (los duplicados y los números que faltan), el uso de m generalizada de la armónica de los números de las órdenes de n de -1 a -m.


    Morón señala que este enfoque se discutió anteriormente en StackOverflow en Fácil pregunta de la entrevista hizo más difícil.

    • Armónica de los números son de la forma 1+ 1/2 + 1/3 + … + 1/n.
    • Me estoy refiriendo a la generalizada armónica de los números de ordenes negativas. (consulte en.wikipedia.org/wiki/… )
    • Esas parecen ser solamente definido solo para m >= 1, pero lo que dices tiene sentido. Esta es otra referencia: mathworld.wolfram.com/PowerSum.html. Véase la ecuación 11.
    • La generalizada número armónico permite para m<0. Intente ejecutar Table[HarmonicNumber[10, -m], {m, 1, 7}] en Mathematica. O Sum[p^k, {p, 1, n}]. Gracias por el enlace a PowerSum, que también parece encajar.
    • Estoy de acuerdo con usted. Es bien definida para todo m. No entendí la página de la wiki.
    • por cierto, tu respuesta es la falta de uso de uso de Newton Identidades para formar un polinomio cuyas raíces buscamos. Además, la generalización ya ha sido tratado aquí: stackoverflow.com/questions/3492302/…
    • Gracias. Voy a hacer una referencia a la discusión anterior citado.
    • De hecho me acabo de dar cuenta, de Newton identidades no se aplican directamente… Como obtenemos las ecuaciones de la forma \sum (x_i)^k – \sum (y_i)^k = P_k. Base de Groebner sería una manera de ir, o se puede generalizar mi respuesta aquí: stackoverflow.com/questions/5249985/…

  6. 3

    Tomar la leave the array untouched requisito literalmente (es decir, la matriz puede ser temporalmente modificar siempre y cuando no cambie en el final), una programación orientada a la solución puede ser sugerido.

    Supongo que el tamaño de un array N es mucho menor que 2^64 que es muy poco realista cantidad de memoria. Por lo que podemos asumir con seguridad que N < 2^P tal que P << 64 (mucho menor). En otras palabras, esto significa que todos números en la matriz tienen algunos alta bits no utilizados. Así que vamos a utilizar el bit superior como un indicador de si el índice de la posición que se ha visto en la matriz. El algoritmo es como sigue:

     set HIGH = 2^63  //a number with only the highest bit set
     scan the array, for each number k do
       if array[k] < HIGH: array[k] = array[k] + HIGH //set the highest bit
       else: k is the duplicate
     for each i in 1..N do
       if array[i] < HIGH: i is missing
       else: array[i] = array[i] - HIGH //restore the original number
    

    Este es el tiempo lineal y muy poco de computación

  7. 1
        long long int len = A.size();
        long long int sumOfN = (len * (len+1) ) /2, sumOfNsq = (len * (len +1) *(2*len +1) )/6;
        long long int missingNumber1=0, missingNumber2=0;
    
        for(int i=0;i<A.size(); i++){
           sumOfN -= (long long int)A[i];
           sumOfNsq -= (long long int)A[i]*(long long int)A[i];
        }
    
        missingno = (sumOfN + sumOfNsq/sumOfN)/2;
        reaptingNO = missingNumber1 - sumOfN;
    
  8. -2

    Pseudo código suponiendo que el conjunto se ordena

    missing = nil
    duplicate = nil
    
    for i = 0, i < set.size - 1, i += 1
      if set[i] == set[i + 1]
        duplicate = set[i]
      else if((set[i] + 1) != set[i+1])
        missing = set[i] + 1
      if missing != nil && duplicate != nil
        break
    
    return (missing, duplicate)
    
    • Es casi seguro que no asumir el array está ordenado.

Dejar respuesta

Please enter your comment!
Please enter your name here