Несколько замечаний
- Все задачки на логику и/или о программировании. Никакого психологического подтекста и круглых люков.
- Решение не приводится умышленно. Однако, я уверяю вас, что почти у всех задач есть простое и красивое решение. Наслаждайтесь!
Задачи
Вот они.
Зеркальные строки в 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 смогут вам помочь?
Вот и всё. Теперь ваша очередь решить какую-нибудь из задач и рассказать о своей интересной подборке с/для собеседований.
