Напишите генератор, который развернет список любой вложенности в плоскую последовательность

ЗадачаMiddleЧасто

Проверила команда СопроводОбновлено

Короткий ответ

Пройдите по элементам списка: если элемент сам список или кортеж, передайте его в тот же генератор через yield from, иначе отдайте элемент через yield. Пустые списки ничего не отдадут и пропадут сами. Строку не проверяйте вопросом «итерируема ли она»: она состоит из строк и уведет рекурсию в бесконечность. Память растет с глубиной вложенности, а не с длиной списка.

Почему этот вопрос задают

Задача проверяет сразу рекурсию, генераторы и внимание к типам. Дерево категорий, вложенные меню и JSON из внешних API приходят именно в таком виде, и разворачивать их приходится часто.

Условие задачи

Каталог строительного магазина хранит категории деревом: подкатегории лежат во вложенных списках, глубина не ограничена. Напишите генератор flatten(items), который отдает названия категорий по порядку в одну плоскую последовательность. Пустые подкатегории пропускайте, строки не разбивайте на буквы. Проверьте на каталоге ["Инструменты", ["Дрели", ["Перфораторы"]], [], "Краски"]: ожидается «Инструменты / Дрели / Перфораторы / Краски».

Как подойти к решению

  1. Пройдите по элементам списка циклом for и проверьте тип каждого
  2. Передайте вложенный список или кортеж в тот же генератор через yield from
  3. Отдайте через yield все остальное: строки, числа, объекты
  4. Проверьте пустые списки и строки: обход не должен на них ломаться
  5. Покажите ленивость: возьмите два первых значения через next

Решение

Каждое значение генератор отдает сразу, без промежуточных списков: два вызова next прошли только начало каталога. Пустые списки и кортежи дают пустой результат. Время O(n × d): значение поднимается через цепочку из d вложенных генераторов, и для каталога в 3–4 уровня это почти O(n). Память O(d) на эту цепочку.

Python
def flatten(items):
    for item in items:
        if isinstance(item, (list, tuple)):
            yield from flatten(item)
        else:
            yield item


catalog = ["Инструменты", ["Дрели", ["Перфораторы"]], [], "Краски"]
print(" / ".join(flatten(catalog)))
names = flatten(catalog)
print(next(names), next(names))
print(list(flatten([[], [[]], ()])))
Вывод
Инструменты / Дрели / Перфораторы / Краски
Инструменты Дрели
[]

Что спросят следом

  • Что будет, если вложенность больше тысячи уровней?

  • Как разворачивать любые итерируемые объекты, а не только списки?

  • Чем yield from отличается от цикла for x in flatten(item): yield x?

Доступно по подписке

Ответы на эти вопросы

Частые ошибки

  • «Проверю, итерируемый ли элемент, через iter(item)»

    Строка итерируема, ее символ тоже строка, и такой генератор уйдет в рекурсию до RecursionError. Проверяйте конкретные типы или исключайте str и bytes явно

  • «Склею все через sum(catalog, [])»

    sum снимает только один уровень и падает с TypeError, если рядом со списками лежат строки. К тому же каждое сложение копирует список, и время растет квадратично

  • «Проверю через type(item) == list»

    Такая проверка пропустит подклассы списка и кортежи. Берите isinstance с кортежем типов: isinstance(item, (list, tuple))

  • «Генератор и функция со списком — одно и то же, просто синтаксис другой»

    Генератор отдает значения по одному и не держит весь результат в памяти. Его можно остановить после первых значений, и остальная часть дерева не будет пройдена

Сигналы для интервьюера

Сильный ответ

Сам называет ловушку со строками, проверяет пустые списки и предлагает обход без рекурсии для глубоких деревьев

Тревожный сигнал

Пишет верный генератор, но на вопрос, что делает yield from, отвечает только «так короче»

Красный флаг

Вынимает элементы из исходного каталога через pop во время обхода и портит данные вызывающего кода

Как еще могут спросить

  • Как сделать плоский список из вложенного в Python?
  • Напишите функцию flatten для списка произвольной вложенности
  • Как развернуть многоуровневый список с помощью yield from?
  • Как превратить список списков любой глубины в одну последовательность?

Похожие вопросы

ЗнаниеMiddleЧасто

Чем генератор отличается от итератора в Python?

Итератор — любой объект с методами __iter__ и __next__: next отдает следующий элемент и в конце бросает StopIteration. Генератор — короткий способ получить итератор: функция с yield возвращает объект, который реализует этот протокол сам. Генератор ленивый, считает значение по запросу и проходится один раз. Класс-итератор пишут, когда нужны свои методы и явное состояние.

  • Python
  • генераторы
240
ЗнаниеSeniorИногда

Что делают yield from и send в генераторе и как подгенератор возвращает значение?

send(value) возобновляет генератор и делает value результатом выражения yield, на котором тот стоял. Первым вызовом идет next или send(None): до первого yield принять значение негде. yield from sub делегирует работу подгенератору, пробрасывает ему next, send и исключения. Значение из return подгенератора становится результатом всего выражения yield from.

  • Python
  • генераторы
187
ЗадачаMiddleЧасто

Напишите декоратор retry, который повторит вызов функции до N раз, если она упала с ошибкой

Декоратор с параметрами — это функция, которая возвращает декоратор: retry(times) отдает decorator, а decorator(func) отдает wrapper. В wrapper сделайте times - 1 попыток внутри try, ловите только переданные исключения и ждите delay между попытками. Последнюю попытку вызовите вне try, чтобы ее ошибка дошла до вызывающего кода. Оберните wrapper в functools.wraps.

  • Python
  • декораторы
252
ЗадачаJuniorЧасто

Напишите функцию, которая вернет три самых частых слова в тексте без учета регистра и знаков препинания

Приведите текст к нижнему регистру и выньте слова регулярным выражением \w+: так запятые и восклицательные знаки не прилипнут к словам. Посчитайте слова через collections.Counter. Для трех лидеров отсортируйте пары по ключу (-count, word): сначала частота по убыванию, при равенстве алфавит. Подсчет идет за O(n), сортировка разных слов за O(m log m).

  • Python
  • строки
  • коллекции
223

Частые вопросы по теме

Короткие ответы на частые вопросы по этой теме.

itertools.chain.from_iterable разворачивает ровно один уровень: для списка списков это лучший выбор. Для произвольной глубины его не хватит, нужна рекурсия или стек. Скажите это интервьюеру, если он спросит о стандартной библиотеке.

Начните с рекурсии: она короткая и показывает понимание yield from. Потом сами назовите ограничение по глубине и предложите стек как следующий шаг. Если интервьюер попросит, вторая версия займет еще 8–10 строк.

Разницу генератора и итератора, yield и yield from, генераторные выражения, next и StopIteration. Решите две-три задачи: разворот вложенного списка, чтение большого файла построчно, бесконечная последовательность чисел Фибоначчи.

Общие вопросы на интервью

Общий вопросС опытомЧасто

Почему вы хотите работать у нас?

Назовите две-три причины, которые связывают вас именно с этой компанией: продукт, задачи, масштаб, команда. Каждую подкрепите фактом, который нашли сами: новость, проект, текст вакансии, свой опыт клиента. Потом покажите, что принесете со своей стороны. Слова о стабильности и известном бренде подходят любой компании, поэтому на них ответ не держится.

  • мотивация
  • о компании
290
Общий вопросБез опытаЧасто

Какие у вас сильные стороны?

Хватит двух-трех сильных сторон, которые нужны на этой работе, если к каждой есть пример: что сделали и какой был результат. Берите качества из текста вакансии, а не из списка «ответственный, коммуникабельный». Без опыта примеры ищите в учебе, практике и подработке. Говорите спокойно, без лишней скромности и без хвастовства.

  • сильные стороны
  • без опыта
276
Общий вопросБез опытаЧасто

Кем вы видите себя через 5 лет?

Расскажите, какие задачи хотите решать через несколько лет и чему для этого научитесь. Свяжите план с тем, что дает эта компания, и покажите первый шаг, который уже сделали. Точную должность называть не обязательно. Важнее, чтобы план был реальным и вел через эту работу, а не мимо нее.

  • мотивация
  • карьерные планы
289
ИсторияС опытомЧасто

Расскажите о конфликте с коллегой: из-за чего он возник и как вы его решили?

Расскажите один реальный конфликт по рабочему вопросу: из-за чего разошлись, чего хотела каждая сторона и как вы договорились. Говорите спокойно, без оценок коллеги. Покажите, что вы искали решение, где-то уступили и сохранили рабочие отношения. Закончите результатом и тем, что теперь делаете, чтобы похожий спор не повторился.

  • конфликты
  • работа в команде
252
ИсторияС опытомЧасто

Каким профессиональным достижением вы гордитесь больше всего?

Назовите одно достижение, близкое к задачам новой работы, и расскажите его как историю: какая была проблема, что сделали лично вы и что изменилось в цифрах. Сильнее всего звучит результат, который держится и после вас: новый порядок работы, правило, схема. Если результат общий, прямо скажите, какая часть в нем ваша.

  • достижения
  • результат в цифрах
276
Общий вопросБез опытаЧасто

Опыта работы еще нет, а интервьюер просит рассказать о себе: что вы скажете?

Начните с того, кто вы сейчас и на какую работу пришли. Вместо стажа расскажите об учебе, практике и подработке, которые похожи на задачи вакансии, и назовите один результат с цифрой. Закончите тем, почему хотите начать карьеру именно здесь. Уложитесь в одну-две минуты и не пересказывайте резюме по порядку.

  • о себе
  • без опыта
244

Вопросы руководителю на интервью

ИсторияРуководительЧасто

Как вы делегируете задачи: что отдаете команде, а что оставляете себе?

Назовите свое правило: что вы отдаете команде и что оставляете себе, и покажите его на одной задаче. Расскажите, кому и почему передали, какие полномочия и рамки дали, как проверяли без мелкого контроля. Закончите честным итогом: что получилось хуже или медленнее, чем у вас, и что вы выиграли.

  • делегирование
  • команда
255
КейсРуководительЧасто

Два сотрудника вашей команды месяц не разговаривают друг с другом, и общий отчет уже сорвал срок — что сделаете?

Поговорите сначала с каждым по отдельности: что случилось, с чего началось и что мешает работать. Потом соберите обоих вместе и обсуждайте работу: кто за какие данные и шаги отвечает. За такой ссорой часто стоит размытая ответственность. Запишите договоренности, назовите новый срок для сорванного отчета и через пару недель проверьте, что все работает.

  • конфликт
  • ответственность
242
ИсторияРуководительЧасто

Расскажите о сотруднике, которого вы вырастили: каким он пришел и чего добился?

Возьмите одного человека и покажите путь: каким он пришел, какие задачи вы ему давали по нарастающей и чем помогали, кем он стал и за какой срок. Назовите цифру роста: новая должность, своя зона, люди в подчинении. Скажите честно, где он вырос сам, а где сработали ваши решения.

  • развитие сотрудников
  • наставничество
303
ИсторияРуководительЧасто

Расскажите о цели, которую ваша команда не выполнила: когда вы это поняли и что сделали?

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

  • цели
  • провал
241
Общий вопросРуководительЧасто

Как вы измеряете результат своей команды?

Назовите два-три показателя, которые отражают то, ради чего существует ваша команда, и их текущие цифры. Добавьте показатель качества, который не дает гнаться за одним числом. Скажите, как часто смотрите на цифры, кто их видит и какое решение вы приняли по ним в последний раз.

  • показатели
  • цели
216
ИсторияРуководительЧасто

Расскажите, как вы разложили цель компании на задачи для своей команды

Возьмите одну цель компании с цифрой и сроком и покажите, как вы ее разбили: на какие части, по какому признаку, какие личные цели получил каждый сотрудник. Расскажите, как следили за ходом и что меняли по дороге. Закончите итогом план-факт честно, даже если цель выполнена не целиком.

  • цели
  • планирование
227