Потрібні програмісту алгоритми і структури даних

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

Але стаття буде швидше про перший: про написання робочого ефективного коду, який прослужить довго. Вона буде корисна як новачкам, які шукають можливості для професійного росту, так і для досвідчених фахівців, які знають кілька мов, можуть придушити будь баг і тягнути будь-який проект, але прагнуть до розробки нових проектів.

Денис Цьоменко з доповіддю «Навіщо мені знати алгоритми, якщо вони вже реалізовані?» на RunIT в Дніпрі, травень 2019

Вічний холівар на тему «чи потрібна програмісту математика» піддається зміні і перетворюється в більш небезпечний для індустрії спір. Все частіше на форумах, конференціях і в голові майнула думка: «Треба чи програмісту знати алгоритми і структури даних?». І цей спір має місце бути. Сумнівно, що розробляючи продукт, доведеться самостійно реалізовувати швидке сортування або словник. Просунуті ж структури даних знадобляться не більш ніж 10-20% інженерів. І навіть якщо людина входить у цей відсоток, він заперечить: «Все гуглится і навчається за пару днів».

Думка протилежної сторони виражається так: «Через 5-7 років 80% завдань, які необхідні при розробці продукту, зможуть виконувати школярі 13-14 років, які закінчили якісні курси. Але компаніям потрібні інженери, здатні вирішити інші 20%». Це можуть бути знання і математичної статистики, і в алгебрі і теорії програмування. Але фундамент, в будь-якому випадку, будується на знаннях алгоритмів і структур даних.

Тому співбесіди в FAANG або MINT на 60%-100% складаються з Problem Solving завдань, для розв'язання більшості з яких потрібні знання алгоритмів. Зараз цей тренд переходить і на middle-size компанії в світі і в Україні. З особистого досвіду можу сказати, що я писав на С++, .NET і Python. І незалежно від мови, я використовував знання алгоритмів.

«Не можна довіряти кодом, який ви не написали повністю самі», — Кен Томпсон .

Алгоритми на співбесідах

У кожної компанії є свій підхід до співбесід та оцінки кандидатів. Також відрізняються мети найму. Але є речі, які їх об'єднують. Я проходив співбесіди в різні компанії різних розмірів і напрямків. Десь алгоритми і рішення задач були ключовим фактором, десь- допоміжним. Завдання можуть бути різних рівнів складності. Наприклад, найпростіша з тих, що мені зустрічалися, — розгорнути рядок без використання додаткової пам'яті. Одне із завдань зводилася до вміння швидко вважати максимальне значення функції xor на префиксном дереві (бор). Її складність швидше полягала в неочевидном рішенні, ніж у реалізації. Хороша завдання на співбесіді повинна мати кілька можливих рішень, крім оптимального. Неможливо знати все.

Приклад поганої завдання, яку я зустрів на співбесіді, це знаходження розв'язку системи звичайних диференціальних рівнянь. За досить недовгий час неможливо наблизитися до вирішення, якщо ти не знаєш алгоритм Рунге-Кутты . Такого ж типу співбесіди зазвичай розраховані якраз не на перевірку вміння заучувати рідкісні алгоритми, а на вміння ефективно використовувати стандартні. Чим же відрізняються підходи в різних компаніях?

Великі корпорації

Компаніям-гігантам не важливо, яку мову Ви знаєте або скільки фреймворків вивчили. Microsoft, Google або Tesla не потрібні «виконавці», яких у них десятки тисяч. Цим компаніям потрібні люди, які зможуть придумати і створити новий продукт, оптимізувати застарілий і далі просувати ці компанії вгору. Помножте це на кількість кандидатів і необхідний ресурс для відбору. В результаті отримаємо «алгоритмічні» співбесіди. Такий підхід критикують, намагаються змінити й удосконалити. Наприклад, питаннями по софт скиллам або по дизайну систем. Подібні інтерв'ю іноді відсівають гідних кандидатів, але продовжують проводитися і доводити ефективність.

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

Пройти таке співбесіду допоможуть навіть не знання алгоритмів, а кількість розв'язаних типових задач. Важливо розуміти, що вірне рішення не завжди гарантує успішне проходження співбесіди. Точно також, як і неоптимальне рішення не гарантує відмову. Люди хочуть працювати з людьми, а не з машинами для написання коду, тому хочуть подивитися, як Ви думаєте і говорите. У розвитку цієї навички дуже допомагають пробні інтерв'ю. Ви можете проводити їх з другом, колегою або на різних ресурсах , де можна провести і пройти інтерв'ю з випадковими людьми. Класичним же мануалом по проходженню у великі корпорації є книга «Cracking the Coding Interview» . І якщо Ви хочете потрапити в одну з них, то раджу прочитати.

Мінімальний набір знань для проходження інтерв'ю в великі компанії

Структури даних	Алгоритми	Концепти
Стек/черга	Бінарний пошук	Бітові операції
Списки	BFS/DFS	Пам'ять (Stack vs Heap)
Хеш-таблиці	Сортування (quick, merge, stable, bucket)	Рекурсія
Списки	BFS/DFS	Динамічне програмування
Дерева, графи	—	Big-O notation

Середні компанії

Досвід кращих переймають і організації, які женуться за ними. В Україні існує мінімум 3 компанії, що фокусуються на problem solving interview (DataRobot, Ring Labs, Grammarly). Ще велика частина включає їх в свій процес співбесід як допоміжні.

На певному етапі розвитку компанії їй знадобляться швидкодію, оптимізація і нові круті фішки. А можливо придумати щось нове, не знаючи і не розуміючи існуюче? Відповідь очевидна.

У деяких компаніях середнього розміру можуть зустрічатися завдання, які вимагають точкової підготовки. Це можливо за конкретних вимог проекту і обмежень у кількості набраних кандидатів. Коли ви набираєте 10 людина, а не 1000, тоді ви дійсно хочете відібрати кращих з кращих.

Стартапи

Будь-який успішний стартап — це не тільки крута ідея, але і якісна реалізація. В самому початку шляху, коли пишеться PoC (Proof of Concept), можна ігнорувати і архітектуру, і оптимізацію. У такому випадку при розвитку і розширенні стартапу доведеться виділити час на переписування/ доопрацювання/ рефакторинг.

Здавалося б, при чому тут алгоритми? Problem solving завдання розвивають вміння швидко писати вирішення завдання, не замислюючись про архітектуру. І це часто те, що потрібно для старту: написати «що-небудь», що буде працювати в найкоротші терміни. Тому до «спортивних програмістам» ставляться з побоюванням. Так, вони напишуть для вашого продукту що завгодно за мінімальний час. Чи зможе цей код підтримувати хтось інший? Відповідь на це питання розмитий.

На цій хвилі можна згадати статтю про український стартапі Looksery, який був заснований людьми, пов'язаними з олімпіадами. Вони набирали собі подібних: призерів та учасників ACM ICPC (студентська командна олімпіада), фіналістів IOI (олімпіада для школярів), хлопців з високим рейтингом на CodeForces або TopCoder. Чим закінчилася ця історія, думаю, всі знають, чи можуть дізнатися за посиланням вище.

З іншого боку, співбесіди в стартапи — непередбачувані. Іноді це може бути й одне інтерв'ю про досвід і «чим хочеш займатися», а після цього — офер. В іншому випадку, це може бути тривалий процес з 8+ інтерв'ю різної складності.

Аутсорс

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

Я жодного разу не зустрічав людей, у яких запитували problem solving в аутсорсе. У маленькому /середньому/ великому — не важливо.

Пов'язано це з тим, що аутсорсу потрібно відразу кинути розробника в бій. Їм важливо, щоб він розумів мову, фреймворки, які використовуються на проекті. Також кандидат повинен пройти інтерв'ю з замовником, яким також не вигідно навіть 2-4 тижні навчати співробітника. Додамо сюди великий відсоток legacy-коду, який не те що оптимізувати, а складно підтримувати. В результаті отримаємо інтерв'ю, яке тестує вашу пам'ять, досвід, що завгодно, але не вміння розв'язувати задачі. До того ж, у великого аутсорса є свої академії, де готують Trainee, Junior-позиції під себе. Їм вигідно впихнути в голову учня пару фреймворків, ніж намагатися навчити його розв'язувати даремні на проекті завдання.

Якщо у Вас є історії про проходження problem solving interview в аутсорсе — поділіться в коментарях. Будемо сподіватися на краще.

Використання алгоритмів у реальному розробці

За свою кар'єру в різних компаніях в трьох країнах (США, Німеччина, Україна) я, так чи інакше, стикався з алгоритмами. Іноді це неявне використання із застосуванням стандартних бібліотек, іноді — явна реалізація. Навіть звичайне наслідування — це, по суті, граф взаємозв'язків між класами. Виходить, що кожен день на роботі програмісти використовують якийсь алгоритм або структуру даних. Хеш-таблиці, сортування, алгоритми пошуку й інші популярні алгоритми реалізовані в більшості популярних мовах. І чим краще розуміння як ці алгоритми реалізовані всередині, тим легше буде знайти ефективне застосування і не зустріти несподівані баги, які складно відстежити. Два моїх улюблених прикладу, які зустрічалися не один раз, це вигуки: «Чому так довго?» при використанні хеш-таблиць. І другий приклад — це флейк тестів при використанні сортування.

Типовий приклад 1

Дано: довгі рядки приблизно такої структури: «{час}. {багато інформації про те, що сталося в цей момент часу}» (структура може відрізнятися). Для кожного рядка потрібно порахувати якесь значення. Наприклад: скільки разів її переглядали, редагували і т. д.

Програміст вирішує використовувати стандартний dictionary, HashTable, unordered_set, в залежності від мови. Але «під капотом» — це і є хеш-таблиця.

Код написаний, тести проходять, апрув отримали — мерджим і запускаємо в продакшн.

І на виявляли у своєму житті таку отримуємо, що запит виконується довго, оновлення даних так взагалі відбувається пару хвилин. Програміст в розгубленості і паніки.

В чому проблема?

В тому, що теоретично отримання значення хешу в середньому займає константна час роботи. Але отримання цього хеш рядка — лінійно. І з великими рядками це працює вкрай погано. Це якщо не говорити про колізії, які також можуть виникати. У гіршому випадку, отримання значення хешу займає лінійний час від розміру хеш-таблиці.

Що робити?

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

Типовий приклад 2

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

На перший погляд, все просто. Витягуємо потрібні дані. Модифікуємо. Сортуємо стандартним сортом, в який передаємо свій компаратор, ключ і т. д. Якщо немає необхідності модифікувати, то відсортуємо на етапі запиту.

Тести написані, код вже давно майстра. Про це давно забули, додали нові поля в таблиці, клієнт надсилає запити з іншими ключами — сервер працює як годинник. В один прекрасний момент починають проходити тести при перевірці завдань, які ніяк не пов'язані з цією ділянкою коду. Інші програмісти тиснуть перезапуск тестів, і з другої-третьої спроби тести проходять. Розробник думає, що йому не пощастило, і в цей момент виникли проблеми з базою, відвалився докер-контейнер або інший інструментарій. Але це починає відбуватися все частіше і частіше на одному і тому ж тесті. Що сталося?

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

Що робити?

Сортувати по двох ключів: ключу, який потрібен, і унікальному в структурі даних. Наприклад, ID елемента таблиці. Тоді кожного разу результат буде однаковим.

Також допоможе використання стабільних сортувань. Наприклад: stable_sort в С++, Перечіслімого.OrderBy в .Net, sorted в Python (після версії 2.2) або подібне на вашому улюбленому мовою. Навіть якщо стандартна бібліотека не містить стабільну сортування, напишіть самі.

Як підсумок, розуміння, що Ви використовуєте, допоможе вам на таких етапах розробки:

оцінка складності програми на початковому етапі;
оцінка кількості необхідних потужностей і пам'яті;
можливість оптимізації в залежності від специфіки продукту;
не довантажувати величезні бібліотеки заради одного методу;
«крутий» дзеркальний фотоапарат не зробить з вас фотографа.

Хочеш зробити добре — зроби це сам

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

Завдання 1

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

Для цієї задачі можна придумати велику кількість рішень в залежності від вашої інфраструктури, сховища та інших факторів. Одним з підходящих буде використання дерева відрізків (segment tree ).

Кількість користувачів — це величина, яка постійно зростає. До того ж, при великій кількості різних запитів навіть на мільйон користувачів будуть помітні втрати швидкості.

Дерево відрізків дає можливість оновлювати дані за O(logN), отримувати показники для послідовної групи людей теж за О(logN). Так, навантаження на пам'ять збільшилася за рахунок того, що потрібно зберігати два таких дерева (для максимуму і для суми), і вони займають в 4 рази більше місця, ніж масив з даними. Але в моєму випадку це було не критично.

Чому не використовувати готову реалізацію?

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

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

Примітивне дерево відрізків для функції мінімуму

Результат

Як я знаю від колишніх колег, це працює і модифікується до сьогоднішнього дня. Хоча було написано менше ніж за день (разом з тестами). Якби в команді ніхто не чув про такому алгоритмі, то на його пошуки і реалізацію пішли б тижня.

Завдання 2

Люди працюють у великій корпорації. Необхідно оптимізувати бізнес-процеси і документообіг. У кожного співробітника є своя навантаження, кількість необхідних тверджень (підписів) для подальшої обробки документа/ товару. Потрібно максимізувати ефективність і мінімізувати час обробки і витрачені ресурси.

Приклад графа для пошуку максимального потоку

Рішення

При рішенні подібної задачі у мене не було уявлення про лінійної алгебри та транспортної задачі. Але я чув про алгоритм Min Cost Max Flow .

По суті, кожного людини/ транспорт можна представити у вигляді вершини графа з показниками ефективності: кількість оброблених одиниць за час і витрати на них. Між вершинами є послідовні взаємозв'язки, які відомі.

Із змінами, але для вирішення цього застосовувався алгоритм пошуку мінімальної вартості максимального потоку.

Сумніваюся, що даний алгоритм знадобиться мені ще хоч один раз. Але він також цікавий тим, що в базовому варіанті об'єднує три інших: BFS , Форда-Фалкерсона і Белмана-Форда .

Результат

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

Завдання 3. Розбір логів сервера

Дано: Файл логів 100 МБ+. Потрібно налагодити швидкий пошук по цьому файлу. Слова і фрази пошуку — це коди, тексти помилок і ID користувачів (короткі рядки).

Стандартні засоби вже не задовольняли запити проекту і потрібно було придумати більш швидкий спосіб. І знову допоміг алгоритм, який я бачив до цього — Агв-Корасик . Про результати найкраще розповість графік:

Результат

Це було не так давно, але є підозра, що ця реалізація прослужить ще пару років. Якщо інфраструктуру і процеси не змінять раніше.

Як прийшов я до вивчення алгоритмів та поради

Чесно зізнаюся, мені пощастило. Я прийшов у розробку і почав освоювати архітектурні та технічні підходи після вивчення алгоритмів і рішення 1000+ задач на різних ресурсах. І мій шлях виглядав приблизно так: бачиш завдання -> не знаєш, як вирішувати -> вивчаєш, реалізовувати, модифицируешь відповідний алгоритм.

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

При підготовці до проходження інтерв'ю, два найпопулярніших ресурсу — це:

LeetCode . Тут зібрано багато завдань і добірок від easy до hard рівня. Для кожної задачі доступний discuss, де люди діляться ідеями рішень і реалізацією на різних мовах.
InterviewBit . Тут завдання розділені за рівнями і темами. Також можна встановити кількість днів до інтерв'ю і бачити свій прогрес. Плюс для кожної задачі представлені поради та рішення.

Існують також ресурси, які пропонують навчання на більш ігровій формі. Наприклад: Codewars або Code in game .

Якщо ж ви захочете перейти на наступний рівень, вивчати просунуті алгоритми і вирішувати пов'язані з ними задачі, то варто поглянути на змагальні сайти, такі як Topcoder , Codechef та інші.

А також абсолютно всім раджу ознайомитися з книгою «Алгоритми. Побудова і аналіз» Томаса Кормена. У ній докладно описані більшість популярних алгоритмів. До того ж, книга написана зрозумілою мовою і легко читається, як в оригіналі, так і в перекладі.

Висновки

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

Коли ви працюєте з архітектурою, хайлоадом, базами даних, знання алгоритмів і структур даних вам однозначно знадобляться. Неможливо займатися 3D-моделюванням, машинним навчанням, IoT-розробкою, не заглиблюючись у деталі і нюанси алгоритміки. Будь-яка галузь, де потрібна оптимізація пам'яті або часу, вимагає цього. Вони допоможуть вам у виборі архітектури. Ви не зможете вибрати графову базу даних для свого проекту, якщо не знаєте, що таке граф.

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

Досвідченим розробникам, яким на даний момент не потрібні знання подібного характеру, можу сказати тільки одне: фундаментальні знання допоможуть вам знайти більш цікавий проект, де потрібно буде писати новий функціонал, а не підтримувати і тягнути на собі старий. Невелика частина розробників в захваті від legacy-коду. А може ви дізнаєтеся про якийсь цікавій для вас завдання і зможете покращити існуюче рішення, створити свій продукт на його основі.

Алгоритми і структури даних допоможуть вам просунутися в кар'єрі. На конференції RunIT в Дніпрі, де я виступав з цією темою, людина в залі навів простий приклад: «Одного разу за те, що я зумів вирішити завдання про переміщення шахового коня з однієї клітини в іншу за найменшу кількість кроків, мені підняли зарплату на 500 $». Чого і вам бажаю.

Опубліковано: 02/09/19 @ 10:00
Розділ Різне

SEO Блог