Pull to refresh

Интересные задачки с технических собеседований

Reading time 3 min
Views 31K
Original author: Ivan Zabrovskiy

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



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


  • Все задачки на логику и/или о программировании. Никакого психологического подтекста и круглых люков.
  • Решение не приводится умышленно. Однако, я уверяю вас, что почти у всех задач есть простое и красивое решение. Наслаждайтесь!

Задачи


Вот они.


Зеркальные строки в SQL


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


Советы и подсказки
  • существует одно неочевидное свойство строк и базовых SQL-операторов, которым можно воспользоваться...
  • Или можно погуглить, при правильном запросе ответ будет в первой ссылке на stackoverflow.

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


Это отличная задачка для оценки знаний по всем базовым возможностям SQL.


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


Совет
  • если ходу не получается, напишите в несколько запросов или с использованием pl/sql, а затем, если ваша идея верна, сможете логически перейти к одному запросу.

Подсказка
  • наиболее красивым запрос будет в случае, если запрос для вышепреведённых входных условий вернёт не "3, 5", а "3, 5, 8".

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


Это задачка про алгоритмы и сложность.


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


Продолжение


Нужно модифицировать результат так, чтобы сложность по памяти была O(1). То есть, чтобы потребление памяти не зависело от размера списка.


Подсказка
  • помните, что так же как масса может превращаться в энергию, так и временнáя сложность, может конвертироваться в потребление памяти и наоборот.

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


Ещё одна задачка на совместное написание кода и его обсуждение в ходе написания.


Напишите key-value storage на любом желаемом языке. Добавьте функцию set_all, которая принимает на вход значение и устанавливает его для всех существующих ключей. Оцените затраты времени и памяти для полученной реализации.


А теперь сделайте set_all, работающим за O(1).


А можно сделать так, чтобы сложность методов get и set осталась как в самом начале, а set_all продолжил работать за O(1)? Если да, то реализуйте. Если нет — докажите почему это невозможно.


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


А в этой задаче надо подумать и порассуждать вместе с собеседуемым. А реализация — это дело техники и не особо интересна.


Представим, что у нас есть группа людей. Количество значения не имеет. Всю группу выстраивают в линию в затылок друг другу и каждому на голову одевают чёрную или белую шляпу. Никто не знает цвета шляпы, которая на него надета. Однако, все видят, что происходит перед ними и слышал, что происходит за ними. После этого, к спине последнего из группы полходит незнакомец с пистолетом. Он спрашивает "какой у тебя цвет шляпы?" Ответом может быть только "черный" или "белый". Никаких других сообщений быть не может. Если человек угадал — его отпускают. Иначе происходит выстрел и, в любом случае, процесс повторяется с "новым" последним членом в очереди.


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


Вопрос: как максимизировать число выживших и существует ли точная оценка числа выживших в зависимости от размера группы?


Совет
  • подуайте, как может каждый член собрать всю доступную информацию и передать её в одном бите?

Подсказка
  • может быть чётность/нечётность или оператор XOR смогут вам помочь?

Вот и всё. Теперь ваша очередь решить какую-нибудь из задач и рассказать о своей интересной подборке с/для собеседований.

Only registered users can participate in poll. Log in, please.
Должны ли давать задачи на собеседованиях?
4.8% Обязательно должны. И посложнее. 11
48.91% Обязательно, но гуманные на ~10 строк кода или на совместное размышление. 112
21.4% Не обязательно. Только если есть сомнения в кандидате. 49
23.58% Не должны. И так стресса хватает. 54
1.31% Иное. В комментарии. 3
229 users voted. 50 users abstained.
Tags:
Hubs:
If this publication inspired you and you want to support the author, do not hesitate to click on the button
+13
Comments 78
Comments Comments 78

Articles