Trie vs HashMap, какой использовать - Вопрос интервью - PullRequest
Новая
       29

Trie vs HashMap, какой использовать - Вопрос интервью

0 голосов
/ 09 февраля 2019

Задача - Учитывая коллекцию текстовых файлов (предположим, список файлов), вам необходимо спроектировать структуру данных.Временная сложность для построения структуры данных не важна, единственное, что важно, это временная сложность (время доступа) для следующих трех методов, дающих начало реализации структуры данных:

find(String word) - возвращаетвсе файлы, содержащие данное слово.

findAnd(String word1, String word2) - возвращает все файлы, содержащие оба слова.

findOr(String word1, String word2) - возвращает все файлы, содержащие хотя бы одно из слов.

У меня трудности с выбором между двумя подходами:

Первый подход

Просто вставьте все слова в hashMap<string word, list containsFiles>, и каждыйслово (ключ) получит соответствующее значение (список файлов).При доступе к структуре данных, после получения списка (в среднем за O (1) раз) все, что мне нужно сделать, это сгенерировать правильный ответ по имени метода и вернуть его.

Второй подход

Используйте hashMap<Character ch, Item item>, где сам элемент содержит hashMap 

class Item{
   hashMap<Character ch, Item item> map;
   list<file> containsFiles;
}
//assume file class looks as follow
class File{
   String name;
   Date creationDate;
   File file
}

Другими словами, сортировка типа Trie с использованием HashMap.И также здесь, после получения списка (в O (L), где L - длина ключа), все, что мне нужно сделать, это сгенерировать правильный ответ по имени метода и вернуть его.

Проектирование -Я склонен выбирать второй подход, потому что мне не нравится идея отображения потенциально большого количества слов в список файлов, а также мне не нравится зависимость между моим дизайном и реализацией Java hashMap (как столкновение в моем случае повлияет на производительность).

Пожалуйста, скажите мне, каков правильный подход между двумя аспектами сложности времени и пространства и ПОЧЕМУ?- Мне очень важно понять .Есть ли лучшее решение, которое вы бы предложили?

...