Формальные языки
Формальные языки на собеседовании (FAANG)
Google L5 system design: 'Спроектируйте query language для distributed key-value store'. Правильный ответ начинается с иерархии Хомского: регулярный для simple lookups, CFG для условных запросов. Знание теории дает структурный ответ там, где другие угадывают.
- LeetCode 10 (Regex Matching): NFA через DP - появляется в Google, Meta и Amazon screen
- Amazon system design: workflow state machine - statechart с явными переходами
- Meta infrastructure: query language для logging - нужно знать трadeoffs Тьюринг-полный vs ограниченный
- Google Research: доказательства NP-hardness для scheduling задач в интервью
Автоматы на собеседовании
Вопросы по автоматам встречаются в Google и Meta в форме задач на регулярные выражения, лексеры и state machines. Реже - явный вопрос 'постройте DFA для этого языка'.
- LeetCode 10 (Regex matching): NFA через DP - типичный Google L5+ вопрос
- LeetCode 44 (Wildcard matching): DFA с backtracking или DP - аналог
- Valid number (LeetCode 65): построить explicit DFA для числа - чистый автомат
- IP Address validating: простой DFA, встречается в Meta screen
- State machine для workflow: Amazon system design часто просит statechart
Почему задача regex matching решается через DP, а не построением явного NFA?
Теория сложности на собеседовании
Теория сложности на FAANG-собеседовании - это system design вопросы ('почему здесь не используется алгоритм X?') и вопросы о сложности конкретных задач. Прямых теоретических вопросов меньше, но они есть в research роли.
- P vs NP: уметь объяснить за 30 секунд без жаргона - обязательно для L6+
- NP-completeness: знать 5-6 примеров и уметь говорить об аппроксимациях
- Reduction: знать как доказать что задача NP-hard через reduction к SAT или 3-SAT
- Undecidability: понимать почему некоторые static analysis задачи undecidable (Rice)
- Halting problem: практическое следствие - нельзя статически проверить все бесконечные циклы
Как объяснить P vs NP за 30 секунд без теоретических терминов?
Дизайн языков: вопросы в system design
System design вопросы в Amazon и Google иногда требуют спроектировать DSL или query language. Здесь знание теории языков даёт конкретные преимущества.
Почему SQL-оптимизатор может переставлять WHERE условия, а Python-интерпретатор нет?
Доказательства и ловушки
На research-уровне собеседованиях (Google Research, DeepMind, Meta AI Research) просят набросать доказательства. Важно знать стандартные техники и типичные ловушки.
- Ловушка: 'exponential' не значит 'NP-hard' - есть задачи exp, которые не NP-complete
- Ловушка: NP-hard != NP-complete (NP-hard может быть вне NP, например PSPACE-hard)
- Ловушка: reduce FROM простой задачи TO сложной (не наоборот) чтобы доказать hard
- Ловушка: 2-SAT in P, 3-SAT NP-complete - знать эту границу
- Ловушка: co-NP != NP (предположительно), co-NP-complete != NP-complete
Как доказать NP-hardness новой задачи B через reduction от 3-SAT?
Итоги
- Автоматы: regex matching как implicit NFA через DP - LeetCode Hard, Google классика
- Сложность: P vs NP за 30 секунд + знать 5-6 NP-complete примеров
- Дизайн языков: иерархия Хомского структурирует выбор парсера и оптимизатора
- Доказательства: pumping lemma, diagonalization, reduction - три стандартные техники
Связанные темы
Интервью-вопросы охватывают весь курс формальных языков:
- Конечные автоматы — Regex matching (LeetCode 10), IP validation, number parsing - implicit DFA/NFA
- NP-полнота — Scheduling, packing, partitioning задачи - доказательство hardness через reduction
- Теорема Райса — Static analysis и linter не могут быть полными - undecidability ограничивает tooling
- Parser combinators — Дизайн DSL: выбор между regex, CFG parser и full language определяет оптимизируемость
Вопросы для размышления
- Как объяснить интервьюеру разницу между 'наш алгоритм NP-hard' и 'наша задача NP-hard'?
- Почему GraphQL намеренно не Тьюринг-полный и какие преимущества это даёт серверу?
- Как теорема Райса объясняет почему TypeScript не может полностью доказать отсутствие runtime ошибок?