struttura dati per un file system - intervista - algoritmo, strutture dati

Ho incontrato le seguenti domande di intervista online. Sulla base della mia comprensione, ti è stato chiesto di progettare una struttura dati per simulare il file system. Qualcuno può darmi qualche suggerimento?

// addMapping("/foo/bar/x", "XController")
// addMapping("/foo/bar/z", "ZController")
// addMapping("/foo/baz", "BazController");

//getMapping("/foo/bar/x") -> ["XController"]
//getMapping("/foo/bar") -> ["XController", "ZController"]


public void addMapping(String path, String destination) {
//candidate TODO

}

public List<String> getMapping(String path) {
//candidate TODO

}

risposte:

Penso che la migliore struttura da usare per questa mappatura sia a prova o ancora meglio la sua versione compressa - un albero di Patricia (a.k.a albero radix). L'idea è la seguente: entrambe le strutture memorizzano i prefissi delle parole del dizionario. Quando un utente esegue una query per un determinato percorso, si attraversa la struttura (che si tratti di un albero trie o radix) in base alla stringa di query. Dopo di ciò, si cammina sopra la sottostruttura sotto il nodo in cui si finisce e si stampano tutti i controller associati ai nodi.