## Условие Дана строка `s` и словарь слов `wordDict`. Определи, можно ли разбить `s` на последовательность слов из словаря (без пробелов в `s`, слова из словаря можно использовать многократно). **Формат входа:** - `s` — строка из строчных латинских букв, $1 \leq len(s) \leq 300$. - `wordDict` — список уникальных строк, $1 \leq len(wordDict) \leq 1000$, $1 \leq len(wordDict[i]) \leq 20$. **Формат выхода:** - `True` / `False`. **Пример 1:** ``` Вход: s = "leetcode", wordDict = ["leet", "code"] Выход: True ``` Объяснение: `"leet" + "code" = "leetcode"`. **Пример 2:** ``` Вход: s = "applepenapple", wordDict = ["apple", "pen"] Выход: True ``` Объяснение: `"apple" + "pen" + "apple"`. **Пример 3:** ``` Вход: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"] Выход: False ``` **Ограничения:** - Наивный backtracking $O(2^n)$ — TLE. Нужна DP / memoization.

Вопрос с собеседования аналитика по теме «Алгоритмы».

Разбор ответа

Получить доступ к ответам — все вопросы →

Что дальше

• Раздел практики →
• Все 3000+ вопросов с разбором →

Похожие вопросы из категории «Алгоритмы»

• Дан массив [5, 2, 8, 1, 9]. Нужно отсортировать без встроенного sort(). Самый простой алгоритм — bubble sort. Реализуй на Python, разбери worst/avg/best case. Где bubble sort реально применяется (хинт: Timsort использует его как fallback на коротких подмассивах)?
• Тебе на собесе дают массив на ~50 элементов почти отсортированный (последние 3 элемента не на месте) и просят отсортировать максимально быстро. Какой алгоритм выберешь и почему insertion sort даст O(n) в этом случае? Реализуй и покажи где Python Timsort использует insertion как часть алгоритма.
• Тебе задают вопрос: «У меня quick sort работает за O(n log n) на random data, но на отсортированном входе тормозит. Почему?» Объясни worst case O(n²) и причину. Какие 3 техники защищают (random pivot, median-of-three, introsort)? Реализуй quick sort с random pivot и обоснуй стабильность.
• Дан массив на 10M элементов которые не помещаются в RAM. Тебя просят отсортировать их на диске (external sort). Какой алгоритм базовый? Реализуй classical merge sort и объясни почему он подходит для external sort (chunks + merge), стабилен, параллелизуется. Сравни с quick sort в этом сценарии.
• У тебя приоритетная очередь задач (job scheduler). Тебе нужно постоянно вытаскивать самую важную и добавлять новые. Какая структура подходит за O(log n) на каждую операцию? Реализуй min-heap (приоритет = меньшее число) через heapq. Покажи top-K largest и median maintenance.
• Дан отсортированный массив на 1M элементов и target. Linear search будет O(n) = слишком медленно. Реализуй binary search за O(log n). Бонус: какая граница (lo<hi vs lo<=hi) корректна? Покажи bisect.bisect_left и bisect_right в Python. Когда применим binary search «по ответу»?
• Тебя просят объяснить как работает Python dict под капотом. Какая средняя/худшая сложность? Расскажи про collision resolution: chaining (linked list в bucket) vs open addressing (linear probing). На каком load factor Python ресайзит (хинт: ~2/3)? Что такое hash flooding attack?
• Дан невзвешенный граф (список друзей в соцсети). Найди кратчайший путь от пользователя A до пользователя B. Если пути нет — верни -1. Восстанови сам путь (последовательность вершин).

SQL-задачи по теме

• Домены email и их частота