📈 From O(n²) to O(n)

Задача
Дан массив целых чисел и число k. Найти количество непрерывных подмассивов с суммой ровно k.

nums = [1, 1, 1], k = 2
→ 2     ([1,1] с индексов 0-1 и 1-2)

nums = [1, 2, 3], k = 3
→ 2     ([1,2] и [3])

Наивное решение — O(n²)
Перебираем все пары (start, end) и считаем сумму:

def subarray_sum(nums, k):
    count = 0
    for i in range(len(nums)):
        total = 0
        for j in range(i, len(nums)):
            total += nums[j]
            if total == k:
                count += 1
    return count

Работает. На массиве в миллион — таймаут.

Идея — префиксные суммы + хеш-таблица
prefix[i] = сумма первых i элементов. Тогда сумма на отрезке [l, r] = prefix[r+1] - prefix[l].

Если эта сумма равна k, значит:

prefix[r+1] - prefix[l] = k
prefix[l] = prefix[r+1] - k

То есть: для текущей префиксной суммы s мы ищем, сколько раз раньше встречалась сумма s - k. Каждое такое совпадение — это отдельный подмассив, оканчивающийся в текущей позиции.

Идём один раз, копим префиксы в словарь:

def subarray_sum(nums, k):
    count = 0
    prefix = 0
    seen = {0: 1}                   # пустой префикс встречался 1 раз
    for n in nums:
        prefix += n
        count += seen.get(prefix - k, 0)
        seen[prefix] = seen.get(prefix, 0) + 1
    return count

O(n) время, O(n) память.
Что значит seen = {0: 1} в начале
Это «нулевой префикс» — сумма пустого начала. Нужно, чтобы корректно считать подмассивы, начинающиеся с индекса 0.
Пример: nums = [3], k = 3. На первом шаге prefix = 3, ищем seen[3 - 3] = seen[0] = 1. Нашли 1 подмассив. ✅

🐍Вопросы с собесов -> ProstoPython

📈 From O(n²) to O(n)

Задача
Дана строка. Найти длину самой длинной непрерывной подстроки, в которой все символы разные.

"abcabcbb"  → 3   ("abc")
"bbbbb"     → 1   ("b")
"pwwkew"    → 3   ("wke")

Наивное решение — O(n²)
Для каждой стартовой позиции расширяем подстроку, пока не встретим повтор:

def longest_unique(s):
    best = 0
    for i in range(len(s)):
        seen = set()
        for j in range(i, len(s)):
            if s[j] in seen:
                break
            seen.add(s[j])
        best = max(best, len(seen))
    return best

Работает. Но мы много раз перепроверяем одни и те же символы. Каждый новый старт начинает с нуля.

Идея — sliding window
Держим окно [left, right] и расширяем его вправо. Если новый символ уже в окне — двигаем left вперёд, пока он не уйдёт.

def longest_unique(s):
    seen = {}                    # символ → последний индекс
    left = 0
    best = 0
    for right, ch in enumerate(s):
        if ch in seen and seen[ch] >= left:
            left = seen[ch] + 1  # перепрыгиваем за повтор
        seen[ch] = right
        best = max(best, right - left + 1)
    return best

O(n) время. Окно проходит слева направо ровно один раз — left и right никогда не идут назад.

🐍Вопросы с собесов -> ProstoPython

🧠 Interview Thinking

Задача
Дан массив из n+1 целых чисел, каждое — в диапазоне [1, n]. Один элемент точно повторяется (один или несколько раз). Найти его.

nums = [1, 3, 4, 2, 2]   → 2
nums = [3, 1, 3, 4, 2]   → 3

Как думает junior — O(n) время, O(n) память
Через множество:

def find_duplicate(nums):
    seen = set()
    for n in nums:
        if n in seen:
            return n
        seen.add(n)

Работает. O(n) время, O(n) память.
Если интервьюер скажет «без дополнительной памяти и не меняй массив» — junior зависает.

Как думает чуть выше — отсортировать

def find_duplicate(nums):
    nums.sort()
    for i in range(1, len(nums)):
        if nums[i] == nums[i-1]:
            return nums[i]

O(n log n), без доп. памяти. Но массив изменён — а это часто запрещено условием.

Как думает сильный кандидат — алгоритм Флойда (поиск цикла)
Главный инсайт: рассматриваем массив как связный список, где nums[i] — это указатель на следующий узел.

nums = [1, 3, 4, 2, 2]
индекс: 0  1  2  3  4

0 → nums[0]=1 → nums[1]=3 → nums[3]=2 → nums[2]=4 → nums[4]=2 → ...
                                          ↑                       ↓
                                          └───────── повтор ──────┘

Раз есть дубликат — есть два индекса, указывающих на одно значение. Это значит, в «графе» есть цикл. А дубликат — это вход в цикл.

Дальше классика: алгоритм Флойда «черепаха и заяц».

def find_duplicate(nums):
    slow = fast = nums[0]

    # Шаг 1: встречаемся внутри цикла
    while True:
        slow = nums[slow]
        fast = nums[nums[fast]]
        if slow == fast:
            break

    # Шаг 2: ищем начало цикла
    slow = nums[0]
    while slow != fast:
        slow = nums[slow]
        fast = nums[fast]
    return slow

O(n) время, O(1) память. Массив не модифицируется.

🐍Вопросы с собесов -> ProstoPython

Попробуйте ответить без запуска, что выведет код, разбор будет через 2 часа

🐍Вопросы с собесов -> ProstoPython

Правильный ответ: [[1, 0, 0], [1, 0, 0], [1, 0, 0]]

Разбор
На первый взгляд кажется, что мы создали матрицу 3×3 и поменяли элемент в углу.
На самом деле — нет.
[0] * 3 создаёт один список [0, 0, 0]. А [[0] * 3] * 3 не создаёт три разных списка. Он создаёт три ссылки на один и тот же внутренний список.

Когда мы пишем matrix[0][0] = 1, мы меняем тот единственный список, на который смотрят все три «строки».

🐍Вопросы с собесов -> ProstoPython

⏱️ Big O Breakdown

def mystery(n):
    if n <= 1:
        return n
    return mystery(n // 2) + mystery(n // 2)

Какая сложность?
A) O(log n)
B) O(n)
C) O(n log n)
D) O(2ⁿ)

Правильный ответ: B — O(n)

Разбор
Глаз видит n // 2 и сразу хочет сказать «логарифм!». Классическая ловушка.
O(log n) появляется, когда мы делим задачу пополам и идём только в одну половину (как бинарный поиск). Здесь мы делим пополам — но рекурсивно вызываемся дважды.

Дерево вызовов:

                mystery(n)
              /            \
       mystery(n/2)      mystery(n/2)
        /        \         /        \
    n/4         n/4      n/4        n/4
   /   \       /  \     /   \      /   \
  ...

На каждом уровне общая работа удваивается. Уровней — log n. Узлов в дереве — 2^(log n) = n.
Итого — O(n).

🐍Вопросы с собесов -> ProstoPython

🧰 Code Cleanup

Плохой код

class User:
    def __init__(self, name, age, email):
        self.name = name
        self.age = age
        self.email = email

    def __repr__(self):
        return f"User(name={self.name!r}, age={self.age}, email={self.email!r})"

    def __eq__(self, other):
        if not isinstance(other, User):
            return NotImplemented
        return (self.name, self.age, self.email) == (other.name, other.age, other.email)

15 строк, чтобы просто хранить три поля. Каждое имя повторяется 3-4 раза. Опечатка в одном месте — баг.

Чистый вариант

from dataclasses import dataclass

@dataclass
class User:
    name: str
    age: int
    email: str

Три строки. Python сам сгенерирует:
__init__ с правильными аргументами
__repr__ с красивым выводом
__eq__ со сравнением по полям

Что это даёт

u1 = User("Anna", 30, "anna@example.com")
u2 = User("Anna", 30, "anna@example.com")

print(u1)        # User(name='Anna', age=30, email='anna@example.com')
u1 == u2         # True

Всё работает «из коробки»

🐍Вопросы с собесов -> ProstoPython

❌ Rookie Mistakes

result = 0.1 + 0.2
if result == 0.3:
    print("ок")
else:
    print("WTF?!")

Вывод: WTF?!

Что происходит
В Python (и почти везде) числа с плавающей точкой хранятся в двоичном виде. И некоторые десятичные дроби не имеют точного представления в двоичной системе — как 1/3 не записывается точно в десятичной.

print(0.1 + 0.2)
# 0.30000000000000004

Эта микроскопическая разница — не баг Python. Это стандарт IEEE 754, и так работает везде: в JavaScript, в C, в калькуляторах.

Где это коварно

balance -= 0.1
balance -= 0.1
balance -= 0.1
# теперь balance не "0.7", а 0.7000000000000001

Накапливается. На финансовых данных или физических расчётах — катастрофа.

if total == 100.0:   # сравнение с round-числом
    ...              # может никогда не сработать

Как правильно
Сравнение с допуском:

import math
if math.isclose(0.1 + 0.2, 0.3):
    print("ок")


math.isclose сравнивает с относительным или абсолютным допуском. Параметры по умолчанию подходят для большинства случаев.

Или вручную:

if abs(a - b) < 1e-9:
    ...

🐍Вопросы с собесов -> ProstoPython

⏱️ Big O Breakdown

def top_after_each_insert(nums):
    sorted_list = []
    result = []
    for n in nums:
        sorted_list.append(n)
        sorted_list = sorted(sorted_list)   
        result.append(sorted_list[-1])
    return result

nums длины n.

Какая сложность?
A) O(n log n)
B) O(n²)
C) O(n² log n)
D) O(n³)

Правильный ответ: C — O(n² log n)

Разбор
Внешний цикл — n шагов.
Внутри на каждом шаге вызывается sorted(sorted_list). Размер списка к шагу i — это i. Сложность сортировки — O(i log i).
Считаем суммарную работу:

шаг 1:  1 × log 1
шаг 2:  2 × log 2
шаг 3:  3 × log 3
...
шаг n:  n × log n

Это O(n² log n) — на каждом шаге пересортируем всё с нуля.

🐍Вопросы с собесов -> ProstoPython

📈 From O(n²) to O(n)

Задача
Дан массив целых чисел (с отрицательными!). Найти непрерывный подмассив с максимальным произведением.

nums = [2, 3, -2, 4]    → 6     ([2, 3])
nums = [-2, 0, -1]      → 0     ([0])
nums = [-2, 3, -4]      → 24    ([-2, 3, -4])

Для суммы работало правило: если префикс отрицательный — начни заново.
Для произведения это правило ломается. Отрицательное число может стать огромным плюсом, если потом умножить на ещё одно отрицательное.

[-2, 3, -4]
шаг 1: -2
шаг 2: -2 * 3 = -6        ← отрицательно, junior бы "сбросил"
шаг 3: -6 * -4 = 24       ← а вот и максимум

Если выкинуть «-6», максимум потеряется.

Наивное — O(n²)

def max_product(nums):
    best = nums[0]
    for i in range(len(nums)):
        product = 1
        for j in range(i, len(nums)):
            product *= nums[j]
            best = max(best, product)
    return best

Перебор всех подмассивов. Работает, но медленно.

Идея — хранить и минимум тоже

Главный инсайт: минимум может стать максимумом, если умножить на отрицательное.
Значит, в каждой точке нужно знать два значения:
max_here — лучший продукт, заканчивающийся здесь
min_here — худший (самый отрицательный) продукт, заканчивающийся здесь

Когда встречаем новое число — пересчитываем оба из трёх кандидатов:

def max_product(nums):
    max_here = min_here = best = nums[0]
    for n in nums[1:]:
        candidates = (n, max_here * n, min_here * n)
        max_here = max(candidates)
        min_here = min(candidates)
        best = max(best, max_here)
    return best

O(n) время, O(1) память.

Почему n тоже в кандидатах
Если предыдущий продукт ушёл в 0, любое умножение оставит 0. Тогда n сам по себе — новая точка старта.
Так алгоритм автоматически рестартует при нулях, и не нужен отдельный case.

🐍Вопросы с собесов -> ProstoPython

🧠 Interview Thinking

Самая знаменитая задача LeetCode. И самая полезная, чтобы научиться думать вслух.

Задача
Дан массив nums и число target. Найти индексы двух чисел, которые в сумме дают target.

nums = [2, 7, 11, 15], target = 9
→ [0, 1]   (2 + 7 = 9)

Как думает junior — O(n²)
«Переберу все пары»:

def two_sum(nums, target):
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            if nums[i] + nums[j] == target:
                return [i, j]

Работает. Решение очевидное — и подаваемое первым считается слабым.

Как думает сильный кандидат — O(n)
Главный приём — переформулировать задачу.
Не «найти пару чисел». А: «для каждого числа n спросить — нужное мне target - n уже встречалось?»
Если хранить пройденные числа в словаре {значение: индекс} — проверка занимает O(1).

def two_sum(nums, target):
    seen = {}                       # значение → индекс
    for i, n in enumerate(nums):
        complement = target - n
        if complement in seen:
            return [seen[complement], i]
        seen[n] = i

Один проход, O(n) время, O(n) память.

Главный инсайт
Не «искать пару» = искать дополнение для каждого элемента.

🐍Вопросы с собесов -> ProstoPython

🧰 Code Cleanup

Walrus-оператор := появился в Python 3.8 и сразу вызвал споры. Кто-то пихает его везде, кто-то боится трогать. Истина — между.

Что это
:= присваивает значение внутри выражения:

if (n := len(data)) > 100:
    print(f"Слишком много элементов: {n}")

Здесь мы одновременно:
посчитали len(data) → положили в n
сравнили его с 100
можем использовать n дальше

Где он реально полезен
1. Чтение по кускам (классика):

# было
chunk = file.read(1024)
while chunk:
    process(chunk)
    chunk = file.read(1024)

# стало
while chunk := file.read(1024):
    process(chunk)

Чище. И file.read(...) написан один раз, а не два.

2. Кэширование дорогого вычисления в comprehension:

# плохо: heavy() считается дважды
results = [heavy(x) for x in data if heavy(x) > 0]

# хорошо: один раз
results = [y for x in data if (y := heavy(x)) > 0]

3. Условие на основании вычисления:

# было
match = pattern.search(line)
if match:
    print(match.group(1))

# стало
if (match := pattern.search(line)):
    print(match.group(1))

Где := лучше не использовать

if (x := compute()) and (y := other()) and x + y > threshold:
    ...

Когда walrus встречается в одном выражении два раза с разными переменными — читаемость падает. Лучше вынести в отдельные строки.

И не пытайся «уплотнить» код ради красоты:

# плохо
[print(y := x * 2) for x in nums]

Walrus — для избавления от дублирования, а не для уменьшения числа строк.

🐍Вопросы с собесов -> ProstoPython

📈 From O(n²) to O(n)

Задача

Дан массив. Вернуть новый массив, где элемент i = произведение всех остальных элементов исходного.

nums = [1, 2, 3, 4]
→ [24, 12, 8, 6]
   │   │   │  └─ 1*2*3
   │   │   └──── 1*2*4
   │   └──────── 1*3*4
   └──────────── 2*3*4

Ограничение: нельзя использовать деление (например, общее произведение / nums[i]). И желательно — O(n) время, O(1) дополнительной памяти.

Наивное — O(n²)

def product_except_self(nums):
    result = []
    for i in range(len(nums)):
        product = 1
        for j in range(len(nums)):
            if i != j:
                product *= nums[j]
        result.append(product)
    return result

Два вложенных цикла. Для каждого элемента считаем заново. Медленно.

Почему «через деление» — плохая идея

total = math.prod(nums)
return [total // n for n in nums]   # ❌

Проблема: если в массиве есть 0 — деление на ноль. И даже без нулей в задаче явно сказано «без деления» — это часть условия.

Идея — два прохода: префиксы и суффиксы
В каждой точке i нужны:
произведение всего слева от i
произведение всего справа от i
Перемножим — получим «всё, кроме i».

Первый проход — слева направо, копим произведение всех левее:

nums    = [1, 2, 3, 4]
left    = [1, 1, 2, 6]
           │  │  │  └─ 1*2*3
           │  │  └──── 1*2
           │  └──────── 1
           └────────── ничего слева

Второй проход — справа налево, домножаем на произведение всех правее:

nums          = [1,  2,  3, 4]
после left    = [1,  1,  2, 6]
после right   = [24, 12, 8, 6]
                 │   │   │  └─ 6 * 1 (ничего справа)
                 │   │   └──── 2 * 4
                 │   └──────── 1 * (3*4)
                 └──────────── 1 * (2*3*4)
def product_except_self(nums):
    n = len(nums)
    result = [1] * n

    # left pass
    left = 1
    for i in range(n):
        result[i] = left
        left *= nums[i]

    # right pass
    right = 1
    for i in range(n - 1, -1, -1):
        result[i] *= right
        right *= nums[i]

    return result

O(n) время. И O(1) доп. памяти — массив result не считается, он сам ответ.

🐍Вопросы с собесов -> ProstoPython

🧠 Interview Thinking

Задача
Строка — палиндром (читается одинаково слева и справа), если игнорировать регистр и все небуквенные символы.

"A man, a plan, a canal: Panama"  → True
"race a car"                       → False
" "                                → True

Как думает junior — O(n) время, O(n) память
«Очищу строку, потом переверну и сравню»:

def is_palindrome(s):
    cleaned = "".join(c.lower() for c in s if c.isalnum())
    return cleaned == cleaned[::-1]

Работает. Короткое, читаемое решение — на собесе его примут.
Но если интервьюер скажет «сделай без доп. строки» — нужен другой подход.

Как думает сильный кандидат — два указателя, O(1) памяти
Идея: два указателя — один с начала, второй с конца. Идут навстречу. Пропускаем небуквенные символы. Если буквы (в нижнем регистре) не совпали — не палиндром.

def is_palindrome(s):
    left, right = 0, len(s) - 1
    while left < right:
        while left < right and not s[left].isalnum():
            left += 1
        while left < right and not s[right].isalnum():
            right -= 1
        if s[left].lower() != s[right].lower():
            return False
        left += 1
        right -= 1
    return True

O(n) время, O(1) доп. памяти. Не строим новую строку.

🐍Вопросы с собесов -> ProstoPython

🎭 Red Flag

Открываешь чужой код и видишь:

# Увеличиваем счётчик на 1
counter += 1

# Проходим по списку пользователей
for user in users:
    # Если пользователь активен
    if user.is_active:
        # Отправляем письмо
        send_email(user)

Выглядит «документированно». На деле — это шум, который мешает читать.
Почему это red flag
Эти комментарии не дают никакой информации сверх кода. Любой, кто видит counter += 1, и так знает, что счётчик увеличивается. Комментарий повторяет код словами.

Хуже того:
1. Комментарии устаревают. Логика меняется — комментарий забывают обновить. И вот ты читаешь:

# Возвращаем True, если возраст >= 18
def is_adult(age):
    return age >= 21    # ❗️ изменили, комментарий не тронули

Доверие к комментариям падает. А плохой комментарий хуже отсутствующего — он вводит в заблуждение.

2. Они говорят «что», вместо «почему». Хороший комментарий объясняет причину, которую не видно из кода. Плохой — пересказывает синтаксис.

Как надо
Комментарий должен отвечать на вопрос, который код не объясняет:

# Плохо — пересказ кода
# Сортируем массив
nums.sort()

# Хорошо — объяснение причины
# Сортируем, потому что бинарный поиск ниже требует упорядоченности
nums.sort()
# Плохо
# Если retry_count больше 3, выходим
if retry_count > 3:
    break

# Хорошо
# Лимит ретраев такой же, как у внешнего API — больше нет смысла
if retry_count > 3:
    break

Хороший комментарий объясняет:
почему так сделано (а не «как»)
что важно знать при изменении этого кода
что было попробовано и почему не подошло
связь с внешним миром: тикеты, баги, ограничения API

Альтернатива комментариям — имена
Часто комментарий — это симптом плохого именования:

# было: непонятный код + объяснение
# x — количество дней до дедлайна
x = (deadline - today).days
if x < 7:
    notify(user)

# стало: код объясняет себя
days_until_deadline = (deadline - today).days
if days_until_deadline < 7:
    notify(user)

Хорошее имя переменной заменяет комментарий. Хорошее имя функции — тем более.

🐍Вопросы с собесов -> ProstoPython

🧰 Code Cleanup

Плохой код

if status == "pending" or status == "processing" or status == "queued":
    show_loader()

if user_role == "admin" or user_role == "owner" or user_role == "superuser":
    grant_access()

Работает. Но переменная повторяется в каждом сравнении, оператор == — тоже. Глаза устают.

Чистый вариант

if status in {"pending", "processing", "queued"}:
    show_loader()

if user_role in {"admin", "owner", "superuser"}:
    grant_access()

То же самое, но переменная написана один раз. И сразу видно: проверяем принадлежность к набору.

Почему именно {...} (set), а не [...] или (...)
in работает для всех трёх. Но:
set — проверка за O(1)
tuple / list — проверка за O(n)

На двух-трёх элементах разницы не видно. На десяти и более — set ощутимо быстрее.

# нормально на маленьких наборах
if role in ("admin", "owner"):
    ...

# обязательно set при больших проверках
ALLOWED_ROLES = {"admin", "owner", "superuser", "auditor", "billing", ...}
if role in ALLOWED_ROLES:
    ...

🐍Вопросы с собесов -> ProstoPython

🧠 Interview Thinking

Задача
Дан отсортированный массив (могут быть отрицательные). Вернуть массив квадратов элементов, тоже отсортированный.

nums = [-4, -1, 0, 3, 10]
→ [0, 1, 9, 16, 100]

Как думает junior — O(n log n)
«Возведу в квадрат, потом отсортирую»:

def sorted_squares(nums):
    return sorted(n * n for n in nums)

Работает. Просто. На собесе примут.
Но мы выбрасываем то, что массив уже отсортирован. Снова платим за сортировку «с нуля».

Как думает сильный кандидат — O(n)
Ключевой инсайт: самые большие квадраты — на краях. Минус сильно отрицательное число даёт большой квадрат, плюс сильно положительное — тоже.
Значит, кандидаты на «самый большой квадрат» — это left и right массива. Два указателя с краёв навстречу.
На каждом шаге сравниваем |nums[left]| и |nums[right]|, берём больший в квадрат и кладём в конец результата:

def sorted_squares(nums):
    n = len(nums)
    result = [0] * n
    left, right = 0, n - 1
    pos = n - 1                          # пишем с конца

    while left <= right:
        if abs(nums[left]) > abs(nums[right]):
            result[pos] = nums[left] ** 2
            left += 1
        else:
            result[pos] = nums[right] ** 2
            right -= 1
        pos -= 1

    return result

O(n) время, O(n) на результат (дополнительной памяти кроме результата — нет).

🐍Вопросы с собесов -> ProstoPython

⏱️ Big O Breakdown

def reverse_via_insert(nums):
    result = []
    for n in nums:
        result.insert(0, n)
    return result


nums длины n.

Какая сложность?
A) O(n)
B) O(n log n)
C) O(n²)
D) Amortized O(n)

Правильный ответ: C — O(n²)

Разбор
Цикл крутится n раз — это O(n).
Но list.insert(0, x) — это O(n) для каждого вызова. Когда вставляешь в начало, все остальные элементы сдвигаются на одну позицию вправо. Чем длиннее список, тем больше сдвигов.

шаг 1:  сдвиг 0 элементов
шаг 2:  сдвиг 1 элемента
шаг 3:  сдвиг 2 элементов
...
шаг n:  сдвиг (n-1) элементов

Суммарно: 0 + 1 + 2 + ... + (n-1) ≈ n²/2 операций.
Снаружи код выглядит «один цикл, одна операция». А внутри прячется квадрат.

🐍Вопросы с собесов -> ProstoPython

📈 From O(n²) to O(n)

Задача
Дан список слов. Сгруппировать анаграммы вместе (слова из одних и тех же букв).

["eat", "tea", "tan", "ate", "nat", "bat"]

→ [["eat", "tea", "ate"], ["tan", "nat"], ["bat"]]

Наивное решение — O(n² · k)
Для каждого слова сравниваем со всеми остальными:

def group_anagrams(words):
    groups = []
    used = [False] * len(words)
    for i, w in enumerate(words):
        if used[i]:
            continue
        group = [w]
        for j in range(i + 1, len(words)):
            if not used[j] and sorted(w) == sorted(words[j]):
                group.append(words[j])
                used[j] = True
        groups.append(group)
    return groups

Где n — число слов, k — средняя длина слова. O(n² · k log k) — каждое сравнение через sorted стоит k log k.

Идея — общий ключ для анаграмм
Главный инсайт: у анаграмм есть одинаковая «нормальная форма».
Например — отсортированная строка букв:

"eat" → "aet"
"tea" → "aet"
"ate" → "aet"
"tan" → "ant"

Если использовать эту форму как ключ словаря, группировка становится одним проходом:

from collections import defaultdict

def group_anagrams(words):
    groups = defaultdict(list)
    for w in words:
        key = "".join(sorted(w))
        groups[key].append(w)
    return list(groups.values())

O(n · k log k) время — один проход, в каждой итерации сортировка слова.

Можно ещё лучше — O(n · k)
Заменяем сортировку на подсчёт частот букв. Кортеж из 26 чисел — это однозначная подпись анаграммы:

def group_anagrams(words):
    groups = defaultdict(list)
    for w in words:
        count = [0] * 26
        for ch in w:
            count[ord(ch) - ord("a")] += 1
        groups[tuple(count)].append(w)
    return list(groups.values())

Время — O(n · k). Сортировки нет, только подсчёт.

🐍Вопросы с собесов -> ProstoPython