Запитання для ШІ-співбесід із програмування: приклади та практика

Навіть знаючи назви алгоритмів, можна не розуміти, як підійти до нової задачі. Ці практичні запитання пов’язують конкретні вхідні дані з вибором розв’язку, межами складності та крайовими випадками, які варто пояснювати вголос.

• Two Sum: поверніть два різні індекси, значення яких у сумі дорівнюють цільовому. Для [3, 3] і цільового значення 6 відповідь використовує обидві позиції. Переглядайте масив, зберігаючи раніше побачені значення в хеш-таблиці: спочатку перевіряйте наявність доповнення, а потім зберігайте поточне значення. Це запобігає повторному використанню одного індексу. Очікуваний час — O(n), додаткова пам’ять — O(n). Уточніть, що повертати, якщо пари немає.
• Знайдіть найдовший підрядок без повторюваних символів. Для 'abba' довжина дорівнює 2. Відстежуйте останню позицію кожного символу та підтримуйте вікно без дублікатів. Ліва межа не повинна рухатися назад, якщо попередня поява символу лежить поза поточним вікном. Очікуваний час — O(n) за умови пошуку в хеш-таблиці. Уточніть, що саме вважається символом.
• Об’єднайте замкнені інтервали, що перекриваються. Для [1, 3], [3, 5] і [8, 10] поверніть [1, 5] та [8, 10]. Відсортуйте інтервали за початком, а потім розширюйте поточний інтервал або починайте новий. Сортування дає час O(n log n). Замкнені інтервали зі спільною кінцевою точкою перекриваються; запитайте, чи відповідає це визначенню задачі.
• Розверніть ациклічний однозв’язний список. Збережіть наступний вузол, перш ніж змінювати вказівник поточного вузла на наступний. Ітеративний розв’язок потребує часу O(n) і додаткової пам’яті O(1). Покроково розгляньте порожній список, один вузол і два вузли. Пояснюйте після кожної ітерації, яку частину списку вже розвернуто.
• Поверніть значення бінарного дерева рівень за рівнем. Використовуйте чергу й обробіть кількість вузлів поточного рівня, перш ніж переходити до наступного. Час — O(n); допоміжна пам’ять черги — O(w), де w — максимальна ширина рівня без урахування поверненого результату. Перевірте порожнє дерево та дерево, у якому на кожному рівні є лише одна дочірня вершина.
• Визначте, чи можна завершити всі курси з урахуванням передумов. Подайте передумови як орієнтований граф і застосуйте топологічне сортування. Якщо оброблено менше ніж V вершин, в орієнтованому графі залишився цикл. Час — O(V + E). Перевірте незв’язані компоненти, ізольований курс і залежність курсу від самого себе.
• Знайдіть найменшу кількість монет, потрібну для отримання заданої суми. Припустімо, що доступна необмежена кількість монет із додатними цілими номіналами. Для [1, 3, 4] і суми 6 жадібний вибір найбільшої монети дає три монети; 3 + 3 дає дві. Визначте стан динамічного програмування як мінімальну кількість монет для кожної суми, починаючи з нуля монет для нульової суми. Для цільового значення A та c номіналів стандартний підхід потребує часу O(Ac) і пам’яті O(A). Явно обробляйте недосяжні суми.

Щоб знайти пов’язані практичні завдання, упорядковані за ролями й темами, перегляньте бібліотеку запитань для співбесід.

Розгляньте таке завдання: порахуйте непорожні неперервні підмасиви, сума яких дорівнює цільовому значенню, враховуючи від’ємні числа. Для [1, -1, 1] і цільового значення 1 відповідь дорівнює 3: будь-який одноелементний підмасив [1] або весь масив.

Почніть із базового підходу: вибирайте кожну початкову позицію та послідовно розширюйте кінцеву, підтримуючи поточну суму. Це потребує часу O(n²) і додаткової пам’яті O(1). Звичайний підхід зі звуженням вікна тут ненадійний, оскільки від’ємні значення порушують припущення, що розширення вікна збільшує його суму.

Швидший підхід використовує префіксні суми й таблицю частот. Якщо поточна префіксна сума дорівнює s, кожен попередній префікс зі значенням s - target визначає підмасив із потрібною сумою. Спочатку внесіть до таблиці одне входження нульової префіксної суми, що представляє порожній префікс перед початком масиву.

• Порядок обробки: додайте поточне значення до префіксної суми, порахуйте відповідні попередні префікси, а потім запишіть поточний префікс. Якби його записали спочатку, за нульового цільового значення помилково було б враховано порожній підмасив.
• Інваріант: перед записом поточного префікса таблиця містить частоти всіх префіксів, що закінчуються до поточної позиції.
• Складність: для кожного елемента виконується стала кількість операцій із таблицею. Очікуваний час — O(n), якщо хеш-операції в середньому мають сталий час; додаткова пам’ять — O(n).
• Перевірки: для порожнього масиву повертається 0. Для [0, 0] і цільового значення 0 поверніть 3. За використання цілочисельних типів фіксованої ширини враховуйте переповнення як накопиченої суми, так і лічильника відповідей.

Корисне додаткове запитання: чи потрібно повернути кількість або самі підмасиви. Повернення всіх відповідних підмасивів створює витрати на виведення: у масиві з одних нулів є n(n + 1)/2 відповідних непорожніх підмасивів, якщо цільове значення дорівнює нулю.

Спочатку спробуйте розв’язати задачу самостійно, а потім попросіть про найменше втручання, яке допоможе продовжити. Наведені нижче запити перетворять розмову із ШІ на практику, яку можна перевірити.

• Попросіть одну підказку: Дайте мені одну підказку щодо того, яку інформацію зберігати. Поки що не наводьте код і не називайте весь алгоритм.
• Перевірте міркування: Ось мій інваріант циклу. Знайдіть вхідні дані, за яких моя реалізація його порушує, або поясніть, чому кожне оновлення його зберігає. Перевірте відповідь самостійно: згода моделі не є доказом правильності.
• Перевірте складність: Порахуйте роботу, яку в цій реалізації виконують створення зрізів, сортування, операції з контейнерами та рекурсивні виклики. Знайома назва алгоритму не визначає складність вашого фактичного коду.
• Створіть тести: Запропонуйте випадки для порожніх вхідних даних, дублікатів, граничних значень і неможливих результатів. Поясніть очікувану відповідь для кожного. Виведіть ці відповіді самостійно, перш ніж використовувати їх як тестовий оракул.
• Змініть одне обмеження: Як зміниться розв’язок, якщо вхідні дані відсортовані, їх не можна змінювати або вони надходять потоком? Поясніть новий компроміс, перш ніж переписувати код.

Уявімо бекенд-інженерку, яка готується до співбесіди на старшу посаду в постачальника хмарних послуг. Розв’язавши задачу про граф передумов, вона просить ШІ-партнера для практики створити незв’язаний граф із циклом. Потім вона покроково аналізує чергу й без підказки пояснює, чому кількість оброблених вершин виявляє цикл.

Прочитавши повний розв’язок, закрийте його та відтворіть із пам’яті алгоритм, інваріант і тести. Уміння відтворити код менш корисне, ніж уміння пояснити, чому він працює, і пристосувати його до зміненого обмеження.

Щоб потренуватися пояснювати свої міркування в розмові, відвідайте сторінку пробної співбесіди.

SubcueAI пропонує два засоби допомоги наживо. Його основний нативний застосунок для macOS і Windows записує системний звук і ваш мікрофон, а допомогу показує в локальному плавучому накладенні. Він працює з настільними клієнтами для зустрічей, зокрема Zoom і Microsoft Teams.

Розширення браузера також надає допомогу наживо через бічну панель у браузерах на основі Chromium, зокрема Chrome та Edge. Воно записує лише звук вкладки зустрічі, охоплюючи виклики у вкладці браузера, наприклад Google Meet. Воно чує співрозмовника через цю вкладку, ніколи не записує ваш мікрофон і не транскрибує кандидата. Версія для Firefox призначена лише для пробної практики.

Жоден із цих засобів не додає бота до зустрічі й не впроваджує сценарій вмісту на сторінку зустрічі. У задачах із програмування розрізняйте усний і письмовий контекст: саме лише записування звуку не передає умову задачі або код, показаний лише в редакторі. Зіставляйте кожну пропозицію з точною умовою, обмеженнями та реалізацією.

Перед використанням допомоги наживо перевірте правила співбесіди. SubcueAI не є гарантовано невиявним за всіх умов. Демонстрація екрана, запис, контрольовані оцінювання та керовані компанією пристрої не охоплюються гарантіями приховування. На спільному або записаному екрані може бути видно накладення чи бічну панель, а засоби керування пристроєм або контролю можуть відстежувати активність.

Інструкції з налаштування доступних засобів дивіться в посібнику SubcueAI.