Как выбрать символ при нескольких максимальных подряд идущих символах?
Что проверяют
Умеете ли вы сначала уточнить условие, а потом писать код. Задача на серии одинаковых символов решается за один проход, а вся соль в правиле выбора при ничьей: первый, последний, минимальный по алфавиту или все сразу. Следом обычно спрашивают сложность и просят переписать решение под другое правило.
Как отвечать
Начните с вопроса интервьюеру, какой символ вернуть при равенстве серий. Затем опишите проход:
- два счётчика: длина текущей серии и лучшая найденная. Когда символ меняется, текущая серия закрывается и сравнивается с лучшей;
- правило ничьей в одном знаке: строгое
>оставляет первый из равных максимумов,>=даёт последний. Для алфавитного порядка сравнивайте пару(длина, -ord(символ))или явно проверяйте символ при равной длине; - последняя серия: после цикла её нужно сравнить ещё раз, иначе строка
"abccc"вернёт неверный ответ; - краевые случаи: пустая строка (вернуть
Noneили броситьValueError, договоритесь заранее), строка из одного символа, регистр букв.
Сложность O(n) по времени и O(1) по памяти. В Python короче через itertools.groupby: max(((k, len(list(g))) for k, g in groupby(s)), key=lambda p: p[1]) вернёт первую из самых длинных серий, потому что max при равенстве ключей оставляет первый элемент.
Для data-ml полезно показать и векторный вариант на pandas: та же задача встречается в данных, например самая длинная серия одинаковых статусов в логах. Номер серии даёт grp = (s != s.shift()).cumsum(), затем s.groupby(grp).agg(['first', 'size']) и выбор строки с максимальным size.
Где спотыкаются
Берут Counter и считают общее число вхождений символа. Это другая задача: в строке "abab" у a два вхождения, но самая длинная серия равна единице.
Не проверяют серию после цикла или путают > и >=, из-за чего правило ничьей работает не так, как заявлено вслух.
Пишут вложенный цикл, который для каждой позиции заново считает длину серии. Это O(n²) там, где хватает одного прохода, и интервьюер обязательно спросит, почему.