У цій статті я розповім про завдання і питаннях, які чекають програмістів на співбесіді при прийомі на роботу.
Інтерв'юери не відрізняються оригінальністю, і один і той же питання можна зустріти на 3-5 різних співбесідах.
Але навіть досвідчені програмісти, опиняючись в стресовій ситуації, нерідко губляться і не можуть знайти відповідь на досить прості питання. Тому пропоную заздалегідь потренуватися, перевірити свої знання, а заодно і подивитися на улюблені запитання інтерв'юерів. Не виключено, що саме на них Вам належить відповідати на наступній співбесіді.
Структури даних і питання про алгоритмах - основна частина будь-якого співбесіди для програмістів незалежно від їх спеціалізації
Всі програмісти знають, що середній елемент в LinkedList нескладно знайти, визначивши довжину списку, послідовно пройшовши всі його вузли, поки не дійдеш до NULL в першому проході. А потім, пройшовши половину з них у другому проході. Коли ж їх просять вирішити цю задачу за один прохід, багато губляться.
Більшість завдань, поставлених на співбесіді, має досить просте рішення, і сидячи в спокійній обстановці, Ви без особливих зусиль знайдете його самі.
У цьому завданні досить ввести два покажчика. Перший буде збільшуватися при проходженні одного вузла списку, другий - при проходженні 2 вузлів. У момент, коли 2ий покажчик дійде до кінця списку (наткнеться на NULL), перший буде вказувати на середину списку.
Успішно впоралися з цим питанням? Отримайте наступний.
Вихідний код рішення
Ставлячи такі питання, ваш співрозмовник, ясна річ, хоче почути не завчене визначення з підручника або отримати посилання з Вікіпедії, а оцінити ваше власне розуміння відмінності цих двох типів структур даних.
Стек і черга схожі відсутністю вільного доступу до всіх елементів структури даних. А головна відмінність полягає в тому, що стек - це структура типу LIFO (Last In First Out), де вільний доступ можливий тільки до останнього доданому елементу, а при його видаленні методом «pop» до елементу, доданому перед ним. Коли ж в стек додається новий елемент, доступний стає тільки він.
Чергу відноситься до типу FIFO (First In First Out), тобто доступний в ній тільки перший доданий елемент. У разі його видалення доступний другий і т.д.
Це питання досить часто на співбесіді чують ті, хто зуміли швидко знайти 1 дублюючийся елемент в масиві. Для вирішення цього завдання можна використовувати HashMap. Як Ви, безсумнівно, знаєте, HashMap зберігає дані парами - ключ / значення, і створивши потрібну кількість карток, Ви легко знайдете все повтори і їх номери.
В обох списках вузли зв'язані за допомогою покажчиків. Тільки в однозв'язного списку покажчик від кожного вузла веде виключно до наступного, і перехід можливий тільки до нього, тобто виключно в одному напрямку. А в двусвязного від кожного вузла, крім першого і останнього, є можливість перейти як до наступного, так і до попереднього вузла, тобто рухатися в обох напрямках.
Якщо раптом хтось не знає, числа Фібоначчі - це послідовність, де кожне наступне число після 1 є сумою двох йому передують. Тобто ряд чисел Фібоначчі виглядає так: 1,1, 2, 3, 5, 8, 13, 21 ...
Вирішити це завдання можна так:
Бінарне, або двійкове дерево пошуку - це структура даних, кожен вузол в якій може мати від 1 до 2 подсистемами (дітей) або не мати їх зовсім.
Розташування даних в бінарному дереві має ряд обмежень:
- Як і у всіх деревах, будь-який вузол бінарного дерева не може мати більше одного батька.
- Дані в дереві розподіляються залежно від їх значень. Якщо значення підвузли (дитини) менше, ніж значення вузла (одного з батьків), цей подузел ставати лівим або дитиною лівого підвузли, якщо лівий подузел вже існує. Відповідно, якщо значення підвузли більше значення вузла, то він стає правим або дитиною правого.
Застосовуються бінарні дерева в реалізації асоціативних масивів і множин, наприклад TreeMap або TreeSet, в деяких алгоритмах обчислювальної геометрії.
Це питання дозволяє продемонструвати свої навички володіння стандартними методами (push і pop) для роботи з цією структурою даних. При виконанні цього завдання Вам потрібно буде використовувати масив або зв'язний список для зберігання елементів.
Написати можна, наприклад, програму стандартного калькулятора.
Не забувайте, що вирішуючи ту чи іншу задачу на співбесіді, бажано роз'яснювати кожен логічний крок інтерв'юеру. На стартовому співбесіді оцінюють не тільки швидкість і правильність вирішення поставлених завдань, а й логіку мислення в цілому.
Саме тому іноді навіть неповне рішення складного завдання дозволить інтерв'юеру оцінити ваші знання як достатні для вакантної посади.
Навіть якщо Ви досвідчений програміст з десятками реалізованих проектів портфоліо, не полінуйтеся перед співбесідою повторити теорію. Адже відповідь «ну це працює десь так ... і взагалі, за останні 3 роки я жодного разу не користувався цією структурою даних» навряд чи влаштує інтерв'юера.
Частина матеріалів переведена з цього джерела.
Креативу Вам і удачі на співбесіді!