Я посетил множество интервью и был по обе стороны этого противостояния. Теперь я хочу поделиться самыми интересными задачами с другими. Потому что я считаю, что интервью должно быть интересным и запоминающимся, а не ужасным и демотивирующим.

Несколько замечаний

  1. Все задания по логике и/или программированию. Никакого психологического подтекста нет.
  2. Я намеренно не хочу давать решение какой-либо задачи. Но уверяю вас, что у большинства из них есть простое и красивое решение. Наслаждаться!

Задания

Они здесь.

Похожие строки в SQL

Допустим, у нас есть таблица со строковым столбцом и мы хотим найти похожие строки по какому-то условию (например, это полнотекстовый поиск или какая-то внутренняя функция, которая получает два значения и возвращает true/false). Итак, пишем самообъединение и, очевидно, получаем дублированные строки. т.е. у нас есть зеркальная пара в результате. Итак, вопрос следующий: как убрать один из зеркальных элементов (неважно какой именно) и оставить только уникальные пары без перестановки?

Подсказка: есть неочевидное свойство строки и общих операторов SQL.

Поиск «дыр» с помощью SQL

Это задание идеально подходит для получения знаний о понимании основ SQL кандидатом.

Предположим, у нас есть таблица с одним целочисленным столбцом. Мы ничего не знаем о его минимальном/максимальном значении. Более того, мы не знаем количество строк в таблице, и в общем случае это количество варьируется. Мы знаем, что между значениями есть пустые промежутки («дырки»). Кроме того, мы знаем, что длина этих пустых интервалов не больше единицы. Например, таблица из 5 (пяти) элементов: 1, 2, 4, 6, 7. Вопрос: написать одиночный SQL-запрос, используя только общие операторы (без процедур и переменных), который имеет все значения «дырок» в результате . Для верхнего примера это было 3, 5. Помните, что для 3 и 5 нет значений NULL. Этих значений вообще нет в таблице.

Советы:

  • если это сложно для вас, попробуйте использовать процедуру, а затем перейти к одному запросу;
  • полезный совет: самый красивый запрос должен быть для запроса с результатом 3, 5, 8 из верхнего примера.

Цикл в односвязном списке

Это об алгоритмах и сложности.

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

Следующий шаг. Необходимо изменить полученный алгоритм в соответствии с требованием: он должен иметь потребление памяти O (1).

Подсказка: помните о преобразовании временной сложности в память и наоборот.

Хранилище ключей-значений

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

Теперь перепишите метод set_all для достижения временной сложности O(1).

Можете ли вы сохранить начальную сложность методов get и set и удовлетворить требования для set_all? Если да — напишите, нет — аргументируйте, почему это невозможно.

Спасите людей

Есть группа людей. У каждого члена есть белая или черная шляпа. Распределение цветов шляпок неизвестно. Более того, никто не знает цвета собственной шляпы. Люди стоят в очереди и смотрят друг другу в затылок. Следовательно, они видят все перед собой и слышат все, что происходит позади. В первый момент времени к спине последнего участника подходит незнакомец с револьвером и спрашивает его о цвете его шляпы. Участник может сказать только «белый» или «черный». Если член прав — он свободен. В противном случае он будет застрелен с громким звуком. Вопросы следующие:

  • как спасти больше всего жизней?
  • Дайте оценку спасенных жизней.

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

Советы:

  • подумайте, как каждый участник может объединить всю существующую информацию в один бит данных и как они могут обмениваться этой информацией;
  • важный совет: может быть, вам поможет чет/нечет или xor?

Это все. Теперь ваша очередь решить некоторые/все из них и рассказать о своем интересном опыте и задачах.