Цікаві задачі з технічних співбесід

Відвідав я багато інтерв’ю і був на обох сторонах протистояння. Тепер прийшов час поділитися найбільш цікавими завданнями з оточуючими. Бо інтерв’ю повинні бути цікавими і запам’ятовуються, а не убогих і демотивирующими.

Кілька зауважень

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

Дзеркальні рядки в 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 зможуть вам допомогти?

От і все. Тепер ваша черга вирішити яку-небудь із завдань і розповісти про свою цікавою добірці з/для співбесід.