MongoDB Interview Experience для Backend-разработчика
Skype Раунд 1 (60 минут): преобразование данного массива в связанный список.
- https://www.geeksforgeeks.org/create-linked-list-from-a-given-array/
Я написал решение, которое вставляет элементы в конец связанного списка для каждого нового элемента и отслеживает последний узел, чтобы следующие вставки были O (1). Я пропустил некоторые крайние случаи, но в целом интервьюер остался доволен моим кодом.
Я точно не помню 2-й вопрос. Это выглядело как типичный вопрос конкурса кодирования с длинным описанием, но сутью вопроса были жадные алгоритмы, а решение было основано на сортировке.
Поскольку времени оставалось больше, интервьюер задавал общие технические вопросы. Он спросил, как и почему внедрение зависимостей и как оно обеспечивает инверсию управления.
Skype Round 2 (60 минут): реализация очереди с использованием массивов.
- https://www.geeksforgeeks.org/circular-queue-set-1-introduction-array-implementation/
Интервьюер изначально не упомянул циклические очереди, но я начал свое обсуждение непосредственно с циклических очередей, поскольку они более эффективны с точки зрения хранения. Но по мере того, как я продвигался вперед, я слишком долго застревал в крайних случаях обнаружения границ очереди, а также интервьюер немного запутался с операциями арифметического модуля, которые я использовал. Я полностью разбомбил этот вопрос, и моя уверенность просто умерла отсюда.
Интервьюер приостановил вопрос о кодировании и начал задавать общие технические вопросы. Он попросил меня объяснить теорему CAP с точки зрения непрофессионала и то, как она применима в распределенных системах. Затем он спросил меня о шаблонах проектирования, которые я знал и где я их использовал, на что я ответил singleton, builder и factory, но я не смог привести ему пример шаблона factory. Затем он задал мне вопросы о моей текущей работе. В конце интервьюер выразился очень позитивно и попросил меня освежить свои знания в области структур данных и алгоритмов, а также упомянул, что надеется вскоре увидеть меня на выездных раундах. Я был почти уверен, что дальше этого раунда не пройду.
К счастью, через несколько дней я получил электронное письмо от рекрутеров с подтверждением моей готовности к выездным раундам. Я провел немало времени, изучая структуры данных, алгоритмы и проектирование систем.
Выездной этап 1 (60 минут): как реплицировать данные в нескольких центрах обработки данных (DC)? Он упомянул, что это открытый вопрос, и попросил меня подумать о различных решениях.
Сначала я предложил использовать NoSQL-решения, такие как Cassandra и Dynamo DB, чтобы сохранить несколько узлов из разных контроллеров домена в кластере и поддерживать уровень согласованности так, как мы хотим. Затем он предложил мне не использовать встроенные решения, после чего я предложил запускать локальных потребителей в каждом контроллере домена, ожидающих синхронизации обновлений при записи исходного контроллера домена. Были еще дополнительные вопросы, но, поскольку у меня практически не было опыта работы с распределенными системами, я чувствовал, что не произвел здесь хорошего впечатления.
После этого он попросил меня сделать макет высокого уровня моего текущего проекта, и я смог дать ему четкую картину.
Очный раунд 2 (60 минут): Были заданы следующие вопросы:
Найдите длину пути от узла А к узлу В в бинарном дереве.
- https://www.geeksforgeeks.org/find-distance-between-two-nodes-of-a-binary-tree/
Я был знаком с такой проблемой. Суть проблемы заключается в том, чтобы найти наименьшего общего предка (LCA) двух узлов, а затем найти высоту узла A и узла B по узлу LCA. Сумма этих двух высот дает расстояние между двумя узлами. Меня попросили написать код на доске.
Дана матрица, содержащая только 1 и 0, найти наибольшую квадратную подматрицу, содержащую только 1.
- https://leetcode.com/problems/maximal-square/
Это задача динамического программирования средней сложности. Цель состоит в том, чтобы определить рекурсивное состояние DP[i][j], которое представляет собой размер наибольшей квадратной подматрицы, заканчивающейся на Matrix[i][j]. DP[i][j] может быть получен из его подзадач DP[i-1][j], DP[i-1][j-1] и DP[i][j-1] на основе содержания Матрица[i][j].
Раунд 3 на месте (60 минут): этот раунд был с техническим менеджером, и сначала у нас было несколько небольших бесед, и мы сразу перешли к вопросам:
- Задача с падением яиц: учитывая 2 яйца и 100-этажное здание, найдите минимальное количество сброшенных яиц, необходимое в худшем случае, чтобы найти первый этаж, на котором яйцо разобьется.
https://www.geeksforgeeks.org/puzzle-set-35-2-eggs-and-100-floors/
- https://leetcode.com/problems/egg-drop-with-2-eggs-and-n-floors/
Это очень сложный вопрос, и я сталкивался с этим вопросом раньше в предыдущем интервью во время моего размещения в кампусе, и я не мог ответить на него тогда. Моя уверенность немного упала, но я начал с грубой силы, когда я начал сбрасывать яйцо с первого этажа по одному этажу за раз, но это было очень неэффективно, так как в худшем случае требуется 100 падений и используется только 1 яйцо. Затем я подумал о бинарном поиске, где я начинаю с 50-го этажа и каждый раз продолжаю уменьшать вдвое, но это все еще было неэффективно, но лучше, чем грубая сила. Затем я попытался разделить этаж на блоки размеров B этажей, т.е. всего 100/B блоков. Я бы начал сбрасывать яйца с самого верхнего этажа в каждом блоке и продолжал бы так. Я написал математическую функцию в терминах B для наихудшего случая и продифференцировал ее, чтобы получить оптимальное значение B:
ПСЕВДОКОД:
F(B) = (100/B) + (B-1) Apply differentiation to get optimal B F"(B) = 0 (-100/B*B) + 1 - 0 = 0 B = 10 Worst case attempts = F(10) = (100/10) + (10-1) = 19 attempts
Я думал, что на этот раз у меня получилось, но, к моему удивлению, это все еще не был правильный ответ. Но интервьюер сказал, что я близок к окончательному ответу. Я не мог найти окончательное решение для себя, но с некоторой помощью интервьюера я смог найти решение. Это модификация моего подхода с фиксированными блоками, но разница в том, что размеры блоков не должны быть фиксированными, и мы должны попытаться взять блоки большего размера внизу и уменьшить размер блока по мере продвижения вверх. Правильным ответом было 14. Смотрите это видео https://youtu.be/uBhSIKLlvdk для правильного объяснения.
Поскольку оставалось еще немного времени, он задал несколько общих технических вопросов, в основном о базах данных, таких как NoSQL и SQL, свойствах ACID, когда использовать NoSQL вместо базы данных SQL и т. д. Интервьюер все время сохранял невозмутимое выражение лица, поэтому я не был уверен, как этот раунд прошел.
Раунд 4 на месте (60 минут): спроектируйте систему хранения сим-карт, которая выдает вам 3 сим-карты по запросу, и каждая из них имеет 10-значный номер телефона.
- Сгенерированные числа должно быть очень трудно предсказать
- Нам нужно отслеживать проданные телефонные номера, а также общее количество неиспользованных номеров, которые есть в системе в любой момент времени.
- Телефонные номера должны храниться очень эффективно, а поиск доступных телефонных номеров должен быть быстрым.
Я пошел с наивным подходом к использованию базы данных, в которой были все возможные 10-значные числа, которые будут храниться как одна запись, каждая с дополнительными метаданными. Он бросил мне вызов и сказал, что это не соответствует требованиям эффективности хранения и случайности. Я подумал еще немного и пришел к мысли использовать структуру данных Trie, так как это наиболее эффективный способ хранения строк. Я сделал интерактивную доску, используя trie в качестве хранилища данных, и показал ему, что телефонные номера с одинаковыми префиксами будут использовать одни и те же узлы и дадут огромную эффективность с точки зрения хранения. Поскольку нам нужны 10-значные длинные телефонные номера, Trie будет состоять из 10 уровней, и каждый узел Trie будет иметь 10 дочерних узлов (т. е. для цифр от 0 до 9). В любое время, когда мы запрашиваем доступные числа, мы можем сделать это непредсказуемым, выбирая любую цифру от 0 до 9 случайным образом в каждом узле дерева. Чтобы отслеживать количество доступных телефонных номеров, мы можем хранить дополнительные метаданные на каждом узле, т. е. когда продается 10-значный номер, мы можем увеличивать количество в каждом узле дерева, связанном с этим 10-значным номером, и с этим корень узел trie будет иметь общее количество проданных номеров для каждой начальной цифры от 0 до 9.
Интервьюеру понравилась идея, и он начал оспаривать доступность и согласованность. Мы обсудили запуск резервного хранилища данных trie, кэширование, периодическое сохранение trie на диск и т. д. В целом этот раунд прошел хорошо.