Uber Interview Experience для летней стажировки (в кампусе)

Раунд 1 (Оценочный онлайн-тест) — 60 минут. Первый раунд включал в себя тест на кодирование, который проводился на CodeSignal. Этот раунд содержал три вопроса, которые приведены ниже:

• Задача 1: Преобразование чисел из базы 2 в базу 6. Ссылка на задачу с решением, аналогичным моему: https://www.geeksforgeeks.org/convert-a-number-from-base-2-to-base- 6
• Задача 2. Имея двоичную строку из нулей и единиц, вы можете выполнить следующую операцию конечное число (возможно, нулевое) раз: выбрать подстроку длины, большей или равной K, и поменять местами все биты подстроки. Вам нужно найти максимально возможное значение K такое, что после выполнения этой операции конечное число (возможно, ноль) раз вы сможете сделать все биты строки равными.

Мой подход: я разработал подход, связанный с применением дека. Я сохранил длины подстрок с одинаковыми последовательными символами в деке (001000110 -> 2 1 3 2 1). Затем, пока размер дека не станет равным единице, я вытащил минимальное значение из крайнего правого и крайнего левого значения и обновил ответ как answer = min(answer, N - currentMinVal), где N - длина строки (1 <= N <= 1e5), а затем добавил это значение к своему соседу в деке (2 1 3 2 1 -> 2 1 3 3 -> 3 3 3 -> 3 6 -> 9). Ответ для этого случая будет шесть, поскольку 9 – 3 = 6 (N = 9) является минимальным значением среди всех итераций. Некоторые из моих товарищей по партии смогли решить эту проблему с помощью бинарного поиска.

• Задача 3. Боулинг — это вид спорта, в котором игрок катит шар для боулинга к группе кеглей, цель которого — сбить кегли в конце дорожки. В этом задании немного изменены правила игры. Имеется N штифтов, N четно, и штифты расположены горизонтально, а не треугольным образом. На i-м выводе стоит номер arr[i]. В каждом броске вы должны сбить ровно две кегли подряд. Как только вы сбьете кегли в позициях iI и i+1, кегли в позициях i-1 и i+2 станут соседними. И вы получите баллы arr[i-1]*arr[i]*arr[i+1]*arr[i+2] за сбивание i-й и i+1-й кеглей. Если i-1 или i+2 выходят за пределы, предположим, что в этой позиции есть булавка с номером 1. Узнайте, какое максимальное количество очков можно получить при грамотной игре. Поскольку ответ может быть большим, верните ответ по модулю 1e9 + 7 в качестве вывода.

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

Раунд 2 (Техническое интервью 1) — 45 минут: Этот раунд проводился онлайн на видеозвонке Zoom и CodeSignal. На звонке было два интервьюера. В этом раунде мне дали сложную задачу LeetCode. Вот ссылка на проблему: https://leetcode.com/problems/find-critical-and-pseudo-critical-edges-in-minimum-spanning-tree

Сначала меня попросили только найти критические грани. Я сразу предложил экспоненциальный подход, включающий генерацию всех возможных деревьев. После некоторых размышлений я придумал подход ² . Подход заключался в том, чтобы сначала найти MST графа с использованием алгоритма Крускала, а затем найти MST без учета текущего ребра для каждого ребра. Если для какого-либо ребра значение MST отличается от значения фактического MST, то это ребро является критическим. Интервьюер остался доволен таким подходом и попросил меня начать программировать. Я смог реализовать логику кода, но немного потрудился с реализацией DSU. В моем коде были разные глупые ошибки, которые я смог исправить ближе к концу. Мой код, наконец, заработал в последние минуты, и затем интервьюер задал мне дополнительный вопрос, чтобы изменить мой код, чтобы найти псевдокритические края. Я добавил условие, согласно которому, если значение MST после удаления текущего ребра не изменилось, то это ребро является псевдокритическим. На этом интервью подошло к концу.

Раунд 3 (Техническое интервью 2) — 45 минут. Этот раунд также проводился онлайн на видеозвонках Zoom и CodeSignal. Интервьюеров снова было двое. В этом раунде мне задали вопрос по ООП и сказали, что этот раунд фокусируется на стиле кодирования, а временные сложности не имеют значения. Меня попросили реализовать структуру данных, содержащую все названия, ингредиенты и цены блюд ресторана. Структура данных была необходима для обеспечения следующих функций:

• Добавляйте новые блюда.
• Распечатайте все блюда, присутствующие в данный момент.
• Учитывая список блюд, рассчитайте счет с 18% GST.
• Учитывая список ингредиентов, выведите все блюда, у которых есть хотя бы один общий ингредиент с данным списком.
• Учитывая список ингредиентов, выведите все блюда, у которых нет общего ингредиента с данным списком.

Я прекрасно реализовал всю функциональность, используя классы, наборы и векторы. У меня оставалось еще около 15 минут, поэтому меня попросили придумать дополнительный функционал,

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

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

Раунд 4 (собеседование с менеджером по найму) — 30 минут: этот раунд также проводился в формате видеозвонка в Zoom.

• На этот раз интервьюер был только один. Сначала меня попросили дать короткое интервью.
• Затем обсуждение перешло к проектам. Меня попросили выбрать один из проектов из моего резюме и кратко описать его. Я выбрал проект, основанный на компьютерной архитектуре, и описал его. Были также некоторые перекрестные вопросы между ними, на которые я мог ответить. Обсуждение длилось около 15 минут, затем интервьюер спросил меня о другом моем проекте, и мы его обсудили.
• В конце концов, мне задали вопрос о моих POR, чтобы рассказать о некоторых случаях, когда я либо помогал кому-то, либо обращался за помощью к кому-то во время моего пребывания в должности. Я ответил на вопрос, и затем интервьюер спросил, есть ли у меня какие-либо вопросы к нему. Я спросил его о его путешествии в Uber, и он коротко ответил. На этом интервью подошло к концу.

Окончательный вердикт: я получил предложение от Uber.