estrutura de dados para um sistema de arquivos - entrevista - algoritmo, estruturas de dados

Encontrei as seguintes perguntas da entrevista online. Com base no meu entendimento, foi solicitado que você projetasse uma estrutura de dados para simular o sistema de arquivos. Alguém pode me dar algumas dicas?

// 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

}

Respostas:

Acho que a melhor estrutura a ser usada para esse mapeamento é um Trie ou ainda melhor sua versão compactada - uma árvore Patricia (a.k.a árvore de raiz)A ideia é a seguinte - ambas as estruturas armazenam prefixos de palavras do dicionário. Quando um usuário consulta um determinado caminho, você atravessa a estrutura (seja uma árvore trie ou raiz) de acordo com a string de consulta. Depois disso, você percorre a subárvore sob o nó onde acabou e imprime todos os controladores associados aos nós ali.