Obtén los 100 números más altos de una lista infinita

Digamos que k es el número de números más altos que quieres saber (100 en tu ejemplo). Luego, puede agregar un nuevo número en O(k) que también es O(1) . Porque O(k*g) = O(g) if k is not zero and constant .

Mantener la lista sin clasificar. Determinar si insertar o no un nuevo número llevará más tiempo, pero la inserción será O (1).

Esto es fácil. El tamaño de la lista de constantes, por lo tanto, el tiempo de clasificación de la lista es constante. Una operación que se ejecuta en tiempo constante se dice que es O (1). Por lo tanto, la clasificación de la lista es O (1) para una lista de tamaño fijo.

Una vez que pase los 100 números, el costo máximo en el que incurrirá para el próximo número es el costo para verificar si el número está entre los 100 números más altos (etiquetemos que Hora de verificación ) más el costo para ingresarlo en ese conjunto y expulsar el más bajo (llamémoslo EnterTime ), que es tiempo constante (al menos para los números delimitados), o O (1) .

Worst = CheckTime + EnterTime

A continuación, si la distribución de los números es aleatoria, el costo promedio disminuye cuanto más números tenga. Por ejemplo, la posibilidad de que ingrese el número 101 en el conjunto máximo es 100/101, la probabilidad del número 1000 sería 1/10, y la posibilidad del número n sería 100 / n. Por lo tanto, nuestra ecuación para el costo promedio será:

Average = CheckTime + EnterTime / n

Por lo tanto, cuando n se acerca al infinito, solo CheckTime es importante:

Average = CheckTime

Si los números están enlazados, CheckTime es constante, y por lo tanto es O (1) tiempo.

Si los números no están vinculados, el tiempo de verificación aumentará con más números. Teóricamente, esto se debe a que si el número más pequeño en el conjunto máximo es lo suficientemente grande, su tiempo de verificación será mayor porque tendrá que considerar más bits. Eso hace que parezca que será un poco más alto que el tiempo constante. Sin embargo, también podría argumentar que la probabilidad de que el próximo número esté en el conjunto más alto se aproxima a cero a medida que n se acerca al infinito y, por lo tanto, la posibilidad de que tenga que considerar más bits también se acerca a 0, lo que sería un argumento para O (1) tiempo.

No estoy seguro, pero mi instinto dice que es O (log (log (n))) tiempo. Esto se debe a que la probabilidad de que aumente el número más bajo es logarítmica, y la posibilidad de que la cantidad de bits que debe considerar para cada verificación también sea logarítmica. Estoy interesado en que otras personas tomen esto, porque no estoy realmente seguro ...

este es fácil si sabes Árboles de montón binarios . Los montones binarios admiten la inserción en tiempo constante promedio, O (1). Y te da acceso fácil a los primeros x elementos.

Si, por la pregunta, el entrevistador realmente quería preguntar "podemos asegurarnos de que cada número entrante se procese en tiempo constante", entonces, como muchos ya han señalado (por ejemplo, consulte la respuesta de @ duedl0r), la solución de su amigo ya es O (1 ), y lo sería incluso si hubiera usado una lista sin clasificar, o haya usado una clasificación de burbuja, o cualquier otra cosa. En este caso, la pregunta no tiene mucho sentido, a menos que sea una pregunta difícil o si la recuerdas mal.

Supongo que la pregunta del entrevistador fue significativa, que no estaba preguntando cómo hacer algo para ser O (1), lo cual es muy obvio.

Debido a que la complejidad del algoritmo de cuestionamiento solo tiene sentido cuando el tamaño de la entrada crece indefinidamente, y la única entrada que puede crecer aquí es 100: el tamaño de la lista; Supongo que la verdadera pregunta era "¿podemos asegurarnos de que obtengamos Top N gastando O (1) tiempo por número (no O (N) como en la solución de su amigo), es posible?".

Lo primero que se me viene a la mente es la clasificación, que comprará una complejidad de O (1) tiempo por número para el problema Top-N por el precio de usar el espacio O (m), donde m es la longitud del rango de números entrantes. Así que sí, es posible.

Use una cola de prioridad mínima implementada con un Fibonacci Heap , que tiene un tiempo de inserción constante:

1. Insert first 100 elements into PQ
2. loop forever
       n = getNextNumber();
       if n > PQ.findMin() then
           PQ.deleteMin()
           PQ.insert(n)

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:

1. 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.

2. Toma un nuevo número x de la secuencia aleatoria.

3. ¿Es más alto que el último número más bajo registrado? Sí = > Paso 4, No = > Paso 2

4. 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)

5. 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)

6. Tome el número más bajo que he registrado (y elimínelo del hash / lista).

7. 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)

8. 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.

¿Podemos suponer que los números son de un tipo de datos fijo, como Integer? Si es así, entonces mantenga una cuenta de cada número que se agrega. Esta es una operación O (1).

1. Declare una matriz con tantos elementos como haya números posibles:
2. Lea cada número a medida que se transmite.
3. Tally el número. Ignóralo si ese número ya se ha contabilizado 100 veces, ya que nunca lo necesitarás. Esto evita que los desbordamientos se acumulen un número infinito de veces.
4. Repita desde el paso 2.

Código VB.Net:

Const Capacity As Integer = 100

Dim Tally(Integer.MaxValue) As Integer ' Assume all elements = 0
Do
    Value = ReadValue()
    If Tally(Value) < Capacity Then Tally(Value) += 1
Loop

Cuando devuelva la lista, puede tomar todo el tiempo que desee. Simplemente itere desde el final de la lista y cree una nueva lista de los 100 valores más altos registrados. Esta es una operación O (n), pero eso es irrelevante.

Dim List(Capacity) As Integer
Dim ListCount As Integer = 0
Dim Value As Integer = Tally.Length - 1
Dim ValueCount As Integer = 0
Do Until ListCount = List.Length OrElse Value < 0
    If Tally(Value) > ValueCount Then
        List(ListCount) = Value
        ValueCount += 1
        ListCount += 1
    Else
        Value -= 1
        ValueCount = 0
    End If
Loop
Return List

Editar: De hecho, realmente no importa si se trata de un tipo de datos fijo. Dado que no hay límites impuestos en el consumo de memoria (o disco duro), podría hacer que esto funcione para cualquier rango de enteros positivos.

Cien números se almacenan fácilmente en una matriz, tamaño 100. Cualquier árbol, lista o conjunto es una exageración, dada la tarea en cuestión.

Si el número entrante es más alto que el más bajo (= último) en la matriz, ejecute sobre todas las entradas. Una vez que encuentre el primero que es más pequeño que su nuevo número (puede usar búsquedas sofisticadas para hacerlo), ejecute el resto de la matriz, presionando cada entrada "hacia abajo" en una.

Ya que mantiene la lista ordenada desde el principio, no necesita ejecutar ningún algoritmo de clasificación. Esto es O (1).

Podrías usar un Binary Max-Heap. Tendría que hacer un seguimiento de un puntero al nodo mínimo (que podría ser desconocido / nulo).

Empiezas insertando los primeros 100 números en el montón. El máximo estará en la parte superior. Una vez hecho esto, siempre mantendrás 100 números allí.

Luego, cuando obtengas un nuevo número:

if(minimumNode == null)
{
    minimumNode = findMinimumNode();
}
if(newNumber > minimumNode.Value)
{
    heap.Remove(minimumNode);
    minimumNode = null;
    heap.Insert(newNumber);
}

Desafortunadamente, findMinimumNode es O (n), y usted incurre en ese costo una vez por inserción (pero no durante la inserción :). La eliminación del nodo mínimo y la inserción del nuevo nodo son, en promedio, O (1) porque tenderán hacia la parte inferior del montón.

Yendo a la inversa con un min-Heap binario, el mínimo está en la parte superior, lo que es excelente para encontrar el mínimo para comparación, pero apesta cuando tienes que reemplazar el mínimo con un nuevo número que es > min. Esto se debe a que debe eliminar el nodo mínimo (siempre O (logN)) y luego insertar el nuevo nodo (promedio O (1)). Por lo tanto, todavía tienes O (logN), que es mejor que Max-Heap, pero no O (1).

Por supuesto, si N es constante, entonces siempre tienes O (1). :)