Зміст[Сховати][Показати]
- 1. Як визначити масив?
- 2. Динамічні масиви: що це таке? Що відрізняє їх від базових масивів?
- 3. Чим відрізняються один від одного масив і словник?
- 4. Перелічіть деякі переваги та недоліки масивів.
- 5. Що означає «розріджений масив»?
- 6. Коли б ви вибрали пов’язаний список замість масиву?
- 7. Чим індексований масив відрізняється від асоціативного?
- 8. Які переваги має Heap перед відсортованими масивами?
- 9. Чи можемо ми визначити розмір масиву як від’ємний?
- 10. Як знайти відсутнє ціле число в масиві від 1 до 100 елементів?
- 11. Як знайти індекс елемента в масиві?
- 12. Як можна позбутися певного елемента з масиву?
- 13. Як можна перевірити рівність двох масивів?
- 14. Коли ми обговорюємо масиви, що ви маєте на увазі під фразами «Розмір» і «Індекс»?
- Питання для співбесіди з програмування
- 15. Знайти пару в масиві, яка має вказану суму
- 16. Сортування двійкового масиву з лінійним часом
- 17. Знайдіть найбільший двоцілий добуток у масиві.
- 18. Як зсунути всі нулі масиву в кінець
- 19. Як відсортувати масив із двома записами, які перемикаються за одну операцію.
- 20. Як об'єднати два відсортованих масиви на місці.
- 21. Як змінити порядок масиву елементів у високих і низьких позиціях, що чергуються?
- 22. Як замінити кожен елемент масиву без використання оператора ділення на добуток кожного елемента масиву?
- 23. Знайти найнепарніший елемент у масиві за логарифмічний час
- 24. Як отримати наступний більший елемент для кожного елемента в круговому масиві?
- 25. Знайти кількість інверсій масиву?
- 26. Що таке проблема уловлювання дощової води?
- Висновок
Інтерв’ю з кодування містить низку запитань DSA. Ви повинні бути навичками роботи з масивами, якщо готуєтеся до майбутньої співбесіди з технічних питань у FAANG або іншому технологічному бізнесі рівня 1.
У більшості інтерв’ю з кодуванням він займає друге місце після Strings. Масив — це група пов’язаних елементів даних, які зберігаються в пам’яті в безпосередній близькості один до одного.
Оскільки вони пов’язані з усіма мовами програмування, такими як C, C++, Java, Python, Perl і Ruby, вони всюди. Продовжуйте читати, щоб дізнатися про практичні завдання з кодування та запитання та відповіді на співбесіді на основі масивів.
Python буде використано в цій публікації для вирішення проблем кодування, оскільки він простий у використанні, зрозумілий і повинен бути знайомий більшості з нас.
Давайте почнемо.
1. Як визначити масив?
- Група пов’язаних типів даних є масивом.
- Масиви завжди фіксовані.
- Змінна одного типу зберігається в кількох місцях об’єктами масиву.
- Примітивні типи та посилання на об’єкти сумісні з ним.
2. Динамічні масиви: що це таке? Що відрізняє їх від базових масивів?
Автоматичне масштабування, яке забезпечують динамічні масиви (також відомі як масиви з можливістю збільшення, масиви зі змінним розміром, змінні масиви або ArrayLists у Java), є значною перевагою.
Ви завжди повинні заздалегідь знати, скільки елементів зберігатиме ваш масив, оскільки масиви мають фіксований розмір. З іншого боку, динамічний масив збільшується, коли ви додаєте до нього додаткові елементи, тому вам не потрібно заздалегідь знати його точний розмір.
3. Чим відрізняються один від одного масив і словник?
Це набір запитань для співбесіди, які регулярно задають, базуються на фундаментальних питаннях. Нижче наведено основні відмінності між масивами та словниками:
- Масив — це впорядкований список подібних елементів. Словник, з іншого боку, має пари ключ-значення.
- Розміри масивів можуть змінюватися динамічно. Таких динамічних ідей немає в словниках.
- Перед використанням масиву необхідно вказати його розмір. Розмір словника не потрібно налаштовувати.
- Використовуйте оператор Redim, якщо ви бажаєте збільшити розмір масиву. У словниках елемент можна додавати без оголошення.
4. Перелічіть деякі переваги та недоліки масивів.
переваги:
- Масиви можуть сортувати кілька елементів одночасно.
- Інше структури даних, як і стеки, черги, пов’язані списки, дерева, графи тощо, можна реалізувати в масиві.
- Для досягнення елемента масиву можна використовувати індекс.
Недоліки:
- Розмір масиву необхідно оголошувати заздалегідь. Проте на момент оголошення масиву ми можемо не знати про потрібний розмір.
- Структура масиву статична. Це означає, що розмір масиву завжди фіксований і що розподіл пам’яті не можна збільшити або зменшити.
5. Що означає «розріджений масив»?
Розріджений масив — це масив даних, який містить багато записів із нульовими значеннями. Навпаки, щільний масив містить більшість елементів із ненульовими значеннями. Індекси розрідженого масиву, який перетворює числа на об’єкти, можуть містити пропуски. Порівняно з HashMap вони більш ефективні для пам’яті.
6. Коли б ви вибрали пов’язаний список замість масиву?
Використовуючи зв’язані списки замість масивів, враховуйте:
- Для довільного доступу вам не потрібні жодні елементи.
- Там, де часова передбачуваність є важливою, вам потрібні постійні вставки та видалення зі списку.
- Щоб створити пріоритетну чергу, вам може знадобитися розмістити елементи в центрі списку.
- Ви не уявляєте, яким довгим буде список. Якщо розмір масиву зростає, ви повинні повторно оголосити та дублювати пам’ять, як і з простими масивами.
7. Чим індексований масив відрізняється від асоціативного?
Основні відмінності між асоціативними та індексованими масивами наведено в наступній таблиці.
- Для сортування асоціативного масиву використовується пара ключ-значення в текстовому або числовому форматі. Усі ключі індексованого масиву є числовими, і кожен ключ пов’язаний із окремим значенням.
- В асоціативному масиві ключем може бути рядок. Індексований масив із цілими ключами, починаючи з 0.
- Таблиця з двох стовпців імітує поведінку асоціативного масиву. Подібно до таблиці з одним стовпцем є індексовані масиви.
- Карти є типом асоціативного масиву. Індексний масив не є картою.
8. Які переваги має Heap перед відсортованими масивами?
Ефективність використання купи над відсортованими масивами є ключовою перевагою. Хоча операції з купою виконуються швидше, сортування масиву вимагає багато часу. Купа може знайти найменший елемент значно швидше, ніж масив може бути відсортований.
Дану колекцію чисел можна впорядкувати одним із двох способів за допомогою відсортованих масивів. З іншого боку, для даного набору чисел може існувати більше однієї потенційної купи.
9. Чи можемо ми визначити розмір масиву як від’ємний?
Ні, ми не можемо визначити від’ємне ціле число як розмір масиву. Якщо ми оголосимо, помилки під час компіляції не буде. Однак під час виконання ми зіткнемося з винятком NegativeArraySizeException.
10. Як знайти відсутнє ціле число в масиві від 1 до 100 елементів?
Підсумок ряду можна обчислити, застосувавши таку функцію: n (n + 1) / 2
Ця функція працюватиме, лише якщо в масиві немає дублікатів або в ньому відсутнє більше одного цілого числа. Незалежно від того, чи містить масив повторювані елементи, ви можете відсортувати масив, щоб побачити, чи є елементи, які є еквівалентними.
11. Як знайти індекс елемента в масиві?
Індекс елемента можна знайти за допомогою лінійного або двійкового пошуку. Поки не буде знайдено збіг необхідного елемента, функція лінійного пошуку циклічно переглядає кожен елемент у масиві. Він повертає індекс, коли знаходить відповідний елемент. Отже, часова складність лінійного пошуку становить O. (n). Як відсортований, так і невідсортований масив можуть використовувати лінійний пошук.
Використовуючи двійковий пошук, який постійно ділить масив навпіл, поки медіана інтервалу не збігається з необхідним елементом і не надає індекс, ви можете отримати індекс елемента, якщо масив відсортовано. Отже, часова складність бінарного пошуку становить O. (log n).
12. Як можна позбутися певного елемента з масиву?
Оскільки ви не можете просто видалити елементи з вихідного масиву, оскільки вони являють собою фіксовані набори з визначеним розміром, інтерв’юер шукає, щоб ви запропонували інший підхід і розв’язали проблему, яку піднімає запитання. Найкращий спосіб – створити новий масив, щоб видалити елемент. Ви можете дублювати елементи з першого масиву в цьому масиві та включати лише той елемент, який хочете видалити.
Інша стратегія передбачає пошук цільового елемента в масиві, а потім зміну порядку всіх елементів, які знаходяться праворуч від цільового елемента.
13. Як можна перевірити рівність двох масивів?
Спочатку потрібно перевірити довжину двох наданих масивів. Збіги елементів обох масивів порівнюються, якщо їх довжини однакові. Два масиви будуть вважатися рівними. якщо кожна пара компонентів у кожній відповідності рівна. Цей підхід не рекомендується для перевірки рівності двох масивів, якщо масиви великі за розміром, оскільки це займе багато часу. Ви також можете використовувати метод equals(), включений у клас Arrays, однак, якщо інтерв’юер попросить вас порівняти два масиви без використання вбудованих методів, цей спосіб буде корисним.
14. Коли ми обговорюємо масиви, що ви маєте на увазі під фразами «Розмір» і «Індекс»?
«Розмірність» масиву — це кількість індексів або індексів, необхідних для ідентифікації кожного окремого члена. Індекси та розміри можуть бути незрозумілими. Розмір — це опис діапазону дозволених ключів, тоді як індекс — це число. Для кожного виміру масиву потрібен лише один індекс.
Наприклад, масив arr[10][5] має два виміри. На одному розміри 10, на другому 5. Щоб звернутися до його компонентів, вам потрібні два нижні індекси. Обидва знаходяться між 0 і 4; один від 0 до 9 включно.
Питання для співбесіди з програмування
15. Знайти пару в масиві, яка має вказану суму
Наприклад,
Вхідний сигнал:
- чисел = [8, 7, 2, 5, 3, 1]
- ціль = 10
вихід:
- Пара знайдена (8, 2)
- Or
- Пара знайдена (7, 3)
Вхідний сигнал:
- чисел = [5, 2, 6, 8, 1, 9]
- ціль = 12
вихід:
- Пара не знайдена
16. Сортування двійкового масиву з лінійним часом
Сортувати двійковий масив у лінійному часі та у фіксованій області. Вихідні дані повинні спочатку відображати всі нулі, а потім усі одиниці.
Наприклад,
- Вхідні дані: { 1, 0, 1, 0, 1, 0, 0, 1 }
- Вихід: { 0, 0, 0, 0, 1, 1, 1, 1 }
Простий підхід полягав би в тому, щоб обчислити загальну кількість нулів у масиві, скажімо, k, а потім заповнити перші k індексів у масиві 0-ми, а решта індексів — 0. Як альтернативу, ми можемо обчислити, скільки одиниць є в цілому в масиву k, заповніть останні k індексів у масиві 1, а решту індексів залиште 1.
Даний підхід має O(n) часову складність і не використовує додаткової пам’яті, де n – розмір вхідних даних.
17. Знайдіть найбільший двоцілий добуток у масиві.
Знайти найбільший добуток двох чисел у цілочисельному масиві.
Подумайте про масив 10 3 5 6 2 як приклад. Пара (-10, -3) або (5, 6) є найвищим продуктом.
Роздумувати про кожну комбінацію елементів і з’ясовувати їхній продукт – дурний підхід. Якщо добуток поточної пари більший за максимальний добуток, отриманий на даний момент, оновіть максимальний добуток. Друкуйте компоненти кінцевого продукту в останню чергу.
Наведене вище рішення, де n — кількість вхідних даних, має часову складність O(n2) і більше не займає місця.
18. Як зсунути всі нулі масиву в кінець
Перемістіть усі нулі в цілочисельному масиві в кінець. Відповідь має уникати використання постійного простору та зберігати відносний порядок компонентів масиву.
Вхідні дані: {1,2,3,0,8,0,4,7}
Вихід буде {1,2,3,8,4,7,0,0}
Помістіть елемент у наступну доступну позицію в масиві, якщо поточний елемент не дорівнює нулю. Заповніть усі індекси, що залишилися, 0, коли всі елементи масиву буде оброблено.
Попереднє рішення має часову складність O(n), де n — розмір вхідних даних.
19. Як відсортувати масив із двома записами, які перемикаються за одну операцію.
Сортувати масив у лінійному часі з двома поміняними місцями елементами та масивом, усі його елементи розташовані в порядку зростання. Уявіть, що масив не містить дублікатів.
Вхід:= [1,9,3,4,7,2] або [9,3,7,2,1,4] або [2,4,1,7,3,9]
Вихід: = [1,2,3,4,7,9]
Починаючи з другого елемента в масиві, метою є порівняння кожного елемента з його попередником. Позиція суперечки зберігається за допомогою двох покажчиків x і y.
Оновіть x до індексу попереднього елемента та y до індексу поточного елемента, якщо перший більший за останній. Оновіть y до індексу поточного елемента, якщо виявиться, що попередній елемент більший за поточний.
Нарешті, поміняйте елементи з індексами x і y, коли ми закінчили обробку кожної суміжної пари елементів.
Через те, що вищезгаданий метод виконує лише одне сканування вхідного масиву розміром n, його часова складність становить O(n). Для рішення не потрібна додаткова кімната.
20. Як об'єднати два відсортованих масиви на місці.
Об’єднайте елементи масивів X[] і Y[] — два відсортованих масиви розміром m і n кожен — зберігаючи відсортований порядок, тобто заповнюючи X[] першими m найменших елементів і заповнюючи Y[] інші елементи.
Якщо елемент у масиві X[] уже знаходиться у правильній позиції (тобто найменшій серед решти елементів), ігноруйте його; інакше замініть його найменшим елементом, який також є першим членом Y[]. Щоб зберегти відсортований порядок після заміни, перемістіть елемент (тепер у Y[0]) у належне місце в Y[].
Розмір першого масиву дорівнює m, а розмір другого масиву — n, а часова складність — O(mn).
21. Як змінити порядок масиву елементів у високих і низьких позиціях, що чергуються?
Переставте цілочисельний масив так, щоб кожен наступний елемент був більшим за попередній і наступний елементи. Припустимо, що масив не містить повторюваних елементів.
Для ефективного підходу не потрібно сортувати масив або використовувати додатковий простір. План полягає в тому, щоб почати з другого елемента масиву та збільшити його на два для кожної ітерації циклу.
Поміняйте компоненти місцями, якщо останній елемент перевищує перший. Подібним чином поміняйте обидва елементи, якщо наступний елемент більший за поточний. Після завершення циклу ми отримаємо потрібний масив, який відповідає вказаним обмеженням.
22. Як замінити кожен елемент масиву без використання оператора ділення на добуток кожного елемента масиву?
Без використання оператора ділення замініть кожен елемент у цілочисельному масиві добутком усіх інших елементів.
У лінійному часі та постійному просторі ми можемо використовувати рекурсію для вирішення цієї проблеми. Рекурсивне обчислення добутків кожного елемента правого підмасиву та передача добутку лівого підмасиву як параметрів функції — це поняття.
Часова складність дорівнює O(n).
23. Знайти найнепарніший елемент у масиві за логарифмічний час
Дано цілочисельний масив, у якому всі члени, крім одного, мають парну кількість входжень, проблема полягає в тому, щоб визначити, скільки разів цей один елемент з’являється. Знайдіть непарний елемент у логарифмічному часі та постійному просторі, якщо однакові елементи зустрічаються парами в масиві, і ніколи не може бути більше двох екземплярів даного елемента в рядку.
Операція XOR дозволяє нам вирішити цю проблему за лінійний час. Мета полягає в тому, щоб XOR кожен елемент у масиві. Лише непарні елементи залишаються після того, як парні елементи компенсують один одного.
Цю проблему можна навіть вирішити за час O(log(n)).
24. Як отримати наступний більший елемент для кожного елемента в круговому масиві?
Має бути розташований наступний більший елемент для кожного елемента в циклічному цілочисельному масиві. Перше більше ціле число після елемента x у масиві є наступним більшим елементом цього елемента.
Справа наліво ми можемо оперувати елементами масиву. Мета полягає в тому, щоб виконати цикл для кожного елемента x, поки або стек не буде порожнім, або ми матимемо вищий елемент поверх нього. Встановіть, щоб наступний більший елемент x з’являвся на вершині стека, коли він з’являється.
25. Знайти кількість інверсій масиву?
Знайдіть загальну кількість інверсій масиву. Пара I j) називається інверсією масиву A, якщо I j) і (A[i] > A[j]). Ми повинні порахувати кожну пару з них у масиві.
Підрахунок усіх членів масиву, менших за нього праворуч, і додавання результату до результату є простим підходом.
Це рішення має складність O(n2), де n — розмір вхідних даних.
26. Що таке проблема уловлювання дощової води?
Знаходження найбільшої кількості води, яка може бути захоплена даним набором смужок шириною в одну одиницю кожна, відоме як проблема «уловлювання опадів».
Мета полягає в тому, щоб визначити найвищу смугу, яку можна розмістити ліворуч і праворуч від кожної смужки. Мінімальна кількість початкових стовпчиків ліворуч і праворуч, за вирахуванням висоти поточного стовпчика, є кількістю води, що зберігається на вершині кожного стовпчика.
Висновок
Порівняно з іншими темами структури даних, масиви простіші. Щоб правильно відповідати на питання інтерв’ю з масивами, вам потрібно мати фундаментальне розуміння масивів.
Щоб успішно відповідати на запитання інтерв’ю щодо масиву, вам слід докладно переглянути основи масивів, зокрема операції з масивами (від оголошення/створення масиву до доступу до/зміни елементів масиву), а також такі концепції програмування, як цикли, рекурсія та основні оператори. Повністю визнайте проблему.
Ви повинні отримати роз’яснення, якщо у вас є якісь запитання. Подумайте про те, щоб розділити проблему на більш зрозумілі частини. Перед початком програмування переконайтеся, що ви маєте на увазі алгоритм; запишіть це або візуалізуйте це на блок-схемі. потім почніть писати код.
залишити коментар