Готовимся к интервью в Netflix и Facebook и создаем 5 практических функций

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

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

Вот почему в этой статье мы хотим немного изменить подход к собеседованию, решив некоторые реальные проблемы, с которыми сталкиваются технологические компании. Изучение того, как создавать реальные функции (например, как объединять рекомендации на Amazon), более увлекательно, и кроме того, это гораздо легче запоминается. Если вы можете понять суть проблемы и найти для нее решение, то вы сможете применить это решение и в других, похожих ситуациях.

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

Краткий обзор:

• Функция Netflix: группировка похожих заголовков (hashmaps)
• Функция Facebook: круг друзей (DFS)
• Функция Календаря Google: поиск конференц-залов (heaps)
• Функция Amazon: товары в ценовом диапазоне (BST)
• Функция Twitter: добавление лайков (strings)
• Что дальше?

Функция Netflix: группировка похожих заголовков (hashmaps)

Netflix — одна из крупнейших платформ потокового видео. Команда инженеров Netflix всегда ищет новые способы отображения контента. Давайте представим, что мы разработчик из команды Netflix.

Задача: наша задача — улучшить поиск, давая возможность пользователям видеть релевантные результаты без опечаток. Мы называем это функцией «Group Similar Titles» (с англ. группировать похожие заголовки).

Во-первых, нужно определить, как индивидуально сгруппировать любую комбинацию символов для данного заголовка. Представим, что в нашей библиотеке есть следующие названия: “duel,” “dule,” “speed,” “speed,” “deul,” и “cars.”. Вам поручено разработать функционал так, чтобы, если пользователь неправильно написал слово (например, “speed” как “spede”), ему все равно был показан правильный заголовок.

Нам нужно разбить наши заголовки на наборы слов, чтобы слова в наборе были анаграммами. У нас есть три набора: {“duel”, “dule”, “deul”}, {“speed”, “spede”} и {“cars”}. Результаты поиска должны включать все элементы набора, в котором находится строка. Лучше предварительно определить наборы, а не формировать их, когда пользователь выполняет поиск.

Члены каждого набора имеют одинаковую частоту каждой буквы, поэтому частота каждой буквы в словах одной группы одинакова. Например, в нашем наборе {{“speed”, “spede”}} частота символов одинакова в каждом слове: s, p, e и d.

Итак, как нам разработать и реализовать эту функциональность? Давайте разбираться.

— Для каждого заголовка нам нужно вычислить вектор из 26 элементов. Каждый векторный элемент представляет частоту английской буквы в заголовке. Мы можем представить частоту, используя строку, содержащую символы #. Этот процесс сопоставления генерирует идентичные векторы для строк, которые являются анаграммами. Например, мы представляем abbccc как # 1 # 2 # 3 # 0 # 0 # 0 … # 0.

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

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

— Каждое значение — это индивидуальный набор, поэтому мы возвращаем значения хэш-таблицы.

Реализация на Java

https://gist.github.com/BetterProgramming/af7e393fab706312af9196b4e241906b#file-netflixsolution-java

Если вы хотите увидеть решение на Python, посмотрите исходный пост.

Сложность

— По времени: O (n ∗ k), поскольку мы считаем каждую букву для каждой строки в списке.

— По памяти: O (n ∗ k), поскольку каждая строка хранится как значение в словаре, а размер строки может быть k.

Функция Facebook: круг друзей (DFS)

Facebook — крупнейшая социальная сеть в мире. Они также владеют и управляют Instagram. Представьте, что вы команда инженеров Facebook, и перед вами стоит задача улучшить интеграцию между их платформами.

Задача: наша задача — найти всех людей на Facebook, которые входят в круг друзей пользователя. Назовем этот функционал «Круг друзей».

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

Пример: если Ник — прямой друг Эми, а Эми — прямой друг Мэтта, то Ник — косвенный друг Мэтта.

Мы будем использовать квадратную матрицу размера n * n. Например, ячейка [i, j] будет содержать значение 1, если эти пользователи являются друзьями. В противном случае ячейка будет содержать значение 0. На иллюстрации ниже есть два круга друзей из приведенного выше примера. Ник дружит только с Эми, но Эми дружит с Ником и Мэттом. Это формирует круг друзей. Марио самостоятельно создает еще один круг друзей.

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

Наша задача — найти количество соединяемых компонентов. Мы рассматриваем входную матрицу как матрицу смежности. Итак, как же это спроектировать и реализовать?

— Сначала мы инициализируем массив с именем visit. Он будет отслеживать посещенные вершины размера n со значением 0 для каждого индекса.

— Затем мы проходим по графу, используя DFS, если посещение [v] равно 0, а если нет, мы переходим к следующему v.

— Затем присваиваем посещенному [v] значение 1 для каждого v, с которым сталкивается наш обход DFS.

— Когда обход DFS завершен, мы должны увеличить счетчик круга на 1. Это означает, что связанный компонент был полностью пройден.

Реализация на Java

https://gist.github.com/BetterProgramming/eaa0e12c8bb5c7b74cb2c13a2f9c04e4#file-friendcircle-java

Сложность

— По времени: O (n^2), потому что мы проходим полную матрицу размера n².

— По памяти: O (n), потому что массив посещений, в котором хранятся наши посещенные пользователи, имеет размер n.

Функция Календаря Google: поиск конференц-залов(кучи)

Инструмент Google Calendar является частью GSuite, используемого для управления событиями и напоминаниями. Представьте, что вы — разработчик в команде Google Календаря, и перед вами стоит задача реализовать некоторые функции, повышающие продуктивность.

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

Нам дается время встреч. Нужно найти способ определить количество конференц-залов, необходимых для их всех. Каждая встреча будет содержать положительные целые числа для startTime и endTime.

Время нашей встречи может быть указано следующим образом: {{2, 8}, {3, 4}, {3, 9}, {5, 11}, {8, 20}, {11, 15}}. Мы могли бы запланировать каждую встречу в отдельной комнате, но мы хотим использовать минимальное количество комнат. Мы видим, что три встречи частично совпадают: {2, 8}, {3, 4} и {3, 9}. Следовательно, как минимум для этих трех потребуются отдельные комнаты.

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

Итак, как нам создать этот функционал?

1. Отсортируйте встречи по времени начала.
2. Разместите первую встречу в комнате. Добавьте endTime как запись в куче.
3. Просмотрите другие встречи и проверьте, закончилась ли встреча наверху.
4. Если комната свободна, извлеките этот элемент и снова добавьте его в кучу с указанием времени окончания текущего митинга, который мы хотим обработать. Если она не свободна, выделите новую комнату и добавьте ее в нашу кучу.
5. После обработки списка встреч размер кучи подскажет, сколько комнат выделено. Это и должно быть минимальное количество необходимых комнат.

Реализация на Java

https://gist.github.com/BetterProgramming/ea47f16fefbb49bd4508a8aadb7fcdb5#file-meetingsolution-java

Если вы хотите увидеть решение на Python, посмотрите исходный пост.

Сложность

— По времени: O (n ∗ log (n))

— По памяти: O (n), где n — количество встреч.

Характеристика Amazon: товары в диапазоне цен (BST)

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

Задача: реализовать фильтр поиска, чтобы найти товары в заданном ценовом диапазоне. Данные о продукте представлены в виде двоичного дерева поиска. Значения — это цены продуктов.

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

Затем они сохраняются в двоичном дереве поиска:

Мы можем предположить, что выбранный диапазон цен low = 7 и high = 20, поэтому наша функция должна возвращать только цены {9, 8, 14, 20, 17}. Итак, как нам это реализовать?

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

1. Реализуйте рекурсивную вспомогательную функцию для прямого обхода.
2. Проверьте, находится ли текущее значение узла в заданном диапазоне. Если да, добавьте его в выходной массив.
3. Рекурсивно вызовите функцию прямого обхода для левого дочернего элемента узла, если текущее значение узла больше или равно low.
4. Если текущее значение узла меньше или равно high, рекурсивно пройдите по правому дочернему элементу узла.
5. По завершении обхода будет возвращен выходной массив.

Реализация на Java

https://gist.github.com/BetterProgramming/ad827e15bc55837069c9ac1fa897369a#file-main-java

Если вы хотите увидеть решение на Python, посмотрите исходный пост.

Сложность

— По времени: O (n)
— По памяти: O (n)

Функция Twitter: добавление лайков (strings)

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

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

Данные уже извлечены и сохранены в простом текстовом файле. Все значения должны оставаться строками и не могут быть преобразованы в целые числа. Из-за этих ограничений мы должны выполнять добавление цифр за цифрой. Итак, как нам сделать это?

1. Инициализируйте пустую переменную res и перенос(с англ. carry;присвойте значение 0).
2. Затем установите два указателя (p1 и p2), которые будут указывать на конец like1 и like2.
3. Пройдите по строкам с конца, используя эти указатели.
4. Установите x1 равным цифре из строки like1 с индексом p1. Если p1 достиг начала like1, установите x1 в 0. Сделайте то же самое для x2 с like2 с индексом p2.
5. Вычислите текущее значение, используя value = (x1 + x2 + carry)% 10. Затем обновите перенос так, чтобы carry = (x1 + x2 + carry) / 10.
6. Добавить текущее значение к результату.
7. Если обе строки пройдены, но перенос по-прежнему не равен нулю, добавьте перенос(carry) в res.
8. Наконец, переверните результат и преобразуйте его в строку. Верните эту строку.

https://gist.github.com/BetterProgramming/d96ea5fd5c617e050f7a0c91196b76cb#file-addlikes-java

Сложность

— По времени: O (max (n¹, n²))

— По памяти: O (max (n¹, n²))

Что дальше?

Поздравляю, вы дочитали до конца! Вы только что создали пять практических функций, используя такие штуки, как DFS, BST, кучи и другие. Как видите, это мощный способ подготовиться к собеседованию по программированию, который, к тому же, очень эффективный. Если вы сможете понять суть проблемы и найти к ней решение, то с легкостью решите подобную. Эта статья — переосмысление подготовки к собеседованию по программированию. Удачного обучения!

Есть еще множество других практических задач, таких как:

1. Объединение твитов в ленту Twitter.
2. AT&T определение местонахождения.
3. Zoom: отображение лобби собрания.
4. Поисковая система: поиск слов.

И еще много других…

Источник