День пятьсот шестьдесят шестой. #ЗадачиНаСобеседовании
Топ 10 Умений Которые Понадобятся на Собеседовании
На собеседовании вам могут как задать самые разные вопросы по теории, так и дать практическое задание. Некоторые из них я уже приводил на канале: 1, 2, 3, 4.
Заучить их все просто нереально. Но большинство из них тестирует одно из следующих базовых умений, которым должен обладать каждый «уважающий себя» программист.

1. Двоичный (бинарный) поиск — классический алгоритм поиска элемента в отсортированном массиве, использующий дробление массива на половины. Используется не только в элементарном нахождении элемента в отсортированном массиве. Он встречается настолько часто, что может быть скрыт даже в задании не на кодирование. К примеру, нужно найти в логах git версию, где в приложении допущена ошибка.

2. Умение строить структуры данных. Практически во всех задачах требуется правильная инкапсуляция данных. Особенно это относится к ООП. Иногда сложность задачи даже не столько в алгоритме, сколько в построении правильной структуры или класса. Поэтому без умения создавать лаконичные и непротиворечивые структуры данных никуда.

3. Рекурсия. Несмотря на то, что рекурсия – тема множества мемов и шуточек про программистов, в реальности она встречается довольно редко (а в таких мемах – почти никогда). Есть хорошее выражение: «Существует несколько задач, которые красиво и эффективно решаются рекурсией. Есть множество задач, которые красиво, но неэффективно решаются рекурсией. Подавляющее большинство задач решать рекурсией и некрасиво, и неэффективно». Тем не менее, знать принципы рекурсивного решения очень полезно. Пример: решение судоку.

4. Основы сортировки. Это не значит, что вам нужно заучить алгоритмы сортировки слиянием или быстрой сортировки. Но важно понимать общие принципы работы, почему сортировка слиянием быстрее сортировки пузырьком, время работы в O-нотации, уметь использовать факт, что коллекция уже отсортирована и т.п.

5. Разворачивание связанного списка. Вариантами задачи могут быть нахождение дубликатов в списке или определение, является ли связанный список зацикленным. Кроме того, важно правильно создать структуру элемента списка (данные и указатель).

6. Манипулирование несколькими переменными/указателями одновременно. Канонический пример: разворот строки, определение, является ли строка палиндромом, нахождение самого длинного палиндрома в тексте, - движение указателей в обе стороны, либо с разной скоростью.

7. Использование Хеш-таблиц (или множеств). Здесь вариантами могут быть задачи на оптимальное нахождение парного числа в массиве, задачи на обход графа с сохранением пути, мемоизация в рекурсии и т.п.

8. Нахождение закрывающей скобки. Вариантами могут быть проверка, все ли скобки закрыты в строке, либо нахождение, сколько скобок нужно добавить. Кандидат для использования стека. Добавляем открывающие скобки в стек, при нахождении закрывающей скобки – удаляем элемент из стека.

9. Поиск в глубину (Depth-first search) — один из методов обхода графа, который состоит в том, чтобы идти «вглубь» графа, насколько это возможно. Можно реализовать с помощью стека и рекурсии. Для заданной вершины добавляем всех её потомков в стек, далее извлекаем первый элемент стека и повторяем процедуру для него рекурсивно.

10. Поиск в ширину (Breadth-first search) — обход всех ребер для «открытия» всех вершин, достижимых из заданной вершины. Можно реализовать с помощью очереди. Для заданной вершины добавляем всех её потомков в очередь. Далее, проходя по очереди добавляем всех потомков каждого элемента в конец очереди.

Источники:
- https://www.youtube.com/watch?v=r1MXwyiGi_U
- https://youtu.be/zHczhZn-z30