Задача, которую предлагали на собеседованиях в 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:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 | 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