Easyprefix-sum
Что такое prefix sum?
1Постановка
Разберём, что от вас хотят в этом вопросе и как к нему подступиться на собеседовании.
2Решение
Prefix sum — массив cumulative sums для range sum queries за O(1) после preprocessing O(n).
def prefix_sum(arr):
prefix = [0]
for x in arr:
prefix.append(prefix[-1] + x)
return prefix
# sum arr[i..j] = prefix[j+1] - prefix[i]
# LeetCode 560: число subarrays с суммой k
def subarraySum(nums, k):
count, prefix = 0, 0
seen = {0: 1}
for x in nums:
prefix += x
count += seen.get(prefix - k, 0)
seen[prefix] = seen.get(prefix, 0) + 1
return countИдея LeetCode 560: для каждого prefix ищем prefix' такой что prefix − prefix' = k. 2D prefix sum — для sum любого submatrix за O(1). Difference array — обратная техника для range update за O(1).
3Как отвечать
- Сначала уточните условия и ограничения, покажите аналитическое мышление.
- Рассуждайте вслух — интервьюеру важен ход мысли, а не только финальный ответ.
- Оцените сложность по времени и памяти (Big-O), если это алгоритмический вопрос.
💡
На реальном собеседовании Alffert подскажет развёрнутый ответ в реальном времени.