Mediumarraysprefix
Решить задачу Product of Array Except Self (LeetCode 238)?
1Постановка
Разберём, что от вас хотят в этом вопросе и как к нему подступиться на собеседовании.
2Решение
LeetCode 238. Для каждого i вернуть product всех элементов кроме nums[i], без деления, за O(n). Подход: prefix и suffix products.
def productExceptSelf(nums):
n = len(nums)
result = [1] * n
# prefix: result[i] = product of nums[0..i-1]
prefix = 1
for i in range(n):
result[i] = prefix
prefix *= nums[i]
# suffix: умножить на product of nums[i+1..n-1]
suffix = 1
for i in range(n - 1, -1, -1):
result[i] *= suffix
suffix *= nums[i]
return resultПервый проход: result[i] = произведение всех слева. Второй: умножаем на произведение всех справа. Без extra space (кроме output). С делением (если разрешено): total / nums[i] — но edge cases с нулями. LeetCode запрещает деление. Проверяет thinking in prefix/suffix terms.
3Как отвечать
- Сначала уточните условия и ограничения, покажите аналитическое мышление.
- Рассуждайте вслух — интервьюеру важен ход мысли, а не только финальный ответ.
- Оцените сложность по времени и памяти (Big-O), если это алгоритмический вопрос.
💡
На реальном собеседовании Alffert подскажет развёрнутый ответ в реальном времени.