Символ с максимальной длиной подряд
Дана строка. Нужно вернуть символ, который встречается подряд максимальное число раз.
Важно: речь не про общую частоту символа в строке, а именно про самый длинный непрерывный блок.
Если максимальный блок есть у нескольких символов, верните символ из самого раннего такого блока.
Сигнатура
def max_consecutive_char(s: str) -> str:Примеры
max_consecutive_char("aaabbccccd") -> "c"
max_consecutive_char("ab") -> "a"Решение прямо на странице
Напишите код, запустите проверки и только потом открывайте разбор.
Нажмите «Запустить проверки» или Ctrl+Enter.
Показать разбор
Идея решения
Подход: идем по строке и поддерживаем текущий блок одинаковых символов.
Когда символ меняется, начинаем новый блок длины 1. Если текущая длина стала больше лучшей, обновляем лучший символ и длину.
Для пустой строки возвращаем пустую строку.
Эталонный код
def max_consecutive_char(s: str) -> str:
if not s:
return ''
best_char = s[0]
best_len = 1
cur_char = s[0]
cur_len = 1
for ch in s[1:]:
if ch == cur_char:
cur_len += 1
else:
cur_char = ch
cur_len = 1
if cur_len > best_len:
best_len = cur_len
best_char = cur_char
return best_charПодматрица с максимальным средним
Дана матрица целых чисел и фиксированный размер подматрицы height x width.
Нужно найти подматрицу такого размера с максимальным средним значением и вернуть координаты ее левого верхнего угла: [row, col].
Так как размер окна фиксирован, максимальное среднее эквивалентно максимальной сумме.
Сигнатура
def max_average_submatrix(matrix: list[list[int]], height: int, width: int) -> list[int]:Решение прямо на странице
Напишите код, запустите проверки и только потом открывайте разбор.
Нажмите «Запустить проверки» или Ctrl+Enter.
Показать разбор
Идея решения
Строим двумерные префиксные суммы pref, где pref[i + 1][j + 1] хранит сумму прямоугольника от (0, 0) до (i, j).
Сумма окна считается через четыре значения префикса. Перебираем все возможные левые верхние углы и выбираем максимум.
Эталонный код
def max_average_submatrix(matrix: list[list[int]], height: int, width: int) -> list[int]:
rows = len(matrix)
cols = len(matrix[0])
pref = [[0] * (cols + 1) for _ in range(rows + 1)]
for i in range(rows):
row_sum = 0
for j in range(cols):
row_sum += matrix[i][j]
pref[i + 1][j + 1] = pref[i][j + 1] + row_sum
best_sum = None
best_pos = [0, 0]
for r in range(rows - height + 1):
for c in range(cols - width + 1):
total = (
pref[r + height][c + width]
- pref[r][c + width]
- pref[r + height][c]
+ pref[r][c]
)
if best_sum is None or total > best_sum:
best_sum = total
best_pos = [r, c]
return best_posПодматрица с максимальным размахом
Дана матрица целых чисел и размеры окна height x width.
Нужно найти левый верхний угол подматрицы фиксированного размера, где размах значений максимален:
range = max(window) - min(window)Если оптимальных окон несколько, верните самое раннее по обходу сверху вниз, слева направо.
Сигнатура
def max_range_submatrix(matrix: list[list[int]], height: int, width: int) -> list[int]:Верните [row, col] — индекс верхнего левого угла.
Решение прямо на странице
Напишите код, запустите проверки и только потом открывайте разбор.
Нажмите «Запустить проверки» или Ctrl+Enter.
Показать разбор
Подсказки
- Разделите 2D-окно на два 1D прохода
Сначала горизонтальные min/max, затем вертикальные min/max по уже сжатым значениям.
- Tie-break
Обновляйте ответ только при строгом улучшении, тогда первое найденное окно останется ответом.
Идея решения
Наивно для каждого окна искать минимум и максимум за O(height * width), но это быстро становится дорого.
Оптимизация делается двумя проходами monotonic queue:
- Для каждой строки посчитать минимум и максимум на каждом горизонтальном окне ширины
width. - Для каждого получившегося столбца посчитать минимум и максимум на вертикальном окне высоты
height. - Получить range для каждого верхнего левого угла и выбрать максимум с детерминированным tie-break.
Эталонный код
def max_range_submatrix(matrix: list[list[int]], height: int, width: int) -> list[int]:
from collections import deque
def sliding_extreme(values: list[int], window: int, want_max: bool) -> list[int]:
dq: deque[int] = deque()
result: list[int] = []
for i, value in enumerate(values):
while dq and dq[0] <= i - window:
dq.popleft()
while dq:
tail = values[dq[-1]]
if (want_max and tail <= value) or (not want_max and tail >= value):
dq.pop()
else:
break
dq.append(i)
if i >= window - 1:
result.append(values[dq[0]])
return result
if not matrix or not matrix[0]:
return [0, 0]
rows = len(matrix)
cols = len(matrix[0])
if height > rows or width > cols:
return [0, 0]
row_mins = [sliding_extreme(row, width, False) for row in matrix]
row_maxs = [sliding_extreme(row, width, True) for row in matrix]
window_cols = cols - width + 1
range_by_position = [[0] * window_cols for _ in range(rows - height + 1)]
for col in range(window_cols):
min_column = [row_mins[row][col] for row in range(rows)]
max_column = [row_maxs[row][col] for row in range(rows)]
window_mins = sliding_extreme(min_column, height, False)
window_maxs = sliding_extreme(max_column, height, True)
for row in range(rows - height + 1):
range_by_position[row][col] = window_maxs[row] - window_mins[row]
best_range = None
best_pos = [0, 0]
for row in range(rows - height + 1):
for col in range(window_cols):
current_range = range_by_position[row][col]
if best_range is None or current_range > best_range:
best_range = current_range
best_pos = [row, col]
return best_posСложность добавления в начало и конец Python list
За сколько работает добавление элемента в начало и в конец Python list? Почему append в конец обычно O(1), но не всегда строго O(1)?
Сначала проговорите ответ вслух или тезисами.
Формулы, план решения, риски и примеры.
Откройте разбор только после своей попытки.
Показать разбор
Короткий ответ
Вставка в начало list стоит O(n), потому что элементы нужно сдвинуть. append в конец - амортизированно O(1), но расширение внутреннего буфера иногда стоит O(n).
Подробный разбор
Python list в CPython реализован как динамический массив ссылок. Добавление в начало требует освободить позицию 0 и сдвинуть все существующие элементы, поэтому это O(n).
Добавление в конец обычно кладет ссылку в уже выделенную свободную ячейку, поэтому стоит O(1). Когда capacity заканчивается, list выделяет новый больший буфер и копирует туда старые ссылки. Такой отдельный append стоит O(n), но средняя стоимость по длинной серии append остается амортизированно O(1).
Сложность вставки строк в set и плохой hash
За сколько вставить n различных строк длины k в Python set? Что изменится, если hash для всех объектов возвращает одно и то же значение?
Сначала проговорите ответ вслух или тезисами.
Формулы, план решения, риски и примеры.
Откройте разбор только после своей попытки.
Показать разбор
Короткий ответ
Обычно получается O(n * k): hash строки считается по символам, а вставка в hash table амортизированно O(1). При константном hash серия вставок деградирует к квадратичной.
Подробный разбор
Для обычных строк Python должен вычислить hash по символам, поэтому первая вставка строки длины k включает O(k) на хеширование. Сама операция set.add в среднем амортизированно O(1), если hash хорошо распределяет элементы.
Если сделать hash константным, все элементы попадают в один кластер коллизий. Тогда при вставке нового элемента нужно проверять уже лежащие элементы с тем же hash, и суммарно по n вставкам получается квадратичная деградация. Для строк и пользовательских объектов при коллизиях также важна стоимость equality-сравнений.
Как устроены float и зачем нужен bfloat16
Как устроены числа с плавающей точкой? Чем bfloat16 отличается от float16 и почему его используют в нейросетях?
Сначала проговорите ответ вслух или тезисами.
Формулы, план решения, риски и примеры.
Откройте разбор только после своей попытки.
Показать разбор
Короткий ответ
Float хранит знак, экспоненту и мантиссу. bfloat16 экономит память как 16-битный формат, но сохраняет широкий диапазон FP32 за счет 8-битной экспоненты.
Подробный разбор
Число с плавающей точкой представляется как sign, exponent и significand/mantissa. Экспонента задает масштаб, мантисса - значащие биты. FP32 имеет 1 бит знака, 8 бит экспоненты и 23 бита мантиссы.
bfloat16 использует 16 бит, но оставляет экспоненту шириной как у FP32: 1 бит знака, 8 бит экспоненты и 7 бит мантиссы. Он менее точен по мантиссе, зато лучше переносит широкий диапазон активаций и градиентов. В ML это удобно для обучения и инференса: меньше память и выше throughput, при этом меньше проблем с overflow/underflow, чем у FP16.
Потоки, процессы, GIL и обмен данными
Чем отличаются потоки и процессы? Что такое GIL в CPython, когда нужны синхронизация и IPC?
Сначала проговорите ответ вслух или тезисами.
Формулы, план решения, риски и примеры.
Откройте разбор только после своей попытки.
Показать разбор
Короткий ответ
Процессы имеют отдельную память, потоки внутри процесса делят память. GIL ограничивает одновременное исполнение Python bytecode, но не отменяет race conditions и синхронизацию.
Подробный разбор
Процесс - более тяжелая единица выполнения с отдельным адресным пространством. Поток легче: он живет внутри процесса и разделяет память, файловые дескрипторы и состояние процесса, но имеет свой stack.
GIL в CPython - глобальная блокировка, которую должен держать поток, исполняющий Python bytecode. Из-за этого CPU-bound Python-код обычно не ускоряется на нескольких потоках. Потоки полезны для I/O-bound задач, потому что GIL может отпускаться на ожидании I/O и в некоторых C-расширениях.
GIL не делает бизнес-инварианты атомарными. Для shared mutable state нужны Lock, Queue или другие примитивы синхронизации. Между процессами нельзя передать обычную Python-ссылку: нужны pipes, queues, sockets, shared memory, файлы, Redis или другой IPC/transport.
Имена, ссылки, циклические ссылки и mutable defaults в Python
В Python есть код со списками, ссылками на объекты, циклическими ссылками и mutable default arguments. Как пройтись по нему и объяснить, что останется в памяти и почему?
Сначала проговорите ответ вслух или тезисами.
Формулы, план решения, риски и примеры.
Откройте разбор только после своей попытки.
Показать разбор
Короткий ответ
В CPython обычные объекты освобождаются reference counting, но циклы не разбираются одним счетчиком ссылок. Для недостижимых циклов нужен cyclic GC. Mutable default argument создается один раз при определении функции, поэтому список переиспользуется между вызовами без явного аргумента.
Подробный разбор
В CPython у каждого объекта есть счетчик ссылок. Когда счетчик падает до нуля, объект можно сразу освободить. Это хорошо работает для обычных ацикличных графов объектов.
Проблема возникает, когда объекты ссылаются друг на друга: например, список a содержит ссылку на b, а b содержит ссылку на a. Если внешние переменные перестали указывать на этот цикл, счетчики ссылок внутри цикла все равно не равны нулю, потому что объекты держат друг друга. Reference counting сам по себе такой цикл не освободит.
Для этого в CPython есть cyclic garbage collector. Он периодически ищет группы контейнерных объектов, которые достижимы только друг из друга, но недостижимы из корней программы. Такие циклы можно собрать. При этом освобождение не обязано случиться ровно в момент зануления внешней ссылки.
Mutable default argument — другой классический runtime-подвох. Значение аргумента по умолчанию вычисляется один раз при создании функции, а не при каждом вызове. Поэтому функция вида def f(x=[]): x.append(1); return x будет переиспользовать один и тот же список во всех вызовах без явного x. Правильный паттерн — использовать None как sentinel и создавать новый список внутри функции.
Типичные ошибки
- Сказать, что любой объект удаляется сразу после присваивания переменной в None.
- Забыть, что циклические ссылки могут держать ненулевые reference counts.
- Думать, что default argument создается заново при каждом вызове функции.
Как сказать на собеседовании
- Разделяй reference counting и cyclic GC: это разные механизмы.
- Для mutable defaults сразу называй паттерн с None и созданием объекта внутри функции.