Me hizo la siguiente pregunta en mi entrevista de ayer:

Considerar un Java o C++ matriz decir X que está ordenada y no hay dos elementos son los mismos. Cómo mejor se puede encontrar un índice de decir i tal que el elemento en el índice también es i. Que es X[i] = i.

Como aclaración de que ella también me dio un ejemplo:

Array X : -3 -1 0 3 5 7
index   :  0  1 2 3 4 5

Answer is 3 as X[3] = 3.

Lo mejor que yo podía pensar era una búsqueda lineal. Después de la entrevista, aunque mucho sobre este problema pero no pude encontrar ninguna solución mejor. Mi argumento es: el elemento con la propiedad puede estar en cualquier lugar en la matriz. Así que también podría ser al final de la matriz por lo que tenemos que comprobar cada elemento.

Yo sólo quería confirmar de la comunidad, aquí, que estoy en lo correcto. Por favor, dime estoy en lo correcto 🙂

  • Algunos algoritmo similar a la búsqueda binaria debe dar la mejor solución
  • No creo que Amazon gustaría exponer sus preguntas de la entrevista…
  • 4 favorits?! 5 upvotes?! De dónde eres (upvoters, favorito de los mandos de respuesta)? ¿ Es muy simple pregunta. Yo no habría tomado un buscador de trabajo que no sabe nada acerca de un binario y la interpolación de búsqueda.
  • en realidad dudo que a ellos les interesa. Si esta pregunta se responde rápidamente, siempre hay otro que lo siga para sondear la profundidad verdadera de conocimiento, en una buena entrevista. Seguro que no es un gran secreto comercial que Amazon espera que sus desarrolladores para saber acerca de la búsqueda binaria.
  • Pedro: he editado para quitar el nombre de la empresa. Alexey: yo sabía de búsqueda binaria, pero no podía pensar en cómo se aplican.
  • si solo querían saber si el candidato sabe acerca de la búsqueda binaria, entonces acababa de pedir encontrar i donde x[i] = 3 en un conjunto ordenado. Esta pregunta es interesante. Si el candidato responde de inmediato, lo más probable es que hayas visto antes, pero podrían ser inteligente y vio el truco extra de inmediato. Si el candidato responde que después de 30 segundos, ya he visto el truco. Si no pueden responder, que no se han localizado. Para separar el inteligente de los conocimientos, preguntar con una matriz de float, a ver si consiguen el mismo (ahora incorrecta) respuesta 😉
  • Es básicamente un problema de punto Fijo teorema. Parece que se ha leído algunos Joel posts 🙂
  • «y no hay dos elementos son los mismos» es la clave. Sin esa restricción, el OP es de derecho: El elemento puede estar en cualquier lugar en la matriz (o incluso en varios lugares), por lo que no se puede hacer nada mejor que O(n). (Si no me equivoco.) Así que este también podría ser una prueba de si el entrevistado lee las instrucciones/requisitos cuidadosamente.
  • Es más estrechamente relacionado con el teorema del valor intermedio. A pesar de que se aplica a funciones continuas, un enfoque similar podría ser utilizado para mostrar cómo la modificación de la búsqueda binaria se encuentra el elemento, si tal existe.
  • Cómo puede ser ajustado para trabajar en el caso en que la matriz tiene elementos duplicados ?

InformationsquelleAutor John | 2010-11-13

10 Comentarios

  1. 104

    Esto se puede hacer en O(logN) tiempo y O(1) espacio mediante el uso de un modificado ligeramente búsqueda binaria.

    Considerar la posibilidad de una nueva matriz Y tal que Y[i] = X[i] - i

    Array X : -3 -1   0  3  5  7
    index   :  0  1   2  3  4  5
    Array Y : -3 -2  -2  0  1  2

    Ya que los elementos en X están en el aumento de orden, los elementos de la
    nueva matriz Y será en no decreciente orden. Así que un binario
    búsqueda
    para 0 en Y dará la respuesta.

    Pero la creación de Y tendrá O(N) espacio y O(N) tiempo. Así que en lugar de
    la creación de la nueva matriz que acaba de modificar la búsqueda binaria tal que un
    referencia a Y[i] es reemplazado por X[i] - i.

    Algoritmo:

    function (array X) 
           low  = 0
           high = (num of elements in X) - 1
    
           while(low <= high) 
                   mid = (low + high) / 2
    
                   //change X[mid] to X[mid] - mid
                   if(X[mid] - mid == 0)
                           return mid
    
                   //change here too
                   else if(X[mid] - mid < 0)
                           low = mid + 1;
    
                   else
                           high = mid - 1;
           end while
    
           return -1 //no such index exists...return an invalid index.
    
    end function

    implementación de Java

    implementación en C++

    • Gracias por la explicación. Yo sabía de búsqueda binaria, pero nunca aunque me gustaría aplicarlo de esta manera.
    • +1 Para pensar acerca de los posibles desbordamientos.
    • «No-orden decreciente» orden ascendente?
    • una matriz de elementos idénticos podría ser visto como no ascendente, pero sin duda es no decreciente. El algoritmo depende de la no-decreciente-ness, pero se las arregla con una matriz de valores iguales.
    • No entiendo por qué la matriz resultante Y es no decreciente. Digamos que X es [3,3,3,3] Y, a continuación, sería [3, 2, 1, 0]. Es claramente decreciente. Creo que me estoy perdiendo algo aquí. puede alguien por Favor me ilumine?
    • La pregunta tiene un requisito de «no hay dos elementos de la matriz son los mismos».
    • Gracias. Me perdí esa parte de la información.
    • También , en caso de no ser capaz de recoger el ‘0’ entrada mientras que la construcción de la nueva matriz ? Que hace que sea lineal.. a la derecha ?
    • Todo está bien excepto una cosa: en realidad no demostrar que la matriz Y es no decreciente (lo cual es cierto para las condiciones dadas) y por lo tanto usted no poner de relieve la condición que hace es no decreciente. Qué cambios si el uso de números de punto flotante en lugar de números enteros? En su explicación, nada cambia, pero el algoritmo es malo para la flota y el verdadero algoritmo es o(n).
    • +1 Gran respuesta. Vale la pena señalar que Java se ha incorporado en las Matrices.binarySearch() y Colecciones.binarySearch() los métodos, de modo que usted no tiene que implementar su propio (Java 7 por lo menos). Sabiendo esto podría ahorrar un montón de tiempo en una entrevista. Probablemente no ayuda en este caso, pero me pregunto si se podría definir un objeto clave con el método equals como: equals(Integer that) { return that - X.indexOf(that) == 0; } o un método compareTo como compareTo(Integer other) { return other - axList.indexOf(other); } acabo de probar y Java no quiero que me deje de tipo motivos de seguridad.
    • No es necesario pensar en términos de una nueva matriz Y. Ver mi respuesta enlace.
    • +1 esa es mi favorito de respuesta para el dulce explicación en términos de una nueva matriz Y. Pero simple razonamiento como sugirió aquí también funciona bien y dar el mismo código.

  2. 9

    Hay algunos más rápido de soluciones, con un promedio de O(log n) o, en algunos casos, O(log log n) en lugar de O(n). Tiene un google para «búsqueda binaria» y «interpolación de búsqueda», usted es probable encontrar muy buenas explicaciones.

    Si la matriz no está ordenado, entonces sí, el elemento está en cualquier lugar y usted no puede obtener en virtud de O(n), pero ese no es el caso con matrices ordenadas.

    Alguna explicación sobre la interpolación de búsqueda como solicita:

    Mientras que la búsqueda binaria sólo preocupaciones con la comparación de dos elementos en términos de «mayor /mayor», la interpolación de búsqueda intenta también hacer uso de valores numéricos. El punto es: Usted tiene un criterio de rango de valores de 0 a, digamos, 20000. Usted busca 300 – binario de búsqueda comenzaría en la mitad del rango, en 10000. La interpolación de búsqueda estima que 300 probablemente sería en algún lugar cerca de 0 a 20000, para que se compruebe el elemento 6000 primer lugar de 10000. A continuación, de nuevo – si es demasiado alta, recurse en menor subrango, y es demasiado baja – recurse en la parte superior del subrango.

    Para una gran variedad con +- distribución uniforme de los valores, la interpolación de búsqueda debe comportarse mucho más rápido que el binario de búsqueda de código y ver por ti mismo. También, funciona mejor si primero utiliza una interpolación paso de la búsqueda, haga una búsqueda binaria paso, y así sucesivamente.

    Nota que es lo que hace un humano de manera intuitiva cuando se busca algo en un diccionario.

    • +1 para interpolation search de referencia. Es descrito en el D. Knuth libros también.
    • ¿Puede por favor explicar cómo aplicar la interpolación de búsqueda para este problema?
    • -1, no has explicado cómo aplicar la interpolación de búsqueda a este problema. El no paso obvio es que para los números enteros, si x[i] es estrictamente creciente, entonces x[i]-i es no decreciente.
    • No sé de qué estás hablando – como me han enseñado, la única algorítmica diferencia entre binario de búsqueda y la interpolación de búsqueda es el método de elección de los «punto de giro». He implementado es exactamente como se describe y funcionó como se esperaba con resultados decentes. Además, incluso si usted tiene algo de importancia práctica para agregar (que puede ser cierto y me gustaría saber que), un downvote no es apropiado para una correcta técnicamente y – creo – responder de manera útil.
    • Kos: Gracias por la explicación. Pero yo todavía no entiendo cómo aplicar la interpolación de búsqueda para este prlblem 🙁
    • la pregunta no es, «¿cómo puedo encontrar un índice de i para que x[i] == 300«. La pregunta es, «¿cómo puedo encontrar un índice de i para que x[i] == i«. Sin tener en cuenta que, yo no veo cómo esta respuesta puede ser considerada correcta (aunque sin duda es una buena descripción de una interpolación de búsqueda).
    • … Steve tienes razón :), por alguna razón hasta ahora no me di cuenta de qué se trata este problema es acerca de; aparrently tengo que renunciar a mis habilidades de programación y se centran en las habilidades de lectura en su lugar. Juan, para la interpolación de búsqueda sólo se refiere a Codaddict del post y reemplace la línea int mid = ... para la adecuada para la interpolación de búsqueda. Lo siento por la confusión, todo el mundo :).

  3. 8

    No requiere pensar en términos de una matriz Y como se sugiere en respuesta por @codaddict.

    Utilizar el binario de búsqueda y verificación de la mitad elemento de la matriz dada, si es inferior a su índice, lo que no se necesita comprobar el menor índice, ya que la matriz es
    ordenados, de manera que si nos movemos a la izquierda, restando m índices y (al menos) valor de m, todos los elementos posteriores también ser demasiado pequeño. E. g. si arr[5] = 4 luego arr[4] <= (4 - 1) y arr[3] <= (4 - 2) y así sucesivamente. Una lógica Similar se puede aplicar si la media del elemento es mayor que el de su índice.

    Aquí es simple Java aplicación:

    int function(int[] arr) {
            int low = 0;
            int high = arr.length - 1;
    
            while(low <= high) {
                int mid = high - (high - low) / 2;
    
                if(arr[mid] == mid) {
                     return mid;
                } else if(arr[mid] < mid) {
                     low = mid + 1;
                } else {
                     high = mid - 1;
                }
            }
    
            return -1; //There is no such index
    }

    Tenga en cuenta que la solución anterior funcionaría sólo si todos los elementos son distintos.

    • Lo que si arr[5] = 3, entonces la solución puede estar en arr[4] todavía o estar en arr[6]. No creo que podemos escoger una dirección, en este caso con el código de arriba
    • en este caso arr[4] debe ser menor que 3 como arr están ordenados, así que debemos buscar en el índice 6 adelante para la solución.
    • oh a la derecha, veo
    • corregidos. Gracias.
  4. 7

    Creo que esto sería más rápido.

    Inicio en el medio de la lista

    Si X[i] > yo, a continuación, ir a la media de los restantes lado izquierdo

    si X[i] < i luego ir a la media de los restantes derecho

    Seguir haciendo eso y se reducirá el número de elementos posibles por la mitad para cada bucle

  5. 3

    Puede realizar una búsqueda binaria:
    la búsqueda de la media, si el valor es menor que el índice, que no menor índice va a contener el mismo valor.

    A continuación, buscar en la mitad superior, y continuar hasta encontrar el elemento, o llegar a un elemento útil.

    • «Usted puede realizar una búsqueda binaria» – ¿Cuál es su clave?
    • el valor de la celda es el «valor» y el índice es la «clave».
    • (bajo el supuesto de que la longitud de la matriz se sabe)
    • -1, el valor de la celda no es el valor a utilizar en la búsqueda binaria.
    • todavía se puede utilizar como parte de la comparación numérica de las células valor
    • Ya que dijo un Java o C++ matriz, es una suposición segura sabemos cuánto tiempo es.
    • +1: no creo que te lo explicó muy claramente como algunos otros (por ejemplo, JOTN), pero parece que fueron los primeros con la respuesta.

  6. 1

    Esta es una solución que se me ocurrió, y funciona si hay duplicados (se me pasó por alto erróneamente que con la salvedad de que no hay duplicados).

    //invariant: startIndex <= i <= endIndex
    
    int modifiedBsearch(int startIndex, int endIndex)
    {
       int sameValueIndex = -1;
       int middleIndex = (startIndex + endIndex) /2;
       int middleValue = array[middleIndex];
       int endValue = array[endIndex];
       int startValue = array[startIndex];
    
       if(middleIndex == middleValue)
          return middleValue;
       else {
          if(middleValue <= endIndex)
             sameValueIndex = modifiedBsearch(middleIndex + 1, endIndex)
    
          if(sameValueIndex == -1 && startValue <= middleIndex)
             sameValueIndex = modifiedBsearch(startIndex, middleIndex -1);
       }
    
       return sameValueIndex;
    
    }

    Me imagino que esto se lleva a O(log n) tiempo, pero esto no está claro en la primera vista???

    Si has tenido mala suerte, se va a tomar O(n log n) tiempo (la altura de la pila de árbol será log n, y va a ser un árbol con n nodos en el último nivel, n/2 en la siguiente a la última, etc.).

    Así, en promedio será de O(log n) y O(n log n).

    • no puede ser O(n log n), puede acceder a cada elemento de a lo sumo una vez.
  7. 0

    de la parte superior de mi cabeza, haciendo binario de la división puede ser más rápido.

    fijamos en el valor medio, si es alta, entonces lo que usted necesita, la investigación en la mitad inferior.

    Después de una comparación, ya ha derramado su conjunto de datos en la mitad de

  8. 0

    Después de leer la pregunta parece que hay un escenario que puede ser utilizado para acelerar la búsqueda. Al comparar la posición para el valor, si el valor es mayor que el de la posición, a continuación, el valor puede ser utilizado como la siguiente posición para evaluar. Esto ayudará a saltar a través de la matriz más rápido. Esto se puede hacer porque la matriz está ordenada. Los valores que nos estamos saltando son conceptualmente desplazado a la izquierda en la matriz y en el lugar equivocado.

    Ejemplo:

    int ABC[] = { -2, -5, 4, 7, 11, 22, 55 };

    Si mi posición actual es de 2, y tiene un valor de 4 que no son iguales y conceptualmente el valor 4 se desplaza a la izquierda. Puedo utilizar el valor de 4 como mi nueva posición, ya que si el valor 4 está fuera de posición, entonces todo menos de 4 fuera de posición así.

    El código de ejemplo sólo por el bien de la discusión:

    void main()
    {
        int X[] = { -3, -1, 0, 3, 5, 7};
        int length = sizeof(X)/sizeof(X[0]);
    
        for (int i = 0; i < length;) {
            if (X[i] > i && X[i] < length)
                i = X[i];                 //Jump forward!
            else if (X[i] == i) {
                printf("found it %i", i);
                break;
            } else
                ++i;
        }
    }
  9. 0

    Versión modificada de Búsqueda Binaria sería suficiente supongo

    Supongamos que la secuencia es

    Array : -1 1 4 5 6
    Index :  0 1 2 3 4
    
    Result : 1

    o

    Array : -2 0 1 2 4 6 10
    Index :  0 1 2 3 4 5 6 
    
    Result: 4

    De los dos ejemplos vemos que el resultado requerido nunca se acueste sobre el lado derecho si a mediados de < a[mid]… pseudocódigo sería algo como esto

    mid <- (first + last )/2
    
    if a[mid] == mid then
           return mid
    
    else if a[mid] < mid then
            recursive call (a,mid+1,last)
    
    else 
             recursive call (a,first,mid-1)
  10. 0

    Java:

    public static boolean check (int [] array, int i)
    {
        if (i < 0 || i >= array.length)
            return false;
    
        return (array[i] == i);
    }

    C++:

    bool check (int array[], int array_size, int i)
    {
        if (i < 0 || i >= array_size)
            return false;
    
        return (array[i] == i);
    }

Dejar respuesta

Please enter your comment!
Please enter your name here