Цікаві задачі з технічних співбесід
Відвідав я багато інтерв’ю і був на обох сторонах протистояння. Тепер прийшов час поділитися найбільш цікавими завданнями з оточуючими. Бо інтерв’ю повинні бути цікавими і запам’ятовуються, а не убогих і демотивирующими.
Кілька зауважень
- Всі задачки на логіку та/або про програмуванні. ніякого психологічного підтексту і круглих люків.
- Рішення не наводиться навмисне. Однак, я запевняю вас, що майже у всіх завдань є просте і красиве рішення. Насолоджуйтесь!
Дзеркальні рядки в 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 зможуть вам допомогти?
От і все. Тепер ваша черга вирішити яку-небудь із завдань і розповісти про свою цікавою добірці з/для співбесід.
