Вы могли заметить, что довольно давно не было постов тут, а дело тут вот в чем — я уволился и искал новую работу, поэтому много свободного времени уделял на подготовку к собеседованиям. Сейчас, наконец, все устаканилось, может быть, я позже расскажу подробнее как это было, но пока, благодаря этому я смог вернуться к вам с разными задачами и темами собесов, которые сейчас актуальны 😎
Поэтому первый пост про задачку, которую мне дали на первом этапе собеседования, довольно простая задачка на алгоритмы и знание питона. Кроме решения необходимо было, как и везде оценить сложность и предложить, как его улучшить.
От себя могу сказать, что задача совершенно несложная (уровень изи на литкоде), проверяет просто то, что вы умеет что-то писать на питоне. Собственно, если вы не собеситесь в Яндекс, то и вряд ли на DE у вас будут жестить по алгоритмам.
Итак, что нужно:
Даны два массива и число target. Нужно найти такие пары чисел (по одному из каждого массива), сумма которых даёт target. Вернуть надо их индексы.
Пример:
a = [1, 3, 5]
b = [2, 4, 6]
target = 7
Ответ:
(0, 1)
(1, 0)
(2, 2)
Решение:
Вариант 1: В лоб, через перебор
for i in range(len(a)):
for j in range(len(b)):
if a[i] + b[j] == target:
print (i, j)
Просто, понятно, но O(n²)
Вариант 2: Добавим хеш-таблицу, т.к. поиск в ней по ключу — О(1)
b_map = {value: j for j, value in enumerate(b)}
for i, value in enumerate(a):
needed = target - value
if needed in b_map:
print (i, b_map[needed])
Уже гораздо лучше, сложность уже О(n). Но самые внимательные из вас могли подумать и заметить: а что, если для одного числа из первого массива подходит несколько вариантов из второго. Вот тут пригодится такая очень удобная тема, как defaultdict.
Вариант 3: Через defaultdict
b_map = defaultdict(list)
for j, value in enumerate(b):
b_map[value].append(j)
for i, value in enumerate(a):
needed = target - value
if needed in b_map:
result.append((i, b_map[needed]))
print(result)
Этот вариант тоже работает за O(n + m), но позволяет найти все индексы b, подходящие к каждому a[i]
Оставляйте ваши решения в комментарии 😎 👇
Вернусь с другими задачами и вопросами с собесов
@bigdata_postupashki