Питання на інтерв’ю

Один з найпопулярніших питань на інтерв'ю для java-девелопера це прохання перевернути масив. Це дуже схоже на питання з минулої статті, про перевертання рядки. але трохи про інше. Питання не виглядає складним, все що потрібно зробити це створити новий масив такого ж розміру, перебрати вихідний масив від кінця до натиснула заповнюючи новий. Все готово. Але ні, ми ж створили додатковий масив того ж розміру, що й вихідний, що ускладнює наше рішення O (n). Ми не зможемо використовувати наше рішення, якщо розмір масиву дуже великий (наприклад 10 млн елементів), а розмір heap невеликий. Що ми можемо тут зробити? Як поліпшити наше рішення? Чи можемо ми перевернути масив не створюючи додатковий буффер? Для нашої задачі припустимо, що у нас масив з integer (взагалі на інтерв'ю хороша практика ставити правильні питання в правильних місцях, як кажуть знаючі люди це риса хорошого програміста). Ключове тут зрозуміти, що вам потрібно перевернути вихідний масив, ми не можемо використовувати інший масив, але використовувати одну дві додаткові змінні, цілком допустимо. Так само неприпустимим є використання сторонніх бібліотек або Java API які можуть зробити цю роботу за нас, а також методів класу java.util.Arrays. за винятком Arrays.toString () щоб виводити масиви. Коли наші вимоги з'ясовані приступимо до вирішення завдання.

Перше що приходить в голову це перебрати всі елементи масиву і поміняти їх місцями. Перший елемент і останній, другий елемент з передостаннім, і т.д. В цьому випадку всі елементи масиви будуть перевернуті без використання додаткового буферу. Ключова річ тут, яку потрібно тримати в голові це тільки що нам потрібно міняти місцями елементи до того моменту як ми досягнемо середини масиву, інакше ми отримаємо той же самий масив. Виникає закономірне питання, а що якщо масив має парну кількість елементів? В цьому випадку в середині масиву будуть два елементи, і нам потрібно поміняти їх місцями, тому наша умова перебору буде містити вираз index <= middle а не index

Як то кажуть, краще один раз побачити, ніж 100 разів прочитати.

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

Нижче мій набір JUnit тестів для нашого reverse (int [] input) методу. Наші тести повинні покривати випадки, коли масив порожній, коли замість масиву null. масив містить один елемент, масив має парне і непарне кількість елементів.

Поки все. Далі буде.