Будьте готовы, если вы проходите собеседование в Uber
Ужасное собеседование по программированию на доске. Мы все ненавидим это, но все должны признать это.
Для компаний стало стандартом проверять навыки программирования соискателей, особенно на должностях младшего и среднего звена. Итак, давайте отточим наши навыки и попробуем сегодня.
Проведя время в нескольких разных странах, я создал крепкую сеть друзей, занимающихся программным обеспечением, в Лондоне, Нью-Дели, Сан-Франциско, Чикаго, Сингапуре, Берлине и Мюнхене.
В этом случае я делюсь тем, чем поделились в моей сети - вопрос, заданный в интервью Uber.
Вопрос
Учитывая массив целых чисел с именем numbers, верните новый массив, где в индексе i есть кратное всех целых чисел в массивеnumbers, кроме одного в индексе i. Ниже приведены некоторые примеры, пример 1:
Ввод: [1, 2, 3, 4, 5]
Ответ: [120, 60, 40, 30, 24]
Пример 2:
Ввод: [7, 8, 9]
Ответ: [72, 63, 56]
Пример 3:
Ввод: [12, 2, 6]
Ответ: [12, 72, 24]
Решение
Как и большинство вопросов на собеседовании по программированию на доске, мы можем решить эту проблему с помощью вложенного цикла и грубой силы, чтобы получить ответ. Однако это даст нам временную сложность только O (n²). Итак, давайте посмотрим на более элегантное решение:
Здесь мы проходим через массив один раз, чтобы создать общее кратное для всех чисел в массиве. Получив это, мы можем еще раз пройти через входной массив, чтобы создать выходной массив, просто разделив значение по индексу, который нам не нужен. Выполнено! Это было просто. Поскольку мы дважды прошли через массив, временная сложность здесь равна O(n) + O(n), что по-прежнему равно O (n). То же самое и с пространственной сложностью решения.
Этот конкретный вопрос был очень легким, но у меня есть еще много таких, которые я собираюсь опубликовать, поэтому следите за ним, чтобы отточить свои навыки собеседования по программированию на доске!
