algorithm - trabajo - ¿Encontrar la existencia del número en una lista ordenada en tiempo constante?(Pregunta de la entrevista)

preguntas y respuestas en una entrevista de trabajo para ventas (16)

Estoy estudiando para próximas entrevistas y me he encontrado con esta pregunta varias veces (escrito textualmente)

Encuentre o determine la no existencia de un número en una lista ordenada de N números donde los números van sobre M, M >> N y N lo suficientemente grandes como para abarcar múltiples discos. Algoritmo para vencer a O (log n); Puntos extra por algoritmo de tiempo constante.

En primer lugar, no estoy seguro de si esta es una pregunta con una solución real. Mis colegas y yo hemos reflexionado sobre este problema durante semanas y parece que está mal formado (por supuesto, solo porque no podamos pensar en una solución no significa que no haya una). Algunas preguntas que le habría hecho al entrevistador son:

¿Hay repeticiones en la lista ordenada?
¿Cuál es la relación con el número de discos y N?

Un enfoque que consideré fue la búsqueda binaria del mínimo / máximo de cada disco para determinar el disco que debería contener ese número, si existe, y luego la búsqueda binaria en el propio disco. Por supuesto, esto es solo un orden de aceleración de magnitud si el número de discos es grande y también tiene una lista ordenada de discos. Creo que esto produciría algún tipo de tiempo O (log log n).

En cuanto a la sugerencia de M >> N, tal vez si sabes cuántos números hay en un disco y cuál es el rango, podrías usar el principio de casillero para descartar algunos casos algunas veces, pero no puedo encontrar una Mejora del orden de magnitud.

Además, "los puntos de bonificación por el algoritmo de tiempo constante" me hacen un poco sospechoso.

¿Alguna idea, solución o historia relevante de este problema?

Bueno, según mi conocimiento. En este problema puedes aprovechar dos pistas. 1. Los números están ordenados y 2. N y M son muy grandes (N >> M) y M abarca varios discos

Puedes usar un poco de aleatoriedad en este problema. En lugar de utilizar la búsqueda binaria, elija un punto al azar y luego verifique si x (número a buscar) es menor o mayor que el valor actual. Puede comenzar desde ambos extremos y reducir iterativamente el tamaño del espacio de búsqueda. Solo en iteraciones muy pequeñas puede reducirlo a un dominio pequeño y, posteriormente, puede aplicar la búsqueda binaria de eficiencia.

Como conocemos el rango de los números (M), podríamos realizar una búsqueda binaria interpolada. En lugar de dividir en dos el rango de búsqueda por 1/2, dividirlo en N / (HI - LO). El resultado seguirá siendo O (log N) pero con una constante más baja. Esta técnica funciona mejor si sabemos que no hay duplicados en los datos, y la pregunta parece indicar que podría ser el caso, pero no es definitiva.

Vea por ejemplo este blog: Más rápido que la búsqueda binaria

Creo que el problema indica claramente que se le da una lista de tamaño N , como

const int N = 15; int xs[N] = {1, 3, 7, 9, 13, 16, 17, 19, 21, 24, 25, 26, 27, 28, 30};

Debe responder a una única consulta (en menos de O(logN) ) y, por lo tanto, no puede realizar ningún preprocesamiento. Creo que la pregunta se habría formulado de manera diferente en tal caso si pudiera ir por los tiempos amortizados.

En la práctica, N puede ser realmente grande, por lo que incluso el número N sí puede necesitar muchos discos para ser almacenados (la forma en que leí la pregunta:). Creo que esto simplemente denota que no se puede crear una matriz de búsqueda simple de tamaño M, porque M > N , por lo tanto, no tiene sentido.

Entonces, realmente no puedes hacerlo mejor que la búsqueda binaria. Sin embargo, como sabe el valor máximo posible de los elementos, que es M (y suponiendo que los datos están distribuidos uniformemente), puede adivinar la posición inicial, donde comenzar la búsqueda binaria.

Esto es esencialmente x / M * N , en código podría ser algo así:

double hint = static_cast<double>(x) / M; // between [0,1) int m = static_cast<int>(hint * N); // guess the position in xs // do binary search using m as initial "middle" point.

Por lo tanto, esta suposición, dada la retención de supuestos, acelerará el algoritmo en una constante agradable. Sin embargo, la complejidad del tiempo seguirá siendo O(lgN) .

Creo que puede obtener algunos tiempos de búsqueda más rápidos si se permite el uso de algunos metadatos.

Configure una serie de bloques o listas indirectas cuyos elementos apuntan a más listas / bloques indirectos. Repita hasta que llegue a un nivel deseado de bloques / lista directos. La idea es usar algo similar a cómo algunos sistemas de archivos acceden a sus datos de archivos (bloques directos, indirectos, doblemente indirectos y triplemente indirectos). Es muy probable que para los rangos de números que solicitan, necesite más del triple de direccionamiento indirecto.

Cada parte del número que está buscando puede referirse a un índice separado en las tablas indirectas / directas. Eventualmente, habrá interrumpido la búsqueda lo suficiente como para poder leer la sección final que puede o no contener el número. Luego puede buscar en esta sección final con un algoritmo de su elección.

Espero que esto ayude y tenga sentido.

Descargo de responsabilidad: voy a almorzar en un minuto y, por lo tanto, no lo he pensado por completo, ya que puede ser poco práctico.

Dado que la pregunta no indica en qué formato se almacenan los números, puede decirle al entrevistador que asumirá que los números se almacenan de manera física. Por ejemplo, cada número puede escribirse en una tarjeta y cada tarjeta es propiedad de una sola persona.

N lo suficientemente grande como para abarcar varios discos

Ahora, si desea encontrar o determinar la no existencia de un número, solo puede preguntar a las personas si el número que está buscando está en la tarjeta que están sosteniendo.

Si nadie responde dentro de N segundos, entonces el número no está allí. Esto es asumiendo que todos pueden escucharlo y cada persona es consciente del número que tiene en su tarjeta.

No sé mucho acerca de la física (velocidad del sonido, fricción del aire, tiempo para que el cerebro de cada persona mire su tarjeta, etc.)

Es un hecho comprobable que cualquier algoritmo que haga comparaciones no puede batir log (n). Eso significa que una solución de tiempo constante no puede comparar números entre sí. Una solución de tiempo constante implicará engaños en todos los casos.

Dado que, una solución de tiempo constante es posible con una serie de suposiciones:

Los números se escriben secuencialmente.
Usted sabe exactamente dónde comienza la secuencia numérica y dónde termina exactamente (desplazamiento del disco)
Todos los discos son del mismo tamaño y tienen exactamente la misma capacidad de bits
Usted sabe exactamente cuántos bits se pueden escribir en un disco

Dados esos supuestos, simplemente multiplique k por el tamaño de bit del número. Busque esa ubicación (O (1)) + desplazamiento y vuelva a leer el número correcto de bits.

Esta es muy probablemente una pregunta mal formulada.

Si los filtros Bloom son la respuesta que buscaban, lo más probable es que no haya necesidad de confundir al candidato con un elemento de algoritmo distribuido / paralelo potencial (discos múltiples).

Asumiendo un disco

Los filtros Bloom son operaciones de tiempo constante una vez que se construye el filtro. Pero, para compensar los falsos positivos, uno tendrá que hacer una búsqueda binaria (o incluso la búsqueda por interpolación como alguien sugirió que asume una distribución uniforme) contribuirá a un factor mayor que el registro constante (n) en el caso de búsqueda binaria.

entonces, es O (k) + 1% * log (n). O (k) Tiempo constante para comprobar el filtro de floración. luego, asumiendo una tasa de error del 1% (falsos positivos) con filtro de floración, que muchas veces uno tendrá que hacer una búsqueda binaria para asegurarse de que realmente existe.

No estoy seguro de que esto pueda reducirse a tiempo constante con análisis amortizado (no demasiado versado allí).

La pregunta es acerca de la no existencia, por lo que no es necesario buscar en los discos. Podemos verificar si el número X está fuera del rango mínimo y máximo de todos los discos en O (1). (el número de discos es constante)

bool not_exists=true for each disk_i in disks: not_exists &&= (X <min_element(disk_i) || X > max_element(disk_i) ) return not_exists

Si el resultado es cierto. entonces podemos estar seguros de que no hay X en los discos. De lo contrario, X ''podría estar'' en los discos.

Por extraño que parezca la pregunta es determinar la NO EXISTENCIA de un valor, no la existencia.

Esto puede implicar que se refieren a un filtro Bloom ( http://en.wikipedia.org/wiki/Bloom_filter ). Un filtro Bloom puede decirte si un elemento:

no existe
o posiblemente exista

Por la letra de la pregunta, probablemente están buscando una búsqueda de interpolación, que es el caso promedio O (log log n). Sí, esto es O (n) en el peor de los casos, pero puede mejorarse con el conocimiento de la distribución o mediante una búsqueda binaria de interpolación.

Esto juega en la pista M >> N. El análisis de casos promedio para la búsqueda de interpolación es bastante complejo, por lo que ni siquiera intentaré una modificación en M >> N. Pero conceptual, en M >> N y suponiendo una distribución uniforme, puede asumir que el valor estará limitado por +/- 1 de la posición de búsqueda inicial, dando O (1).

Una implementación práctica podría hacer la interpolación inicial una vez, y si el valor de búsqueda no está limitado, recurra a una búsqueda binaria.

Sin embargo, no estoy seguro de cómo se podrían usar los discos múltiples para aprovechar este enfoque ...

Sólo un pensamiento humilde.

Tal vez esto sea más una cuestión de sistema que una pregunta de algoritmo, tratemos de pensar desde el motor de búsqueda.

Supongamos que tengo suficientes máquinas para tener todos los N enteros ordenados indexados, con cada máquina solo una cantidad fija de documentos K que representan K de los N enteros.

De este modo, para cualquier número X dado, el tiempo de conexión en red para que el servidor de consultas del cliente alcance los nodos de búsqueda se puede tratar como tiempo constante; el tiempo para que un nodo de búsqueda busque un documento que represente el número X también es un tiempo constante, ya que la cantidad de documentos en cada nodo de búsqueda es un número fijo K.

Así, el tiempo total es constante. Sin embargo, esto es más o menos similar a lo que Enrique mencionó.

Si solo se utilizan comparaciones, tenemos un límite inferior Omega (log N) (caso más desfavorable) (es decir, O (1) no es posible).

Digamos que decide mirar alguna posición en la matriz, entonces su adversario puede colocar el elemento en la parte de la matriz que es más grande.

Por lo tanto, en cada paso, tiene al menos la mitad de los elementos por considerar y, por lo tanto, Omega (logn) en el peor de los casos.

Por lo tanto, probablemente deba dejar de usar solo comparaciones para obtener mejores resultados que O (log N) en el peor de los casos.

Como mencionó alguna otra respuesta, usted podría hacer una búsqueda probabilística de tiempo constante que le dé la respuesta correcta con una probabilidad razonable, por ejemplo, para usar Bloom Filters.

Si todo lo que podemos hacer es comparar, entonces, como se señala en un póster de arriba, no podemos hacerlo mejor que O (log (N)).

Pero, si sabemos un poco más sobre la distribución de entrada, podemos hacer más cosas. Si el entrevistador le dice (a los entrevistadores :) que los números son contiguos, entonces es posible una solución O (1). La diferencia entre el primer elemento y el elemento que estamos buscando nos dará un lugar exacto que deberíamos esperar para encontrar el número.

Un aspecto que aún no se ha mencionado es que la pregunta no es específica sobre qué tipo de computadora está utilizando. Es trivial hacer esto en un tiempo constante si cada disco duro simplemente se conecta a su propia CPU.

Esto parece una anulación, pero si esta pregunta fue hecha por un entrevistador que hace computación distribuida, podría ser la respuesta que están buscando.

puede resolver esta pregunta comprobando el tamaño del archivo que contiene el número y luego crear un número cuyo tamaño sea mayor que el tamaño del archivo (no hable abt int o lar

Primera vista

M >> N no es una pista, creo, simplemente desalienta la creación de un mapa de bits que le diría directamente en O (1) tiempo si existe un número.

Creo que una suposición sensata con N que abarca varios discos duros es que puede esperar que no tenga a su disposición más discos magnéticos o magnéticos. Como necesitará 2 ^{M de} espacio para el rendimiento de O (1), y si N abarca varios discos, M abarca >> discos múltiples y 2 ^M >> discos que los disponibles.

Además, le indica que el método para almacenar los números faltantes no sería eficiente ya que entonces tendría que almacenar números X donde

X = M - N => X ~ M (desde M >> N)

que es entonces un caso peor.

Así que a primera vista parece que puedes probar que no hay una respuesta mejor conocida.

EDITAR: Todavía estoy en el razonamiento anterior, que también está mejor probado por la respuesta de Moron. Sin embargo, la conclusión, después de ver la respuesta de Patrick a Bloom Filter, creo que el entrevistador podría haber estado observando este y otros algoritmos probabilísticos (que deberían haberse anotado en la pregunta de la entrevista).