Un rompecabezas en la estructura de datos

Question

Me enfrenté a esta pregunta puzzle [related to data structure] en una competición de codificación.

Hay un planeta de árboles (árboles reales, no estructura de datos de árbol !!). Tiene miles de millones o incluso billones de árboles. El rey ordena encontrar la mediana de las edades (en años y números enteros) de todos los árboles que usan datación por carbono. (Method does not matter.) Nota: La mediana es el "número medio" en una lista ordenada de números.

Restricciones:
1. El árbol más antiguo se sabe que es de 2000 años de antigüedad.
2. Tienen una sola máquina que puede almacenar enteros en el rango de -infinito a + infinito.
3. Pero la cantidad de dichos enteros que se pueden almacenar en la memoria a la vez es de 1 millón.

así que, una vez que almacene 1 millón de enteros para almacenar el siguiente, debe eliminar uno ya almacenado.
De alguna manera tienen que hacer un seguimiento de la mediana a medida que continúan contando las edades de los árboles.
¿Cómo pueden hacer esto?

Mi enfoque
Uso de una variante de tipo externo para ordenar las edades en trozos & los escriben en el archivo.
Aplicar combinación de k-way [para los fragmentos].
El problema con el enfoque anterior es que necesita dos escaneos del archivo.

No puedo pensar en otro enfoque que utiliza la información The oldest tree is known to be 2000 years old.
¿No podemos tomar un count array [as range of ages of tree is fixed]?

Quiero saber ¿Hay algún otro enfoque?
¿Existe algún método en el que no necesitamos almacenar los datos en el archivo? [where only main memory is sufficient?]

Answer 1

Usted puede hacer esto mediante el almacenamiento de sólo 2.001 enteros. Crear una matriz de diferentes edades posibles

ages[2001] // [0..2000] 

si se incluye un árbol

ages[thisAge]++ 

luego calcular la mediana es trivial. Pareces haber llegado a esta solución en el segundo enfoque que mencionas, pero luego dices . Quiero saber si hay un mejor enfoque.

¿Existe algún método en el que no hay que almacenar los datos en el archivo ? [En el que sólo la memoria principal es suficiente?]

No undertstand por qué preguntar si hay existe cualquier método donde la memoria principal es suficiente. ¿No encaja una matriz del número entero de 2001 en la memoria principal?

Utilizando el enfoque anterior, puede completar su conjunto de recuentos, y luego calcular la mediana repitiendo los conteos, manteniendo una suma total sobre la marcha. Cuando su suma alcanza la mitad del número total de árboles, tiene la mediana. Esto requiere un pase a través de todos los árboles para contar, más un pase a través de la matriz de conteo de algún número < = 2001. Entonces este es O (n). Podrías, en cambio, hacer un seguimiento de la mediana con esta matriz sobre la marcha, pero en realidad no mejoraría la solución.

Answer 2

El enfoque recomendado (una serie de 2001 años) es O (n), con una operación rápida por árbol, por lo que es óptimo.

Bueno, casi óptimo. En algún momento durante el recuento, la cantidad de árboles restantes será insuficiente para cambiar el resultado. Por ejemplo, si cuento la mitad + 1 de los árboles, y todos tienen exactamente 100 años, entonces tengo mi respuesta: 100 años.

Pero si los árboles están bien dispersos en edad, entonces la cantidad de árboles requeridos será cercana al número total.