Задача, которую предлагали на собеседованиях в Apple: у вас есть массив с целыми числами, в том числе и отрицательными, вам нужно найти самое большое произведение 3 чисел из этого массива.
Например: у вас есть массив list_of_ints, содержащий числа -10, -10, 1, 3, 2. Функция, которая обрабатывает этот массив, должна вернуть 300, так как -10 * -10 * 3 = 300. Задание нужно выполнить максимально эффективно, не забывая про отрицательные числа.
Решение
Методов решения много, но не так просто добиться O(n) времени выполнения и O(1) затрат памяти. Для эффективного решения задачи мы создадим и будем наблюдать за состоянием следующих переменных:
- highest_product_of_three
- highest_product_of_2
- highest
- lowest_product_of_2
- lowest
Когда мы пройдемся по массиву до конца, в highest_product_of_three будет содержаться наш ответ, а остальные переменные мы используем как временный буфер. highest_product_of_2 и lowest_product_of_2 будут содержать наибольшее произведение из двух и наименьшее произведение из двух соответственно, а проходя по массиву, мы будем проверять произведение текущего числа current с этими переменными (отрицательный current с lowest_product_of_2 и положительный с highest_product_of_2). highest и lowest нам нужны для запоминания минимального и максимального чисел в массиве.
Код решения на Python:
def highest_product_of_3(list_of_ints):
# Проверим, чтобы в массиве было 3 и больше чисел.
if len(list_of_ints) < 3:
raise Exception('Less than 3 items!')
# Мы начнем с 3-его элемента массива (с индекса 2),
# так как первые 2 элемента уже сразу пойдут
# в highest_product_of_2 и lowest_product_of_2.
highest = max(list_of_ints[0], list_of_ints[1])
lowest = min(list_of_ints[0], list_of_ints[1])
highest_product_of_2 = list_of_ints[0] * list_of_ints[1]
lowest_product_of_2 = list_of_ints[0] * list_of_ints[1]
# Также вычислим highest_product_of_three из первых 3-х элементов.
highest_product_of_three = list_of_ints[0] * list_of_ints[1] * list_of_ints[2]
# Начинаем проход по массиву с индекса 2.
for current in list_of_ints[2:]:
# проверяем возможность увеличить highest_product_of_three
# или оставляем его как есть.
highest_product_of_three = max(
highest_product_of_three,
current * highest_product_of_2,
current * lowest_product_of_2)
# То же самое проверим и на максимальном произведении из двух.
highest_product_of_2 = max(
highest_product_of_2,
current * highest,
current * lowest)
# И на минимальном произведении из двух.
lowest_product_of_2 = min(
lowest_product_of_2,
current * highest,
current * lowest)
# Появилось ли новое максимальное число?
highest = max(highest, current)
# Появилось ли новое минимальное число?
lowest = min(lowest, current)
return highest_product_of_three
Сложность алгоритма — O(n) по времени выполнения и O(1) по памяти.
Источник: Interview Cake