Un puzzle sulla struttura dati

Question

Ho affrontato questa domanda puzzle [related to data structure] in una competizione di codifica.

C'è un pianeta di alberi (alberi reali non struttura dati dell'albero !!). Ha miliardi o addirittura trilioni di alberi. Il re ordina di trovare la mediana delle età (in anni e interi) di tutti gli alberi usando la datazione al carbonio. (Method does not matter.) Nota: Mediana è il "numero centrale" in un elenco ordinato di numeri.

Vincoli:
1. L'albero più antico è conosciuto per essere 2000 anni fa.
2. Hanno una singola macchina che può memorizzare interi compresi nell'intervallo da -infinito a + infinito.
3. Ma il numero di tali numeri interi che possono essere memorizzati in memoria alla volta è 1 milione.

quindi, una volta memorizzato 1 milione di numeri interi per memorizzare quello successivo, è necessario eliminare uno già memorizzato.
Quindi in qualche modo devono tenere traccia della mediana mentre continuano a contare le età degli alberi.
Come possono fare questo?

Il mio approccio
Utilizzare una variante di tipo esterno per ordinare i secoli in blocchi & li scrivono nel file.
Applicare la fusione k-way [per i blocchi].
Il problema con l'approccio precedente è che è necessario eseguire due scansioni del file.

mi viene in mente un altro approccio che utilizza le informazioni The oldest tree is known to be 2000 years old.
non possiamo prendere un count array [as range of ages of tree is fixed]?

Voglio sapere c'è un approccio migliore?
Esiste alcun metodo in cui non abbiamo bisogno di memorizzare i dati nel file? [where only main memory is sufficient?]

Answer 1

Si può fare questo memorizzando solo 2001 numeri interi. Creare una matrice di età diverse possibili

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

quando si conta un albero

ages[thisAge]++ 

Quindi calcolando la mediana è banale. Sembra che tu abbia colto questa soluzione nel secondo approccio che hai citato, ma poi dici Voglio sapere se esiste un approccio migliore?

Esiste alcun metodo in cui non abbiamo bisogno di memorizzare i dati in file? [In cui solo la memoria principale è sufficiente?]

Non undertstand perché si chiede se non ci esiste un metodo in cui la memoria principale è sufficiente. Non un array di 2001 intero si adatta alla memoria principale?

Utilizzando l'approccio di cui sopra, è possibile compilare la serie di conteggi, quindi calcolare la mediana eseguendo il iterazione attraverso i conteggi, mantenendo una somma totale man mano che si procede. Quando la somma raggiunge la metà del numero totale di alberi, hai la mediana. Ciò richiede un passaggio attraverso tutti gli alberi per contare, oltre a un passaggio attraverso una parte della serie di numeri di alcuni numeri < = 2001. Quindi questo è O (n). Si potrebbe, invece, tenere traccia della mediana con questo array come si va, ma non migliorerebbe davvero la soluzione.

Answer 2

L'approccio consigliato (una serie di 2001 anni) è O (n), con un'operazione rapida per albero, quindi è ottimale.

Bene, quasi ottimale. Ad un certo punto durante il conteggio il numero di alberi rimanenti sarà insufficiente per cambiare il risultato. Per esempio, se conto la metà + 1 degli alberi, e tutti hanno esattamente 100 anni, allora ho la mia risposta: 100 anni.

Ma se gli alberi sono ben distribuiti per età, il numero di alberi richiesti sarà vicino al numero totale.