Реалтайм-кодинг на 10 минут

Во время собеседования интервьюер дает простую задачу, надо за 10 минут написать код, оценить его алгоритмическую сложность (complexity). Интервьюер в реалтайме смотрит, что вы пишите, поэтому надо одновременно и писать код, и объяснять, что и зачем.

Писать можно на любом из 20 доступных языков программирования. Можно даже на псевдо-языке. Можно допускать синтаксические ошибки - код все равно не запускается, важна только структура и алгоритм. Плюсом будет наличие комментариев, типизации, читаемости кода, валидации данных и пр.

Примеры задач:

• Написать алгоритм:
  • Обход дерева в ширину.
  • Проверка, является ли двоичное дерево двоичным деревом поиска.
  • Проверка, является ли слово палиндромом.
  • Инвертировать порядок слов в предложении, но сами слова не менять. Например, "Hello World" -> "World Hello". Будет плюсом упомянуть про вариант решения нативными средствами типа split(" ").reverse().join(" ") , но все-таки реализовать надо без этих функций.
  • Клонирование двусвязного списка.
  • Нахождение наиболее используемой буквы в тексте.
  • Нахождение в массиве чисел, соседних с максимальным.
  • Сортировка массива любым способом. Естественно, без использования нативных функция языка.
  • Найти файлы в директории по заданному параметру (имени, расширению, размеру).
  • и еще множество других алгоритмов, где надо перебирать элементы массива / дерева / строки / списка.
• Создать классы (свойства, константы, методы):
  • Кэш с вытеснением наименее используемых элементов,
  • Игра Sokoban. Если не знаете правил - не беда, вам их кратко расскажут.
  • Игра шахматы. Конечно, не требуется обыграть Deep Blue - достаточно только создать классы для игрового поля и фигур. Желательно с указанием, как они могут двигаться.
  • Игра крестики-нолики.
  • Игра домино.
• Создать таблицы БД:
  • Обмен сообщениями на сайте.
  • Бронирование номеров в отеле.
  • Расписание движения поездов.
  • Книги в библиотеке.
  • Календарь с повторяющимися событиями.
  • Журнал посещаемости.
  • Интернет-магазин.
  • Школьный журнал оценок.