Подборка полезных алгоритмов для собеседований: задачи на строки

В этом материале мы решили разобрать алгоритмы, которые часто встречаются на собеседованиях. В качестве инструмента реализации мы использовали Java.

Стоит сразу заметить, что нашей задачей является не подробное описание алгоритмов или их реализация, а перечисление необходимых основ и указание общего направления, в котором следует двигаться. По многим темам мы привели ссылки на источники полезной информации, с которыми и рекомендуем ознакомиться.

Как работать со строками

В Java строка как класс представляет из себя массив символов и ещё несколько полей и методов. Подробнее об этом можно прочитать в нашей статье. Мы выделили несколько самых востребованных методов для работы со строками:

			toCharArray() // Возвращает массив символов строки
charAt(int x) // Возвращает символ, находящийся на указанной позиции
length() // Возвращает длину строки. Обратите внимание, это не поле, в отличие от массива
substring(int beginIndex) // Возвращает подстроку от указанного индекса и до конца строки
substring(int beginIndex, int endIndex) // Возвращает подстроку между указанными индексами
Integer.valueOf() // Переводит строку в число
String.valueOf() // Переводит число в строку, аналогично toString()
		

Понять природу строк не очень сложно, особенно, если, не придавать особого значения кодировкам или различиям между кодовой точкой и символом. Несмотря на это, вопросы, связанные с их обработкой, нередко влекут за собой реализацию сложных алгоритмов.

Обратная польская нотация

Обратная польская, или постфиксная, нотация широко применяется в строковых калькуляторах, где выражение полностью обрабатывается после его ввода.

Постфиксная нотация, в отличие от инфиксной, что привычна для нас, требует такую запись арифметического выражения, когда операнды идут перед знаком операции. Не стоит забывать и о различиях в записи левоассоциативных и правоассоциативных операций. Например, 1 2 + в инфиксной нотации выглядит как 1 + 2, 1 2 + 3 + — как 1 + 2 + 3, 1 2 3 ^ ^ — как 1 ^ 2 ^ 3.

Для перевода в постфиксную нотацию необходимо знание такой структуры, как стек. Примеры реализации обратной польской записи можно найти на Wikiversity, а описание алгоритма на английском языке можно прочесть в статье на programcreek.com.

Нахождение максимальной подстроки-палиндрома

Палиндромом — строка, которая читается одинаково в обе стороны, т.е. такая строка S длины n, что S[i] = S[n - 1 - i], где i принимает значения от 0 до n - 1.

Решение «в лоб»

Работает, очевидно, за O(N³). Естественно, такой подход не является оптимальным.

С использованием динамического программирования

Подробнее о динамическом программировании можно прочесть в этой статье. В таком случае, временная сложность составляет O(N²), требуется O(1) памяти. Если вы не знакомы с понятием «сложность алгоритма», настоятельно рекомендуем вначале изучить статью по этой теме. Идея алгоритма заключается в работе с массивом, где в позиции с индексом i, записано, какой максимальной длины есть палиндром с центром в i. Алгоритм решения задачи со схожей идеей можно найти на Wikibooks, а реализация именно такого решения есть на сайте programcreek.com, но на английском языке.

Быстрые алгоритмы

Быстрыми алгоритмами (за O(N)) решения этой задачи являются алгоритм Манакера, а также алгоритмы на суффиксном дереве с использованием быстрого алгоритма поиска LCA. Однако же эти алгоритмы являются довольно трудными для понимания, а подобная задача нехарактерна для больших объемов данных, так что для реального собеседования можно обойтись и более простыми вариантами.

Разбитие слова на словарные части

Задача: дано слово и словарь. Необходимо выяснить, существует ли способ разбить это слово на несколько частей, каждая из которых входит в словарь.

Наивный алгоритм

Мы рекомендуем отказаться от данного подхода в силу высокой сложности — O(2ⁿ).

Динамическое программирование

Сложность составляет O(N × L), где L — длина словаря. Требуется O(N) памяти. Пример такой реализации, конечно же, есть на programcreek.com и он, как вы догадываетесь, на английском языке.

Работа с регулярными выражениями

Регулярные выражения — гибкий инструмент поиска символьных последовательностей в строках. В большинстве языков программирования, если не во всех, существуют методы для работы с регулярными выражениями. В Java, например, это пакет java.util.regex. Единственное, что нужно программисту — научиться использовать эти методы. Для глубокого изучения темы можно почитать теорию конечных автоматов, на которых построены регулярные выражения, а познакомиться с «регулярками» можно в нашем вводном материале.

Словарная лестница

Задача: даны два слова и словарь. Необходимо найти алгоритм превращения одного слова в другое, меняя за один шаг одну букву, причём каждое новое слово должно быть в словаре. Например:

			// Входные данные:
"hit"; "cog"; ["hot","dot","dog","lot","log"]
// Вариант получаемой в результате цепочки:
"hit" -> "hot" -> "dot" -> "dog" -> "cog"
		

Поиск в глубину

Начинать перебирать все варианты и спускаться ниже — не самый лучший способ. Такой метод называется «поиск в глубину». Чтобы такой алгоритм действительно давал кратчайший путь, а не первый в лексико-графическом порядке, потребуется O(N!), где N — длина словаря.

Поиск в ширину

Данный метод является оптимальным решением. Его реализация приведена на уже хорошо знакомом нам англоязычном сайте programcreek.com. Здесь используются две очереди и, собственно, сам алгоритм поиска в ширину.

Перевод строки в число

В общем-то, этот алгоритм тоже реализован во многих языках. Тем не менее, нередко есть смысл писать собственный парсер, чтобы, например, считывать ввод из потоков, что увеличит быстродействие. Если вы решили так поступить, не забудьте учесть следующие моменты:

• строка может быть пустой, а значит имеет смысл вернуть 0;
• в начале строки могут быть пробелы;
• у числа может быть знак «минус»;
• число может быть в вещественной форме;
• полученное число может выходить за границы типа.

Корректность скобочной последовательности

Задача: дана строка, в которой используются скобки разного типа. Необходимо проверить, является ли такая скобочная последовательность правильной. Неправильным будет, например, такое сочетание: ({)}.

В общем-то, здесь мы и применим наивный алгоритм, работающий за O(N): например, с использованием стека, куда помещаются встреченные скобки. Такое решение будет стоить O(N) памяти, но можно решить и за O(1) памяти, если завести счетчики для каждого типа скобок. В Java можно реализовать решение этой задачи используя Hashmap, как говорится на programcreek.com.

Проверка на палиндромность

При выполнении этой задачи нужно учитывать только буквы и цифры, но не учитывать регистр, иными словами, фраза «А роза упала на лапу Азора» является палиндромом.

Замечание Если этот вопрос попадется вам на собеседовании, лучше спросить, чем считать пустую строку. Мы считаем ее палиндромом.

На самом деле, решение этой задачи не очень сложное имы предлагаем аж два варианта.

Сначала обработать строку

Для начала можно пройтись по строке, оставив только буквы и цифры, чего требует условие и лишь затем наивным способом проверить, является ли эта строка палиндромом, что потребует O(N) времени.

Сразу проверить строку

Другой вариант — проверка строки без обработки. В этом случае мы заводим два указателя, инициализируемые началом и концом строки. Далее они движутся по строке, смещаясь к центру, пока не станут указывать на букву или цифру. Затем просто проверяем их на равенство. Продолжаем выполнение, пока левый указатель не станет больше правого. Очевидно, что это те же O(N), но здесь меньше константа.

Оба эти решения приведены на programcreek.com.

Длиннейшая подстрока без повторяющихся символов

На programcreek.com приведены два решения: наивное, за O(N²) времени и O(1) дополнительной памяти, а также с использованием HashMap. В Java обращение к HashMap составляет O(1), поэтому второе решение занимает O(N) времени, но требует больше памяти.

Однако, при реализации решения этой задачи на других языках программирования, где HashMap не является таким эффективным, будет необходимо обратиться к понятию z-функции. Тогда решение займет O(N) памяти (меньше, чем для HashMap) и O(N) времени.

Вниманию любителей решать задачки также предлагаем подборку 28 сайтов, где можно порешать задачи по программированию.