Підбірка корисних алгоритмів для співбесіди: задачі на рядки


Дізнайтесь більше про нові кар'єрні можливості в EchoUA. Цікаві проекти, ринкова оплата, гарний колектив. Надсилайте резюме та приєднуйтеся до нас.

У цьому матеріалі ми вирішили розібрати алгоритми, які часто зустрічаються на співбесідах. Як інструмент реалізації ми використали Java.

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

Як працювати з рядками?

У Java рядок як клас являє собою масив символів і ще декілька полів і методів. Детальніше про це можна прочитати у нашій статті. Ми виділили декілька найбільш затребуваних методів для роботи з рядками:

toCharArray () // Повертає масив символів рядки charAt (int x)  // Повертає символ, що знаходиться на вказаній позиції length () // Повертає довжину рядка. Зверніть увагу, це не поле, на відміну від массиваsubstring (int beginIndex)  // Повертає підрядок від вказаного індексу і до кінця строкиsubstring (int beginIndex, int endIndex)  // Повертає підрядок між вказаними индексамиInteger.valueOf () // Переводить рядок в числоString.valueOf () // Переводить число в рядок, аналогічно toString ()

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

Зворотна польська нотація

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

Постфіксна нотація, на відміну від інфіксної, що є звичною для нас, вимагає такий запис арифметичного виразу, коли операнди йдуть перед знаком операції. Не варто забувати і про відмінності в записі лівоасоціативних і правоасоціативних операцій. Наприклад, 1 2 + в інфіксній нотації набуває вигляду як 1 + 2, 1 2 + 3 + – як 1 + 2 + 3, 1 2 3 ^ ^ – як 1 ^ 2 ^ 3.

Знаходження максимального підрядка-паліндрома

Паліндром – рядок, який читається однаково в обох напрямах, тобто такий рядок S довжини n, що S[i] = S[n - 1 - i], де i набуває значень від 0 до n - 1.

Розв’язання “в лоб”

Працює, очевидно, за O (N³). Природно, такий підхід не є оптимальним.

З використанням динамічного програмування

Швидкі алгоритми

Швидкими алгоритмами (за O (N)) розв’язання цієї задачі є алгоритм Манакера, а також алгоритми на суфіксному дереві з використанням швидкого алгоритму пошуку LCA. Проте ж ці алгоритми є важкими для розуміння, а подібна задача нехарактерна для великих об’ємів даних, так що для реальної співбесіди можна використати і простіші варіанти.

Розбиття слова на словникові частини

Задача: дано слово і словник. Необхідно з’ясувати, чи є спосіб розбити це слово на декілька частин, кожна з яких входить до словнка.

Наївний алгоритм

Ми рекомендуємо відмовитися від цього підходу внаслідок високого рівня складності – O (2ⁿ).

Динамічне програмування

Складність становить O (N × L), де L – довжина словника. Вимагається O (N) пам’яті. Приклад такої реалізації, звичайно ж, є на programcreek.com і він, як Ви здогадуєтеся, англійською.

Робота з регулярними виразами

Регулярні вирази – гнучкий інструмент пошуку символьних послідовностей в рядках. У більшості мов програмування, якщо не в усіх, є методи для роботи з регулярними виразами. В Java, наприклад, це пакет java.util.regex. Єдине, що треба програмістові – навчитися використовувати ці методи. Для глибокого вивчення теми можна почитати теорію кінцевих автоматів, на яких побудовані регулярні вирази, а ознайомитися з “регулярками” можна в нашому вступному матеріалі.

Словникові сходи

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

// Вхідні дані:" hit"; "cog"; ["hot"," dot"," dog"," lot"," log"]
// Варіант отримуваного в результаті ланцюжка :" hit" -> "hot" -> "dot" -> "dog" -> "cog"

Пошук углиб

Починати перебирати всі варіанти і спускатися нижче – не найкращий спосіб. Даний метод називається “Пошук углиб”. Щоб такий алгоритм дійсно давав найкоротший шлях, а не перший в лексикографічному порядку, знадобиться O (N!), де N – довжина словника.

Пошук завширшки

Цей метод є оптимальним розв’язанням. Його реалізація наведена на англомовному сайті programcreek.com. Тут використовуються дві черги і, власне, сам алгоритм пошуку завширшки.

Переведення рядка в число

Даний алгоритм реалізований у багатьох мовах. Проте є сенс писати власний парсер, щоб, наприклад, читати введення з потоків, що пришвидшить дію. Якщо Ви вирішили так вчинити, не забудьте врахувати:

  • рядок може бути порожнім, а це означає, що має сенс повернути 0;
  • на початку рядка можуть бути пропуски;
  • у числа може бути знак “мінус”;
  • число може бути в речовій формі;
  • отримане число може виходити за межі типу.

Коректність дужкової послідовності

Задача: даний рядок, в якому використовуються дужки різного типу. Необхідно перевірити, чи є така дужкова послідовність правильною. Неправильним буде, наприклад, таке поєднання: ({)}.

Загалом, тут ми і застосуємо наївний алгоритм, який працює за O (N): наприклад, з використанням стека, куди поміщуються зустрінуті дужки. Таке розв’язання коштуватиме O (N) пам’яті, але можна розв’язати і за O (1) пам’яті, якщо встановити лічильники для кожного типу дужок. У Java можна реалізувати розв’язання цієї задачі використовуючи Hashmap, як говорять на programcreek.com.

Перевірка на паліндромність

При розв’язанні цієї задачі треба враховувати тільки літери і цифри, але не враховувати регістр, інакше кажучи, фраза “А троянда впала на лапу Азора” є паліндромом.

Зауваження. Якщо це питання буде у Вас на співбесіді, то краще запитати, ніж рахувати порожній рядок. Ми вважаємо його паліндромом.

Насправді, розв’язання цієї задачі не надскладне і ми пропонуємо два варіанти.

Спочатку обробити рядок

Спершу можна пройтися по рядку, залишивши тільки літери і цифри, чого вимагає умова і лише потім, скориставшись наївним способом, перевірити, чи є цей рядок паліндромом, що вимагає O (N) часу.

Відразу перевірити рядок

Інший варіант – перевірка рядка без обробки. Ми створюємо два покажчики, ініціалізовані початком і кінцем рядка. Далі вони рухаються по рядку, зміщуючись до центру, поки не стануть вказувати на літеру або цифру. Потім просто перевіряємо їх на рівність. Продовжуємо виконання, поки лівий покажчик не стане більше за правий. Очевидно, що це ті самі O (N), але тут менше константа.

Обидва розв’язання наведені на programcreek.com.

Довгий підрядок без повторюваних символів

На programcreek.com наведено два розв’язання: наївне, за O (N²) часу і O (1) додатковj] пам’яті, а також з використанням HashMap. У Java звернення до HashMap становить O (1), тому друге розв’язання триває O (N) часу, але вимагає більше пам’яті.

Проте за розв’язання цієї задачі на інших мовах програмування, де HashMap не є таким ефективним,  необхідно буде звернутися до поняття z-функції. Тоді рішення займе O (N) пам’яті (менше, ніж для HashMap) і O (N) часу.

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

Київ, Харків, Одеса, Дніпро, Запоріжжя, Кривий Ріг, Вінниця, Херсон, Черкаси, Житомир, Хмельницький, Чернівці, Рівне, Івано-Франківськ, Кременчук, Тернопіль, Луцьк, Ужгород, Кам'янець-Подільський, Стрий - за статистикою саме з цих міст програмісти найбільше переїжджають працювати до Львова. А Ви розглядаєте relocate?


Залишити відповідь

Ваша e-mail адреса не оприлюднюватиметься. Обов’язкові поля позначені *