Хочу работать в Google: Большой разбор маленькой задачи (part 1)
Когда я учу гуглеров проводить интервью, я часто говорю, что можно взять одну простую задачу и просто постепенно ее углублять. Даже элементарный вопрос можно раскопать так, что целого интервью может не хватить. Так что давайте сегодня покопаем в глубину и заодно посмотрим, как может выгляить один из вариантов интервью в Google.
Задача
Задача формулируется весьма просто: “Найдите самый частый символ в строке”.
В плюс кандидату уйдет, если он уточнит строка Unicode или ASCII. А если он спросит есть ли в строках какая-то закономерность (например – это слова, которые в среднем короткие), то это второй плюс.
Часть 1a: Простые ASCII строки, однопоточность.
Давайте начнем с простой задачи, и предположим что у нас простая строка, один компьютер, и один поток, который все это обрабатывает.
Вопросы, которые бы хорошо задать в этом месте – есть ли какие-то ограничения для строк? Какие-то закономерности? Является ли наша функция частью какого-то проекта, который делает что-то специальное (например, обрабатывает слова в английском языке -> наши строки будут короткие, разрешенных символов намного меньше, и мы уже довольно много знаем про свойства языка что касается распределения букв итп.).
Допустим, что закономерностей нет. Мы просто рассматриваем ASCII строки длиной до 10000 символов. В этом случае возможны 3 подхода:
- Неэффективный 1. Мы знаем, что в строке 256 разных символов. Идем по строке и считаем количество каждого из них: ‘a’ -> 10 раз, ‘b’->20 раз… В процессе помним максимум, и меняем его если мы нашли новый максимум.
Надеюсь, не надо объяснять, что это плохое решение. Сложность, кстати, линейная – O(256*N)~O(N). Но решение все равно плохое. - Неэффективный 2. Для каждого символа в строке считаем сколько раз он встречается. Сложность O(N^2).
- Эффективный. Для подсчета символов есть три варианта – array of 256 symbols, hash table, map. Сложность алгоритма в этом случае O(N), O(N), O(N logN) соответственно.
a) Последнее потому, что map реализован как красно-черное дерево, где все операции логарифмические. В С++ есть unordered_map, который и нужно использовать в этом случае.
b) Если вас просят оценить размер хеш-таблицы, то учтите, что туда входят не только значения (size=256*(char_size+int_size)), но и size overhead для хранения самой структуры данных. В случае unordered_map, судя по всему, overhead довольно большой. В нашем случае это, впрочем, неважно, так как значений у нас мало, и байт туда, байт сюда роли не играет :). Но знать, что overhead присутствует и примерно представлять его порядок (10%? 100%? 1000%?)- важно! По моему опыту overhead обычно составляет 20-50%, в зависимости от данных и реализации контейнера. - Странный. Строку можно отсортировать за O(N log N). В отсотрированной строке найти самый частый символ можно за один проход.
a) Тут можно спросить: в каких случаях это решение вообще имеет смысл? Думаю, что правильный ответ – это если у нас мало памяти и мы не можем хранить хеш таблицу в памяти. Таблица у нас мега-маленькая, поэтому это очень странная ситуация.
b) Еще тут важно знать сортировочный алгоритм, который работает за O(N log N), без дополнительной памяти. Я часто задаю этот вопрос к другой задаче, и большинство кандидатов говорит Quick Sort. Это технически неправильный ответ, так как QS в худшем случае O(N^2). Иногда называют Merge Sort, но для него нужна дополнительная память. Один из алгоритмов, подходящий под наши требования – Heap Sort.
Важно не забыть, что в ASCII 256 символов, а не 26, как в английском алфавите.
При использовании хеш таблицы нужно как-то найти максимум когда таблица уже составлена. Тут есть два варианта:
- Проходим всю таблицу и находим символ с максимальным счетчиком Удостоверьтесь, что вы знаете как написать этот итератор на вашем языке, иначе вам грозит epic fail на интервью.
- В процессе заполнения таблицы мы всегда обновляем порядок счетчиков. Это можно сделать если в таблице хранить указатели на связной список для счетчика, а не сам счетчик. Максимальный символ всегда находится в начале. Когда счетчик какого-то символа меняется, надо проверить “соседа” из списка, стоящего впереди, и если новое значение счетчика стало больше, то просто поменять узлы местами.
Кстати, вышеописанная идея вообще очень полезна. Она применима ко многим задачам, например к дизайну эффективного LRU cache. Я очень советую разобраться в этом подходе во время подготовки к интервью.
Часть 1b: Короткие ASCII строки, однопоточность.
Теперь допустим, что мы знаем, что все наши строки короткие, максимум 10 символов. В этом случае может иметь смысл воспользоваться алгоритмом “Неэффективный 2“. Дело в том, что инициализация структур данных – массивов или хеш таблиц – требует определенных ресурсов. И если мы разанее знаем, что объем данных маленький, может иметь смысл этого не делать.
Часть 1c: Unicode, однопоточность.
Для начала я советую ознакомиться с этой статьей.
Если вас спрашивают про Unicode, то важно понимать, что Unicode бывает разный. Есть UTF-8, UTF-16 и UTF-32, в зависимости от количество бит. Вам нужно знать сколько бит занимают символы чтобы правильно оценить размер памяти, которая вам потребуется для хранения данных.
Если в решении 1a вы пользовались массивом, то теперь проблема в том, что алфавит намного больше, и создавать массив размером 2^16 (а то и 2^32) для всех возможных значений – не самое разумное решение. В этом случае можно для начала посчитать сколько у нас разных символов (используя unordered_set, не обычный set, который увеличивает сложность алгоритма!). И после этого создать массив нужного размера.
В случае с хеш таблицей решение не меняется. Единственный момент – размер хеш таблицы может сильно увеличиться, если символы, скажем, 32 бит (а не 8, как для ASCII). Тут может иметь смысл задуматься о подходе с сортировкой, если память надо экономить.
Кстати, удостоверьтесь, что вы знаете, как работать с Unicode в вашем языке программирования. Это несложно, но нужно это знать.
Продолжение следует… В следующих сериях нас ждет многотопочный и распределенный вариант этой же задачи.
