stampa tutti i file in una determinata cartella e sottocartelle senza usare la ricorsione/pila

Question

Recentemente ho avuto un colloquio con una società rispettabile per la posizione di Software Developer e questo era una delle domande ha chiesto:

"Dato i seguenti metodi:

List subDirectories(String directoryName){ ... }; 
List filesInDirectory(String directoryName) { ... }; 

Come suggeriscono i nomi, il primo metodo restituisce un elenco di nomi di immediati sotto-directory nella directory di input ('directoryName') e il secondo metodo restituisce un elenco dei nomi di tutti i file in questa cartella

Stampa a tutti i file nel file system. "

Ci ho pensato e ho dato all'intervista una soluzione ricorsiva piuttosto ovvia. Poi mi ha detto di farlo senza ricorsione. Dal momento che la ricorsione usa lo stack delle chiamate, le ho detto che userò uno stack ausiliario, al punto in cui mi ha detto di non usare neanche uno stack. Sfortunatamente, non sono riuscito a trovare una soluzione. Ho chiesto come si può fare senza ricorsione/pila, ma lei non lo direbbe.

Come si può fare?

Answer 1

si desidera utilizzare una coda e un algoritmo di BFS.

Credo che alcune pseudo-codice sarebbe bello:

files = filesInDirectory("/") 
foreach (file in files) { 
    fileQ.append(file) 
} 

dirQ = subDirectories("/") 
while (dirQ != empty) { 
    dir = dirQ.pop 
    files = filesInDirectory(dir) 
    foreach (file in files) { 
     fileQ.append(file) 
    } 
    dirQ.append(subDirectories(dir)) 
} 

while (fileQ != empty) { 
    print fileQ.pop 
} 

Answer 2

Se ho capito bene, le sottodirectory immediate sono solo le directory in quella cartella. Voglio dire, se I = abbiamo questi tre percorsi /home/user, /home/config e /home/user/u001, possiamo dire che sia user e config sono sottodirectory immediati di /home/, ma u001 non è. Lo stesso vale se user e u001 sono file (user è immediato mentre u001 no).

Quindi non è necessario ricorrere a ricorsione o stack per restituire un elenco di sottodirectory o file immediati.

EDIT: Ho pensato che il PO ha voluto attuare le subDirectories() e filesInDirectories() funzioni.

Quindi, si può fare qualcosa di simile per stampare tutti i file (tipo di pseudocodice):

List subd = subDirectories(current_dir); 
List files = filesInDirectories(current_dir); 

foreach (file in files) { 
    print file.name(); 
} 

while (!subd.empty()) { 
    dir = subd.pop(); 

    files = filesInDirectory(dir.name()); 

    foreach (file in files) { 
     print file.name(); 
    } 

    subd.append(subDirectories(dir.path())); 
} 

Answer 3

Penso che quello che @lqs suggerisce è davvero una risposta accettabile che lei potrebbe essere stato alla ricerca di: memorizzare il percorso completo in una variabile, e aggiungi il nome della directory ad esso se inserisci una sottodirectory e togli l'ultimo nome della directory quando lo lasci. In questo modo, il tuo percorso completo funge da puntatore a dove ti trovi attualmente nel file system.

Poiché il percorso completo viene sempre modificato alla fine, il percorso completo si comporta (non a sorpresa) come stack.

domande di intervista a parte, credo che sarei ancora scegliere una vera pila sopra la manipolazione di stringhe anche se ...