Что делать за 1 неделю до Google Onsite?

Личный опыт Google

Коллеги, что посоветуете делать за неделю до назначенного телефонного интервью (или onsite) в Google. Вот осталась неделя, и я думаю, стоит ли пробежаться по старым задачам? Или может надо быстренько проглядеть как можно больше новых на то, вижу ли я идею? Или тупо продолжать решать в том же темпе? Или может дать мозгам успокоиться и сильно не перенапрягаться? Что посоветуете? Чтобы не плодить лишних сообщений, заранее всем СПАСИБО за советы)

John: я работал вширь — смотрел алгоритмы и подходы, вспоминал где у меня были самые большие проблемы и пробелы и в спешке закрывал, но за сутки до собеседования закрыл все, включил иксбокс и просто отдыхал. Помогло.

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

• Смотри на природу данных и на их вариативность: целые числа например легко сортируются за O(n) с помощью бакет-сорта или радикс-сорта. char элементы — тоже числа с фиксированной вариативностью, значит можно подумать о кэшировании с мемори комплексити О(1).
• Разделяй (и властвуй): можно ли сразу отсечь заведомо неподходящие элементы/результаты, например все операции со сложностью O(log(n)) построены на этом принципе — это бинарный поиск, мердж, квик сорты, и вообще все деревья и кучи. Кстати, не надо забывать, что для бинарного поиска данные уже должны быть отсортированы предварительно.
• Кэшируй: посмотри можно ли улучшить рантайм комплексити запоминая промежуточные результаты в какой-нибудь подходящей структуре данных — в дереве, куче, хэштейбле или даже тупо в массиве. Каждая структура имеет свои рантайм комплексити на добавление/чтение/удаление и их тоже надо учитывать. Сюда же динамическое программирование.
• Пробуй использовать более одного указателя за один проход: подходит для структур, где нет прямой адресации элементов: деревьев, списков
• Пробуй классику от математиков: сведём задачу к типовой задаче и будем решать её.
• Обход дерева/графа в глубину — используем стэк (рекурсия — не вариант, на большом объеме будет переполнение стэка), обход в ширину — используем очередь.
• Некоторые алгоритмы придется таки разобрать и запомнить: всякие там алгоритмы на графах — Дейкстры или Беллмана-Форда, для поиска кратчайшего расстояния между узлами, поиска связанных групп в графе, поиска циклов и т.п.

Как это было у меня и опыт Amazon

Но по моему опыту прохождения интервью в Амазон, сложные задачи спрашивают редко: за час решить задачу, проверить бихевиор и при этом записать всё в точности за кандидатом — это большая нагрузка на интервьюера. Поэтому задачи дают такие, чтобы подготовленный кандидат смог быстро в уме решить, рассказать о способах решения, успеть написать нормальный код на бумаге/доске и рассказать как он бы протестировал свой код, И! еще ответить на каверзные вопросы типа, что будешь делать если не успеваешь в дедлайн. Вообще в Амазоне больше всего оценивают именно 14 leadership принципов. Так что большое внимание стоит уделить soft-skills.

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

• прочитал и перерешал весь Cracking the coding interview,
• прошёл целиком курс по алгоритмам на corsera от Тима Рафгардена — именно из его лекций я почерпнул эти принципы подхода к решениям задач выше
• решал задачи на codility и позже на hackerrank — в принципе, не важно где решать, это тот же leetcode.

мок интервью я не делал никогда, а это стоило бы сделать, желательно с теми, кто работал(ет) в тех компаниях, чтобы они сказали на что именно обратить внимание…

сейчас у меня знакомые работают в Амазоне инжиниринг менеджерами, они говорят, что самое важное — 14 leadership принципов, нужно под каждый из принципов заготовить истории из своей практики о том, как вы проявили или придерживались этих принципов :)

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

Для System Design или когда строите систему на примере Youtube

• в построении систем работают абсолютно те же принципы, что и для решения задачек, только в большем масштабе: смотреть на природу данных, разделять (партишнинг, шардинг — привет хэштейбл!), кэширование и т.п.
• важно понимать, что нужно оптимизировать: вычислительную нагрузку по CPU или по IO — запись оптимизировать или чтение, или по пропускной способности сети, или минимизировать лейтенси, etc.
• понимать какие данные требуют ACID, а какие можно отдать на eventual consistency, помнить про CAP-теорему.

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

Например для ютуба нужно:

• загружать файлы
• хранить видео файлы
• стримить видосы
• хранить метаданные о видео
• хранить комменты.

Для аплоада и перекодирования видосов, нужно оптимизировать нагрузку по цпу, если возможно, то параллелить какими-нибудь stateless workers. Также сделать эту операцию асинхронной, поставив задачу в очередь — классический producer-consumer pattern.

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

Для просмотра важен bandwidth, а latency — не сильно, а для стриминга уже и то и то.

И так далее анализируешь фичи, делаешь предположение, что в каждой фиче важно и предлагаешь решение.

Кстати, забыл добавить в пост выше еще одну мысль: эдакий дуализм — уменьшить runtime complexity можно за счет увеличения memory complexity (пункт про кэширование) и наоборот. Иногда, кстати, и задачу могут дать из разряда “отсортируй файл с целыми числами размером 5 терабайт” с явным ограничением по памяти.

Jacky: Я придерживаюсь следующих принципов перед походом на онсайт: постараться походить побродить возле офиса заранее, чтобы территория для тебя была максимально знакомая и не вызывала стресса. Между раундами просись в туалет чтоб умыть лицо, тоже антистресс. На интервью я беру коробку шоколадок и ем по одной перед каждым раундом, это я взял у Вассермана. Перед первым интервью надо разогреться — порешай пару изи задачек, поговори с кем нибудь на английском. На интервью по возможности излучай позитив и уверенность, следи за языком тела. Перед интервью хорошо выспись