Автор оригинала: Robin Andrews.
Эта статья посвящена классическому вызову, который часто дается в интервью по кодированию на Python. Есть несколько различных подходов, которые вы могли бы использовать для решения этой задачи, но цель состоит в том, чтобы найти решение, которое имеет “разумную” временную сложность – то есть при большом вводе оно будет завершено в течение нескольких секунд, а не часов…
Учитывая несортированный список целых чисел, найдите пару, которая складывается в заданное значение. Определите индексы значений, которые суммируются с целью. Эти индексы должны быть различны (т. Е. вы не можете использовать значение в одной и той же позиции дважды).
Например:
входные данные [1, 2, 3], 4
должен дать выход (0, 2)
Почему бы вам самому не попробовать кодировать решение?
Для того чтобы сосредоточить свой ум на желаемом результате решения этой задачи, очень хорошо написать несколько базовых тестов или, по крайней мере, рассмотреть конкретный пример и четко определить, какого результата вы ожидаете.
Тестирование -это большая тема, и мы не будем здесь вдаваться в подробности, но чтобы дать вам фору, я приведу несколько очень простых тестов в виде операторов Python assert . Если вы новичок в утверждениях assert, то это просто простой способ проверить ваш код – когда он верен, ничего не произойдет, что хорошо, но если утверждение неверно, вы получите AssertionError . Если это не ясно и вы предпочитаете не использовать assert, вы можете удалить эти операторы и просто использовать вместо них оператор print. Например, print(sum_of_squares(10)).
Имея это в виду, вот некоторые заглушки функций и несколько тестов, чтобы вы начали:
# 2-Sum Interview Problem
def two_sum_problem(arr, target):
pass
assert two_sum_problem([1, 2, 3], 4) == (0, 2)
assert two_sum_problem([1234, 5678, 9012], 14690) == (1, 2)
assert two_sum_problem([2, 2, 3], 4) in [(0, 1), (1, 0)]
assert two_sum_problem([2, 2], 4) in [(0, 1), (1, 0)]
assert two_sum_problem([8, 7, 2, 5, 3, 1], 10) in [(0, 2), (2, 0), (1, 4), (4, 1)]
Причина, по которой некоторые из этих утверждений имеют несколько возможных значений, заключается в том, что мы не определили порядок, в котором функция будет тестировать пары кандидатов, поэтому нам нужно учитывать более одного возможного решения, в том числе когда оба кандидата имеют одно и то же значение (они не могут иметь один и тот же индекс по определению задачи).
Python Programming Two Sum Interview Problem – Наивный Подход
То, как вы решите решить эту проблему, будет зависеть от вашего уровня опыта. Один из подходов состоит в том, чтобы повторить список и для каждого элемента сравнить его со всеми остальными элементами в списке.
Хотя этот подход очень неэффективен из-за большого количества используемых сравнений (он имеет O(n^2) временную сложность), его все же стоит реализовать, так как это даст вам возможность полностью понять задачу и почувствовать, что нужно.
Вот заглушка и несколько тестов для наивного подхода. Попробуйте сами, прежде чем смотреть на мое решение.
def two_sum_problem_brute_force(arr, target):
pass
assert two_sum_brute_force([1, 2, 3], 4) == (0, 2)
assert two_sum_brute_force([1234, 5678, 9012], 14690) == (1, 2)
assert two_sum_brute_force([2, 2, 3], 4) in [(0, 1), (1, 0)]
assert two_sum_brute_force([2, 2], 4) in [(0, 1), (1, 0)]
assert two_sum_brute_force([8, 7, 2, 5, 3, 1], 10) in [(0, 2), (2, 0), (1, 4), (4, 1)]
И вот мое решение.
# Two Sum Interview Problem
# Brute force approach
def two_sum_brute_force(arr, target):
length = len(arr)
for i in range(length - 1):
for j in range(1, length):
# print(i, j)
if arr[i] + arr[j] == target:
return i, j
return None
Вы должны держать свои утверждения утверждениями, и если код работает без ошибок, вы можете быть вполне уверены, что ваше решение правильно, хотя вы вполне можете захотеть написать еще несколько тестов, включая проверку крайних случаев .
Улучшенное решение задачи интервью с 2 суммами с использованием бинарного поиска
Цель интервьюера, задавая этот вопрос, вполне может состоять в том, чтобы получить представление о вашем общем подходе к решению проблем, но также и увидеть, осознаете ли вы “большую” проблему с наивным подходом (его радикальную неэффективность для любого большого ввода) и насколько хорошо вы можете применить свои знания алгоритмов, чтобы придумать более эффективное решение.
Один из подходов, который может произвести впечатление на вашего интервьюера, заключается в том, чтобы сначала пойти по пути сортировки входных данных и посмотреть, куда это вас приведет. Сортировка-это относительно недорогая операция при условии использования хорошего алгоритма, поэтому, если мы можем улучшить эти вложенные циклы for , то мы должны это сделать.
Оказывается, это обеспечивает аккуратное решение проблемы двух сумм: мы можем отсортировать наши данные, а затем использовать алгоритм двоичного поиска , чтобы найти дополнение к текущему значению для решения задачи.
Например, если текущее значение, когда мы проходим через наш вход, равно 11 , а целевое значение равно 20, мы используем двоичный поиск, чтобы найти это значение 9 на входе. Если он там, мы закончили. Однако нам нужно быть осторожными, чтобы исключить текущее значение из поиска, поскольку проблема требует, чтобы мы не могли использовать один и тот же входной элемент дважды для формирования нашей суммы.
Код этого улучшенного решения приведен ниже:
# Binary Search Solution to Two Sum Interview Problem
def binary_search(lst, target):
low = 0
high = len(lst) - 1
while low <= high:
mid = (low + high) // 2
if lst[mid] == target:
return mid
elif lst[mid] > target:
high = mid - 1
else:
low = mid + 1
return None
def two_sum_binary_search(arr, total):
length = len(arr)
arr = sorted(arr)
for i in range(length):
complement = total - arr[i]
complement_idx = binary_search(arr, complement)
# print(f"comliment: {complement} idx: {complement_idx}")
if complement_idx is not None: # Found solution!
if complement_idx != i:
return (i, complement_idx)
return None
assert two_sum_binary_search([2, 2], 4) in [(0, 1), (1, 0)]
print(two_sum_binary_search([8, 7, 2, 5, 3, 1], 10)) # Sorted!!
assert two_sum_binary_search([8, 7, 2, 5, 3, 1], 10) in [(2, 4), (4, 2), (1, 5), (5, 1)]
Это решение содержит несколько утверждений. Обратите внимание, что в этой версии тесты должны основываться на отсортированном массиве.
Решение хэш-таблицы для Python Two Sum Interview Problem
Подход, который, скорее всего, произведет впечатление на вашего интервьюера, заключается в использовании хэш-таблицы . В Python это обычно просто означает использование словаря . Основная идея заключается в том, что мы перебираем наши входные данные, ища комплимент текущего значения ( target – current_value ) в хэш-таблице. Если его найдут, нам конец. В противном случае мы храним значения в хэш-таблице вместе с индексами, где эти значения были найдены.
Ключевое наблюдение: хэш-таблица хранит пары value: index с текущим входным значением в качестве ключа и индексом в качестве записи для этого ключа.
Вот список кода для решения проблемы интервью с двумя суммами на основе хэш-таблицы в Python. Поскольку хэш-таблицы, как правило, являются очень эффективными структурами данных для выполнения поиска, это решение очень экономично по времени (в основном O(n) временная сложность).
В зависимости от вашего уровня опыта, вы можете попробовать реализовать решение самостоятельно. Если да, то вот заглушка и несколько тестов, чтобы вы могли начать. Мое решение показано ниже.
def two_sum_hash_table(arr, total):
pass
assert two_sum_hash_table([1, 2, 3], 4) in [(0, 2), (2, 0)]
assert two_sum_hash_table([1234, 5678, 9012], 14690) in [(1, 2), (2, 1)]
assert two_sum_hash_table([2, 2, 3], 4) in [(0, 1), (1, 0)]
assert two_sum_hash_table([2, 2], 4) in [(0, 1), (1, 0)]
assert two_sum_hash_table([8, 7, 2, 5, 3, 1], 10) in [(0, 2), (2, 0), (1, 4), (4, 1)]
Мое решение:
def two_sum_hash_table(arr, total):
hash_table = dict()
for i in range(len(arr)):
complement = total - arr[i]
if complement in hash_table:
return (i, hash_table[complement])
else:
hash_table[arr[i]] = i
return None
assert two_sum_hash_table([1, 2, 3], 4) in [(0, 2), (2, 0)]
assert two_sum_hash_table([1234, 5678, 9012], 14690) in [(1, 2), (2, 1)]
assert two_sum_hash_table([2, 2, 3], 4) in [(0, 1), (1, 0)] # order!
assert two_sum_hash_table([2, 2], 4) in [(0, 1), (1, 0)]
assert two_sum_hash_table([8, 7, 2, 5, 3, 1], 10) in [(0, 2), (2, 0), (1, 4), (4, 1)]
В этой статье мы рассмотрели три подхода к проблеме интервью с двумя суммами с использованием Python. Надеюсь, вы нашли это полезным. Дайте мне знать в комментариях, если вы это сделали.
Эта статья основана на сообщение в блоге академии Компу
Счастливых вычислений!