Здравствуйте, мои маленькие любители DS/ML. Сегодня поговорим про то, как мой старый школьный друг проходил собеседование в зеленую компанию. Материал вполне себе исчерпывающий и полезный. Какие то вещи я видел впервые. # Алгосы в Сбере — что спрашивали на собесе ## Знакомство Короткий спич про себя и опыт. ## Максимальная серия одинаковых символов Задача: дана строка, найти символ, который встречается подряд максимальное число раз. Пример: bbccccbbbdd -> c ## Line reflection Я сказал, что решал эту задачу “тысячу раз”, поэтому мне дали другую. Иначе собес мог бы закончиться минут за 20–25. ## Матрица nm -> подматрица n’m’ с максимальным средним n’ и m’ даны. Нужно найти подматрицу фиксированного размера с максимальным average (эквивалентно — с максимальной суммой, потому что размер фиксированный). Я предложил решение через одномерные префиксные суммы по строкам. Оно получается неоптимальным в случае, когда подматрица по сути “вырождается в столбец”. До двумерных префиксных сумм на собесе не дошёл. ## Вопросы по Python а) За сколько работает добавление n строк длины k в set() б) Куча вопросов на мутабельность/иммутабельность и ссылки/GC. Примеры: - a = 1; b = a; a += 1. Чему равно b? - a = [1, 2], b = [a], a[0] = b. Когда (после какой строчки) сборщик мусора в теории может удалить b? # Запись “как есть” (то, что писал себе) ## Максимальная серия символов (код) Дана строка, необходимо найти символ, который встречается подряд максимальное число раз. Пример: bbccccbbbdd -> c `python def max_count(s: str) -> str: if len(s) == 1: return s mx = 1 cur_ans = s last_seen = s cur_cnt = 1 for c in s[1:]: if c == last_seen: cur_cnt += 1 else: last_seen = c cur_cnt = 1 if cur_cnt > mx: mx = cur_cnt cur_ans = last_seen return cur_ans Подматрица с максимальным средним (код) Дана матрица A размера hw, элементы int32. Нужно найти подматрицу размера khkw, в которой среднее значение максимально (то же самое, что максимальная сумма). Мой набросок: префиксные суммы по строкам, дальше перебор по всем позициям и суммирование по kh строкам. python def segment_sum(pref: list[int], l: int, r: int) -> int: return pref[r + 1] - pref[l] def max_submatrix(A: list[list[int]], w: int, h: int, kw: int, kh: int) -> tuple[int, int]: pref_sums = [[] for _ in range(h)] for i, row in enumerate(A): pref_sum = (w + 1) for j, elem in enumerate(row): pref_sum[j + 1] = pref_sum[j] + elem pref_sums[i] = pref_sum mx = float("-inf") ans = (-1, -1) for y in range(h - kh + 1): for x in range(w - kw + 1): sm = sum(segment_sum(pref_sums[y + i], x, x + kw - 1) for i in range(kh)) if sm > mx: mx = sm ans = (y, x) return ans # память: O(wh) на префиксы # время: O((h-kh+1)(w-kw+1)kh) Line reflection (вертикальная ось симметрии) Дан массив точек с целочисленными координатами (x, y). Нужно понять, существует ли вертикальная прямая x = x0, делящая точки на 2 множества, симметричные относительно этой прямой. Идея: берём xmin и xmax по всем точкам кандидат на ось: x0 = (xmin + xmax) / 2 для каждой точки (x, y) должна существовать точка (x’, y) такая, что x + x’ = xmin + xmax Python-часть (что вспоминалось) Про сложность set: “за сколько отработает добавление n одинаковых строк длины k в set()” Про float: 2.0100 == 2.0100 + 1 Про with/open: with open(...) as f: ... когда реально вызывается close() Про MRO/наследование: python class A: def hello(self): print("A") class B(A): def hello(self): print("B") class C(A): def hello(self): print("C") class D(B, C): pass d = D() d.hello() Про ссылки / мутабельность / сборщик мусора: a = [] b = a a = 0 a = b = a a = 0 b = 0 a = b = [a] a = b a = 0 b = 0