Иногда, на алгоритмических секциях дают задачки с хитрыми формулировками, иногда — задачи, для которых нужно придумать хитрый алгоритм.
Но, время от времени, попадаются задачи где нужно просто имплементировать ту или иную структуру данных. Конечно же, обычно интервьюер таким образом пытается понять, знаете ли вы какую-нибудь хитрую (или не очень) структуру данных, которую так хорошо знает он сам, и сумеете ли вы реализовать ее с закрытыми глазами.
Конечно же, я большой противник таких подходов — структур данных превиликое множество, а знать их и помнить все невозможно.
Что делать, если вам попалась такая задача и вы не знаете что от вас просят? Вспомните, что софт скилы не менее важны чем харды и попросите интервьюера рассказать, какую проблему должна решать структура, какие методы должны быть имплементированы, какие требование к скорости/памяти предъявляются и так далее.
Если интервьер адекватный, он обязательно поможет вам понять, что от вас требуется.
Сегодняшняя наша задача — имплементировать префиксное дерево.
Сложность: 🟠 Cредняя
ℹ️ Описание
Необходимо написать реализацию структуры данных «Префиксное дерево». Данная структура должна имплементировать следующие методы:
▶️ Insert(word string) —сохранение слова в дерево
▶️ Search(word string) bool —проверка наличия слова в дереве. Важно помнить, что данный метод должен отвечать true только в случае, если найдено конечное слово (а не префикс)
▶️ StartsWith(prefix string) bool — проверка наличия префикса в дереве. В отличии от предыдущего метода true вернется как в случае нахождения полноценного слова, так и при наличии префикса.
⚠️ Ограничения
🔹Длина одного слова не превышает 2000 символов
🔹Слова могут состоять только из латинских букв в нижнем регистре
🔹Суммарное максимальное кол-во вызовов всех методов - 30000
Пример
trie := Constructor()
trie.insert("apple")
trie.search("apple") // return True
trie.search("app") // return False
trie.startsWith("app") // return True
trie.insert("app")
trie.search("app") // return True
✅ Решение
Суть префиксного дерева — слово раскладывается посимвольно. Каждый символ будет нодой дерева. Связи между нодами соответствуют последовательности симолов в строке.
Таким образом, слово «apple» должно в нашей структуре превратиться в «ветку» a -> p -> p -> l -> e.
Для того, чтобы реализовать дерево, нам нужно описать структуру ноды. В нашем случае она будет очень простой.
type Trie struct {
children map[rune]*Trie
isFullWord bool
}
children — набор дочерних нод.
isFullWord — признак того, является ли текущая нода конечной буквой слова (нам нужен этот флаг, так как одно слово может полностью являться префиксом для более длинного слова).
Более подробное описание структуры можно найти по ссылке.
Для реализации метода вставки нам потребуется вспомогательный рекурсивный метод. На каждой итерации рекурсии мы будем отрезать по одной букве слева, превращая ее в префиксную ноду. В ноде последней буквы мы проставим флаг isFullWord в true.
Методы Search и StartsWith отличаются только тем, что в последней найденной ноде нам нужно проверить флаг isFullWord (для Search он должен оказаться true, а для StartsWith значение флага не имеет никакого значения). Поэтому для реализации обоих методов нам понадобится один вспомогательный метод traverse, который сможет рекурсивно обходить дерево вглубь. В этом методе мы будем отрезать по одной букве слева и искать ее в мапе children текущей ноды. Если такой ключ существует — переходить к найденной дочерней ноде.
Посмотреть подробное решение в блоге
🅾️ Оценка сложности
По времени
Функции Insert, Search и StartsWith используют рекурсивные вспомогательные функции insert и traverse. У обеих функций глубина рекурсии равна длине префикса.
Таким образом, все 3 функции имеют сложность O(n), где n - длина префикса.
По памяти
Для работы функций не используются промежуточные структуры, зависящие от длины префикса. Сложность по памяти O(1).
#tries #medium