Розв’язуємо задачі з LeetCode. Три приклади на C#

💡 Усі статті, обговорення, новини для початківців — в одному місці. Приєднуйтесь до Junior спільноти!

Привіт! Мене звати Тарас Пивоваров, я Senior Software Engineer у GlobalLogic. У професії я вже близько 13 років. За цей час працював на десктопних проєктах, на вебпроєктах, з JavaScript, хмарними технологіями тощо. Моя рідна мова С#, тому всі приклади в цьому матеріалі я побудую на ній. Також я проводив інтервʼю та бачив, як студенти справляються з кодінг-задачами — це стало додатковою мотивацією до написання матеріалу.

Тож поговоримо про розвʼязання задач із LeetCode. Я хочу поділитися підходом, який мені самому колись допомагав. Основна відмінність моєї статті від інших, як я вважаю, це поступовий прогрес до результату з нескладних кроків. Викладення підходу, який можна застосовувати для багатьох інших задач і в реальній роботі на комерційному проєкті.

Задачі з LeetCode є певним стандартом для прокачування навиків програмування та проходження інтервʼю. Розглянемо, як підходити до розвʼязання задач, як зменшувати їх складність. Спробуємо на практиці розвʼязати 3 задачі, освоїмо пару технік для найбільш поширених алгоритмічних проблем, подумаємо, наскільки важливо опанувати алгоритми і як глибоко варто в них занурюватись.

Кому буде корисно

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

Підхід до розв’язання складних задач

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

Вирішимо 3 hard-задачі, освоїмо деякі підходи на реальних прикладах.

Структура, опис та пояснення задач

Початкові задачі розбиваються на послідовність підзадач, кожна з яких самостійно могла б бути easy-задачею (максимум початковий medium).

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

Для уникнення плутанини рекомендую дотримуватися підходів та інтерфейсів. А внутрішнє наповнення намагатись писати самостійно, звертатись до коду за потреби. Код підзадач не має залежностей, окрім своїх вхідних параметрів та попередніх методів/підпунктів цієї задачі, його легко запускати і перевірити роботу. Вхідні параметри або відомі, або зрозумілі для використання з тестовими даними. Рекомендую на кожному етапі викликати написаний код з власними тестовими даними для самоперевірки. Поїхали.

Задача 1. Вирівнювання тексту

Дано колекцію слів words та довжину рядка maxWidth. Потрібно:

• Зі слів зібрати рядки тексту так, щоб довжина кожного рядка була рівна maxWidth;
• Набирати в рядок максимальну кількість слів, дозаповнювати рядок пробілами ' ', щоб отримати довжину рядка maxWidth.
• Пробіли повинні бути розповсюджені рівномірно між словами. Якщо це неможливо, простір між словами зліва отримає більше пробілів, ніж справа.
• Останній рядок має бути вирівняним до ліва, без додаткових пробілів між словами.
• Слова довші ніж довжина рядка (maxWidth) не траплятимуться.

Приклад вхідних даних:

• words = ["Science","is","what","we","understand","well","enough","to","explain","to","a","computer.","Art","is","everything","else","we","do"]
• maxWidth = 20

Відповідь:

[
  "Science  is  what we",
  "understand      well",
  "enough to explain to",
  "a  computer.  Art is",
  "everything  else  we",
  "do                  "
]

План дій

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

1.1. Вибір слів в рядок

Рахуємо, скільки слів поміститься в один рядок. Оформимо це в метод з таким інтерфейсом:

int GetLineWordCount(string[] words, int maxWidth, int lineStartWordIndex);

Де lineStartWordIndex — індекс слова колекції words, від якого починаємо рахувати рядок. Метод повертає int — кількість слів, що поміщаються в рядок.

Реалізація:

• Проходимо по колекції words, рахуємо суму символів пройдених слів, зупиняємось перед наступним словом, що не поміщається в рядок.
• Крім символів у словах, потрібно врахувати, що між словами має бути мінімум 1 символ пробілу.
• Для 2-х слів мінімум 1 пробіл (слово1+пробіл+слово2), для 3-х слів — 2 пробіли і так далі. Мінімальна кількість пробілів — це кількість слів - 1.

Для даних з прикладу, при lineStartWordIndex=0, код повинен порахувати «Science», «is», «what», «we». В сумі 4 слова (15 символів + 3 пробіли), наступне «understand» вже не поміститься в ширину maxWidth=20. Метод повинен повернути 4.

В мене вийшов такий код:

int GetLineWordCount(string[] words, int maxWidth, int lineStartWordIndex)
{
    int wordCount = 0;
    int wordCharsCount = 0;

    for (int wordIndex = lineStartWordIndex; wordIndex < words.Length; wordIndex++)
    {
        int nextWordCount = wordCount + 1;
        int nextWordCharsCount = wordCharsCount + words[wordIndex].Length;
        int minSpaceCount = nextWordCount - 1;

        // Determine if including one more word still fits the line:
        if (nextWordCharsCount + minSpaceCount > maxWidth)
            return wordCount; // Word doesn't fit the line, quitting without it.

        // This word still fits the line. Include the word and continue:
        wordCount = nextWordCount;
        wordCharsCount = nextWordCharsCount;
    }

    return wordCount;
}

1.2. Розподілення слів по рядках

Тепер можемо пройти по колекції words і розбити її на рядки. Можна оформити це в якийсь тестовий метод. Реалізація:

• Стартуємо з першого (індекс 0) елемента колекції words, рахуємо кількість слів в рядку.
• Переходимо до наступного вільного слова і циклічно повторюємо, поки слова не закінчаться.
• Маючи параметри рядка, можемо зробити тестове виведення на консоль, перевірити результат.

...
int lineStartWordIndex = 0;
while(true)
{
    int lineWordCount = GetLineWordCount(words, maxWidth, lineStartWordIndex);

    if (lineStartWordIndex + lineWordCount == words.Length)
        break;

    for (int wordIndex = lineStartWordIndex; wordIndex < lineStartWordIndex + lineWordCount; wordIndex++)
        Console.Write($"{words[wordIndex]} ");
    Console.WriteLine();
}
...

1.3. Вирівнювання тексту в рядку

Відомі всі необхідні параметри рядка, будуємо слова в текстовий рядок з вирівнюванням. Інтерфейс:

string BuildFullJustifiedTextLine(string[] words, int maxWidth, int lineStartWordIndex, int lineWordCount);

Де lineStartWordIndex та lineWordCount — параметри рядка: індекс стартового слова та кількість слів. Метод повертає string — вирівняний текст рядка.

Реалізація:

• Рахуємо кількість символів в словах рядка (вже розраховано в п.1.1., оптимальніше прокинути звідти, але для простоти інтерфейсів розрахуємо ще тут).
• Знаючи кількість символів в словах і ширину рядка, розрахуємо кількість пробілів в рядку.
• Рахуємо, скільки пробілів потрібно поставити в кожен проміжок між словами: ділимо кількість пробілів на кількість проміжків;
• Якщо поділити націло не вдалось, залишок пробілів розповсюджуємо додатково по одному на проміжок, починаючи зліва.
• Збираємо вирівняний рядок.

Для даних з прикладу, при lineStartWordIndex=0, lineWordCount=4: маємо 4 слова на 15 символів. В рядку шириною 20 буде 5 пробілів. 4 слова мають 3 проміжки між словами. 5 пробілів неможливо розподілити рівномірно на 3 проміжки, маємо 1 пробіл на кожен проміжок і 2 в залишку. Відповідно, 2 залишкових пробіли розкидаємо по перших 2-х проміжках.

string BuildFullJustifiedTextLine(string[] words, int maxWidth, int lineStartWordIndex, int lineWordCount)
{
    // Calculate total number of word chars in line:
    int lineWordCharsCount = 0;
    for (int wordIndex = lineStartWordIndex; wordIndex < lineStartWordIndex + lineWordCount; wordIndex++)
        lineWordCharsCount += words[wordIndex].Length;

    // Calculate total number of spaces in line:
    int lineSpaceCount = maxWidth - lineWordCharsCount;
    // Calculate number of mandatory spaces and remainder that could not be distributed evenly:
    int mandatorySpaceCount = 0; int remainderSpaceCount = 0;
    if (lineWordCount > 1)
        mandatorySpaceCount = Math.DivRem(lineSpaceCount, lineWordCount - 1, out remainderSpaceCount);
        
    // Push first word into the line:
    System.Text.StringBuilder lineBuilder = new(words[lineStartWordIndex]);

    // Push spaces + next words:
    for (int wordIndex = lineStartWordIndex + 1; wordIndex < lineStartWordIndex + lineWordCount; wordIndex++)
    {
        lineBuilder.Append(' ', mandatorySpaceCount);
        if (remainderSpaceCount > 0)
        {
            lineBuilder.Append(' ');
            remainderSpaceCount--;
        }

        lineBuilder.Append(words[wordIndex]);
    }

    // Add trailing spaces if line is shorter then required. Could happen to the line with one word:
    if (lineBuilder.Length < maxWidth)
        lineBuilder.Append(' ', maxWidth - lineBuilder.Length);

    return lineBuilder.ToString();
}

1.4. Додаткове вирівнювання тексту до ліва

Для останнього рядка задача вимагає зробити вирівнювання до ліва. Для цього робимо ще один метод з ідентичними параметрами:

string BuildLeftJustifiedTextLine(string[] words, int maxWidth, int lineStartWordIndex, int lineWordCount);

Реалізація: зʼєднуємо слова в рядок через 1 пробіл і дозаповнюємо рядок до бажаної довжини пробілами в кінці.

string BuildLeftJustifiedTextLine(string[] words, int maxWidth, int lineStartWordIndex, int lineWordCount)
{
    // Push first word into the line:
    System.Text.StringBuilder lineBuilder = new(words[lineStartWordIndex]);

    // Push spaces + next words:
    for (int wordIndex = lineStartWordIndex + 1; wordIndex < lineStartWordIndex + lineWordCount; wordIndex++)
    {
        lineBuilder.Append(' ');
        lineBuilder.Append(words[wordIndex]);
    }

    // Add trailing spaces if line is shorter then required:
    if (lineBuilder.Length < maxWidth)
        lineBuilder.Append(' ', maxWidth - lineBuilder.Length);

    return lineBuilder.ToString();
}

1.5. Формування вирівняних рядків тексту

Останнє, потрібно сформувати остаточні рядки. В п.1.2. вже є код, який виводить слова по рядках. Варто його доповнити і оформити в остаточний метод. Доповнення:

• Після розрахування параметрів рядка сформувати вирівняний текст і зберегти;
• Для останнього рядка застосувати ліве вирівнювання.

IList<string> FullJustify(string[] words, int maxWidth)
{
    List<string> justifiedLines = [];

    int lineStartWordIndex = 0;
    while(true)
    {
        int lineWordCount = GetLineWordCount(words, maxWidth, lineStartWordIndex);

        if (lineStartWordIndex + lineWordCount == words.Length)
        {
            // Justify left for the last line and exit:
            justifiedLines.Add(BuildLeftJustifiedTextLine(words, maxWidth, lineStartWordIndex, lineWordCount));
            return justifiedLines;
        }

        justifiedLines.Add(BuildFullJustifiedTextLine(words, maxWidth, lineStartWordIndex, lineWordCount));
        lineStartWordIndex += lineWordCount;
    }
}

Код одним файлом є тут.

Задача 2. Обчислення булевого виразу

Дано текстовий булевий вираз, потрібно розпізнати і обчислити його. Вираз може мати такі форми:

• t обчислюється в true;
• f обчислюється в false;
• !(subExpr) обчислюється в логічну інверсію вкладеного виразу subExpr;
• &(subExpr1,subExpr2,...,subExprn) обчислюється в логічне AND вкладених виразів subExpr1..subExprn, де n >= 1;
• |(subExpr1,subExpr2,...,subExprn) обчислюється в логічне OR вкладених виразів subExpr1..subExprn, де n >= 1.

Приклад вхідних даних:

expression = "!(&(f,t))"

Відповідь: true

Спершу оцінюється &(f,t) -> false, потім оцінюється !(f) -> true.

План дій

Є 2 основні активності, які треба виконувати:

• Розпізнавати текст в bool-змінну;
• Обʼєднувати bool-змінні логічними операціями до отримання результату всього виразу.

Вирази можуть мати вкладеність. Тобто вираз може бути такий: !(t), а може бути такий: !(!(!(!(t)))). Це рекурсія. Але для спрощення відкладемо її, спочатку розвʼяжемо задачу без підтримки вкладених виразів. Потім, маючи код, що працює на простих виразах, додамо підтримку вкладеності.

2.1. Обчислення без складних підвиразів

Зробимо метод, який обчислює такі типові вирази: t, !(f), &(t,t,f).

2.1.1 Розпізнавання елементарного виразу

Елементарних виразів може бути 2: t та f. Зробимо метод для розпізнавання символу в bool-змінну. Потім використаємо це для розпізнавання елементарних частин в тексті. Інтерфейс:

bool ParsePrimitiveExpression(char primitiveExpressionChar);

Мій код:

bool ParsePrimitiveExpression(char primitiveExpressionChar) => primitiveExpressionChar switch
{
    't' => true,
    'f' => false,
    _ => throw new ArgumentException($"Unexpected primitive expression char: '{primitiveExpressionChar}'")
};

2.1.2 Виконання логічних операцій

Є потреба виконувати логічні операції для одного (!(f)) та двох (&(t,f)) операндів. Для 3+ операндів послідовно виконуватимемо операції з 2 операндами, поступово накопичуючи результат. Зробимо метод, який підтримує все що нам потрібно. Інтерфейс:

bool RunBoolEvaluation(char operatorChar, bool operand1, bool? operand2 = null);

Де operatorChar — символ логічного оператора, operand1 — перший операнд, operand2 — опціональний другий операнд.

Для двох операндів можливі операції | та &. Для одного операнда можливі |, & та !.

Мій код:

bool RunBoolEvaluation(char operatorChar, bool operand1, bool? operand2 = null)
{
    if (operand2.HasValue)
        return operatorChar switch
        {
            '|' => operand1 || operand2.Value,
            '&' => operand1 && operand2.Value,
            _ => throw new ArgumentException($"Unexpected operator: '{operatorChar}'")
        };
    return operatorChar switch
    {
        '|' => operand1,
        '&' => operand1,
        '!' => !operand1,
        _ => throw new ArgumentException($"Unexpected operator: '{operatorChar}'")
    };
}

2.1.3 Пошук роздільників у виразі з декількома операндами

Для виразів з багатьма операндами (t,t,f), потрібно знаходити роздільні коми(,), знати, де закінчується операнд і починається наступний. В першому наближенні можна використати стандартні методи, наприклад, string.IndexOf(','). Але, памʼятаючи, що ми повернемось до складних підвиразів, варто відразу підготувати код, що знаходитиме роздільники лише на своєму рівні, ігноруючи , у вкладених дужках.

Робимо метод, що знаходить наступну , в тексті, в діапазоні заданих індексів. Інтерфейс:

int FindNextSplitterIndex(string expressionText, int searchStartIndex, int searchEndIndex);

Де expressionText — текст для пошуку, searchStartIndex та searchEndIndex — діапазон пошуку. Метод повертає int — індекс першої знайденої ,, або -1, якщо їх немає.

Мій код:

int FindNextSplitterIndex(string expressionText, int searchStartIndex, int searchEndIndex)
{
    int openedBracketsCount = 0;
    for (int index = searchStartIndex; index <= searchEndIndex; index++)
    {
        if (expressionText[index] == '(')
            openedBracketsCount++;
        if (expressionText[index] == ')')
            openedBracketsCount--;
        if (openedBracketsCount == 0 && expressionText[index] == ',')
            return index;
    }

    return -1;
}

2.1.4 Метод обчислення без складних підвиразів

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

bool ParseExpression(string expressionText, int startIndex, int endIndex);

Де expressionText — текст виразу. startIndex та endIndex — індекси діапазону роботи. На цьому етапі вони не обовʼязкові, але надалі, для складних виразів, потрібна підтримка роботи з фрагментом тексту. Метод повертає bool-результат обчислення виразу.

Реалізація:

• Якщо вираз елементарний (напр.: t), відразу вирішуємо його. Розпізнати його просто: текст довжиною в 1 символ може бути лише елементарним виразом.
• Залишається формат &(t,t,f). Стартовий символ — завжди логічний оператор. Внутрішні операнди починаються з startIndex + 2 символи, закінчуються на позиції endIndex - 1.
• Виділяємо вкладені підвирази t,t,f.
• Проходимо від , до ,, виділяємо окремі підвирази. На цей момент очікуються лише елементарні підвирази, розпізнаємо їх, виконуємо логічну операцію.

Код:

bool ParseExpression(string expressionText, int startIndex, int endIndex)
{
    if (startIndex == endIndex)
        // Only primitive expression (ex: 't') can be of this length, parsing it and quitting:
        return ParsePrimitiveExpression(expressionText[startIndex]);

    // Working with nested expression format, ex: '&(some_content)':
    char expressionOperatorChar = expressionText[startIndex]; // First char is operator.
    int nestedStartIndex = startIndex + 2; // Setting initial start for nested content right after '('.
    int nestedEndIndex = endIndex - 1; // Setting end for nested content right before ')'.

    bool? expressionResult = null;
    while (true)
    {
        // Looking for next splitter starting from current position:
        int nextSplitterIndex = FindNextSplitterIndex(expressionText, nestedStartIndex, nestedEndIndex);
        if (nextSplitterIndex == -1)
        {
            // No more splitters after current position. Parsing one last expression from current position to the end:
            bool lastExpressionResult = ParsePrimitiveExpression(expressionText[nestedStartIndex]);
            return RunBoolEvaluation(expressionOperatorChar, lastExpressionResult, expressionResult);
        }
                
        // Next splitter is found, parsing expression between current and next, evaluating and continue:
        bool nextExpressionResult = ParsePrimitiveExpression(expressionText[nestedStartIndex]);
        expressionResult = RunBoolEvaluation(expressionOperatorChar, nextExpressionResult, expressionResult);
        nestedStartIndex = nextSplitterIndex + 1;
    }
}

Підсумуємо результат. Маємо метод, який вміє вирішувати прості вирази. Можемо перевірити його роботу:

string expression = "t";
Console.WriteLine(ParseExpression(expression, 0, expression.Length - 1)); // Outputs: true.

string expression = "!(t)";
Console.WriteLine(ParseExpression(expression, 0, expression.Length - 1)); // Outputs: false.

string expression = "&(t,t,f,t)";
Console.WriteLine(ParseExpression(expression, 0, expression.Length - 1)); // Outputs: false.

Оскільки метод має параметри startIndex та endIndex, можна передати текст зі складними вкладеннями, якщо їх немає в робочому діапазоні метода:

string expression = "!(!(&(t,t,f,t)))";
Console.WriteLine(ParseExpression(expression, 4, 13)); // Parses only '&(t,t,f,t)', outputs: false.

2.2. Додавання підтримки складних підвиразів

Можна перейти до рекурсивної обробки складних виразів. Що міняється: раніше, виділяючи вкладені підвирази, ми приймали їх за елементарні t/f. Тепер на їх місці ними може бути такий самий складний вираз. Потрібно:

• В методі ParseExpression() переглянути місця, де вкладені вирази оброблюються як елементарні, за допомогою метода ParsePrimitiveExpression().
• Замінити обробку елементарного виразу на обробку складного. І вже є код, який це робить, це сам метод ParseExpression().

Тому все, що потрібно, це оновити ParseExpression() з заміною елементарного виклику на складний:

Це все! Тепер ParseExpression() працює зі складними виразами. Можна запускати і перевіряти:

string expression = "!(&(f,t))";
Console.WriteLine(ParseExpression(expression, 0, expression.Length - 1)); // Outputs: true.

Варто зазначити, що настільки простим перехід вийшов завдяки підготованим інтерфейсам: заздалегідь введені параметри startIndex та endIndex, пошук у FindNextSplitterIndex() з урахуванням вкладених дужок. Зазвичай доведеться більше підганяти код при переході від простих до складних структур. Найпростіший підхід реалізації рекурсивного обходу: спочатку реалізувати загальний випадок обробки n-го елемента дерева/структури, потім додати рекурсію.

Код одним файлом є тут.

Задача 3. Драбина слів

Дано колекцію слів wordList, потрібно побудувати послідовність трансформацій від beginWord до endWord і повернути кількість слів в найкоротшій послідовності трансформацій.

• В трансформації наступне слово відрізняється від попереднього на 1 символ.
• Використовуються лише слова із колекції wordList.
• Слова в колекції wordList мають однакову довжину.
• Початкове слово beginWord не обовʼязково є в колекції wordList.

Приклад вхідних даних:

• beginWord = "hit";
• endWord = "cog";
• wordList = ["hot","dot","dog","lot","log","cog"].

Відповідь: 5. Найкоротша послідовність трансформацій: hit -> hot -> dot -> dog -> cog. Складається з 5 слів.

План дій

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

3.1. Визначення, чи слова є трансформацією

Робимо метод, що визначатиме, чи 2 слова відрізняються між собою рівно на 1 символ, тобто можуть бути трансформацією. Інтерфейс:

bool AreWordsOneCharDifferent(string word1, string word2);

Мій код:

bool AreWordsOneCharDifferent(string word1, string word2)
{
    bool diffHappened = false;
    for (int charIndex = 0; charIndex < word1.Length; charIndex++)
    {
        if (word1[charIndex] != word2[charIndex])
        {
            if (diffHappened)
                return false; // Words differ by more than 1 char.
            diffHappened = true; // First difference spotted.
        }
    }

    return diffHappened;
}

3.2. Крок побудови трансформацій

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

void BuildNextStepWords(List<string> unvisitedWordList, ref Stack<string> currentStepWords);

Де unvisitedWordList — колекція доступних слів для пошуку подальших трансформацій. currentStepWords — колекція слів поточного кроку. Використання інших колекцій може сповільнити або пришвидшити роботу, залежно від реалізації. Я використав список (List<>) і стек (Stack<>).

Реалізація:

• Створюємо пусту колекцію, в яку зберігатимемо трансформації наступного кроку.
• Для кожного слова з поточного кроку (currentStepWords) шукаємо трансформації серед доступних слів (unvisitedWordList).
• Видаляємо слова з unvisitedWordList відразу, як вони потрапляють в новий крок, щоб не ходити по колу.
• Додаємо знайдені трансформації в колекцію наступного кроку.
• Приймаємо колекцію слів наступного кроку за новий поточний крок, переписуючи currentStepWords новим значенням.

Код:

void BuildNextStepWords(List<string> unvisitedWordList, ref Stack<string> currentStepWords)
{
    Stack<string> nextStepWords = [];

    while (currentStepWords.TryPop(out string currentStepWord))
    {
        // Loop through unvisited words, find ones with one char diff from current word.
        // There are deletions in loop, iterating from the end to keep 'unvisitedIndex' correct:
        for (int unvisitedIndex = unvisitedWordList.Count - 1; unvisitedIndex >= 0; unvisitedIndex--)
        {
            if (AreWordsOneCharDifferent(currentStepWord, unvisitedWordList[unvisitedIndex]))
            {
                // Word for next step is found, adding to next step, removing from unvisited:
                nextStepWords.Push(unvisitedWordList[unvisitedIndex]);
                unvisitedWordList.RemoveAt(unvisitedIndex);
            }
        }
    }

    // Next step is new current step:
    currentStepWords = nextStepWords;
}

Можна перевірити, як це працює:

...
Stack<string> currentStepWords = new();
currentStepWords.Push("hit");
List<string> unvisitedWordList = ["hot","dot","dog","lot","log","cog"];
BuildNextStepWords(unvisitedWordList, ref currentStepWords);
// current step contains: "hot"
BuildNextStepWords(unvisitedWordList, ref currentStepWords);
// current step contains: "dot", "lot"
...

3.3. Обчислення довжини драбини слів

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

• Будуємо колекцію слів, не взятих в роботу. Початково це вся колекція wordList, яка з ходом кроків зменшуватиметься.
• Будуємо колекцію слів у поточному кроці, на старті в ній буде лише початкове слово beginWord.
• Створюємо лічильник кроків з початковим значенням 1, бо рахуємо слова, а не переходи. У найкоротшій драбині буде 1 перехід, але 2 слова (напр.: hit — > hot).
• Крокуємо по словах, поки не закінчаться варіанти, після кожного кроку перевіряємо, чи досягнули кінцевого слова endWord.

public int LadderLength(string beginWord, string endWord, IList<string> wordList)
{
    List<string> unvisitedWordList = new (wordList);
    Stack<string> currentStepWords = new();
        
    currentStepWords.Push(beginWord);
    int stepCounter = 1;

    // Run word transformation steps:
    while (currentStepWords.Count > 0)
    {
        stepCounter++;
        BuildNextStepWords(unvisitedWordList, ref currentStepWords);

        if (currentStepWords.Contains(endWord))
            return stepCounter;
    }

    // No path from begin to end word is found:
    return 0;
}

Це все. Але рекомендую додаткову оптимізацію: в методі BuildNextStepWords(), ще на етапі формування слів наступного кроку, перевіряти, чи слово не є endWord і робити швидке повернення результату. Це економитиме перевірку наявності кінцевого слова після кожного кроку.

Код одним файлом є тут.

Детальніше про задачі та алгоритми

Ми зайшли на територію складних задач. Ці 3 задачі є хорошим початком. Фактично, поступово розкладаючи задачі на більш прості, брутфорсом можна розв’язувати будь-яку проблему.

Але, на жаль, все не так просто. Є приклади hard-задач, які брутфорсом вирішити дуже легко. Їхня складність полягає в тому, що передбачається використання певної математичної формули. Її потрібно або знати, або вивести по ходу розвʼязання.

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

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

Ми використали дві різні техніки проходу по деревах. В одному випадку, щойно натикаючись на нову вершину, ми переходили до неї, проходячи граф в глибину. В іншому випадку ми вибирали знайдені вершини в одному кроці від поточних, та проходили їх по черзі. До таких підходів легко прийти самостійно, але вони теж типові і описані: пошук в глибину/depth-first search(DFS) та пошук в ширину/breadth-first search(BFS).

Наскільки важливо вміння розвʼязувати задачі

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

Тому я рекомендую зануритись в алгоритми до певного рівня. Вміти вирішувати medium-задачі точно буде корисно, а освоїти їх не так важко. Особливо є сенс занурюватись молодим людям і студентам. JS-фреймворки приходять і йдуть, а алгоритми і через 20 років залишаться ті ж самі.

Що на інтервʼю

Все буде залежати від особливостей компанії/проєкта.

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

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

Заключення

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