La tarea es claramente encontrar un algoritmo que sea O (1) en la longitud N de la lista de números requeridos.
Por lo tanto, no importa si necesita los 100 primeros o 10000 números, el tiempo de inserción debe ser O (1).
El truco aquí es que aunque ese requisito de O (1) se menciona para la inserción de la lista, la pregunta no dijo nada sobre el orden del tiempo de búsqueda en todo el espacio numérico, pero resulta que esto se puede hacer O (1) también.
La solución entonces es la siguiente:
-
Organice una tabla hash con números para las teclas y pares de punteros de la lista vinculada para los valores. Cada par de punteros es el comienzo y el final de una secuencia de lista enlazada. Esto normalmente será solo un elemento y luego el siguiente. Cada elemento de la lista enlazada va junto al elemento con el siguiente número más alto. Por lo tanto, la lista enlazada contiene la secuencia ordenada de números requeridos. Mantenga un registro del número más bajo.
-
Toma un nuevo número x de la secuencia aleatoria.
-
¿Es más alto que el último número más bajo registrado? Sí = > Paso 4, No = > Paso 2
-
Pulsa la tabla hash con el número que acaba de tomar. ¿Hay alguna entrada? Sí = > Paso 5. No = > Toma un nuevo número x-1 y repite este paso
(esta es una búsqueda lineal descendente simple, solo tenga paciencia conmigo, esto se puede mejorar y explicaré cómo)
-
Con el elemento de lista que se acaba de obtener de la tabla hash, inserte el nuevo número justo después del elemento en la lista vinculada (y actualice el hash)
-
Tome el número más bajo que he registrado (y elimínelo del hash / lista).
-
Pulsa la tabla hash con el número que acaba de tomar. ¿Hay alguna entrada? Sí = > Paso 8. No = > Toma un nuevo número l + 1 y repite este paso
(esta es una búsqueda lineal ascendente simple)
-
Con un golpe positivo, el número se convierte en el nuevo número más bajo. Vaya al paso 2
Para permitir valores duplicados, el hash realmente necesita mantener el inicio y el final de la secuencia de la lista vinculada de elementos que son duplicados. Agregar o eliminar un elemento en una clave dada aumenta o disminuye el rango al que apunta.
La inserción aquí es O (1). Las búsquedas mencionadas son, supongo algo así como, O (diferencia promedio entre números). La diferencia promedio aumenta con el tamaño del espacio numérico, pero disminuye con la longitud requerida de la lista de números.
Por lo tanto, la estrategia de búsqueda lineal es bastante pobre, si el espacio numérico es grande (por ejemplo, para un tipo int de 4 bytes, 0 a 2 ^ 32-1) y N = 100. Para solucionar este problema de rendimiento, puede mantener conjuntos paralelos de tablas hash, donde los números se redondean a magnitudes más altas (por ejemplo, 1s, 10s, 100s, 1000s) para hacer las claves adecuadas. De esta manera, puede subir y bajar de velocidad para realizar las búsquedas requeridas más rápidamente. Entonces, el rendimiento se convierte en una O (número de registro), creo que es constante, es decir, O (1) también.
Para aclarar esto, imagine que tiene el número 197 a mano. Golpeaste la tabla hash de los 10, con '190', se redondea a la decena más cercana. ¿Cualquier cosa? No. Así que desciendes en 10 segundos hasta que alcanzas, por ejemplo, 120. Luego, puedes comenzar con 129 en la tabla hash 1s, luego prueba 128, 127 hasta que golpees algo. Ahora ha encontrado dónde en la lista enlazada para insertar el número 197. Al ponerlo, también debe actualizar la tabla hash 1s con la entrada 197, la tabla hash 10 con el número 190, 100s con 100, etc. La mayoría de los pasos lo que debe hacer aquí es 10 veces el registro del rango de números.
Puede que me hayan equivocado algunos de los detalles, pero dado que este es el intercambio de programadores y el contexto fueron las entrevistas, espero que lo anterior sea una respuesta suficientemente convincente para esa situación.
EDIT Agregué algunos detalles adicionales aquí para explicar el esquema de tabla hash paralela y cómo las búsquedas lineales deficientes que mencioné pueden reemplazarse con una búsqueda O (1). También me he dado cuenta de que, por supuesto, no hay necesidad de buscar el siguiente número más bajo, porque puedes avanzar directamente hacia él en la tabla hash con el número más bajo y pasar al siguiente elemento.