Leetcode #14: Longest common prefix.

Решить эту задачу за O(n) можно не менее чем тремя подходами:

- horyzontal scanning,
- vertical scanning,
- trie.

Сканирование выполняется через циклы. В горизонтальном берем за предполагаемый общий префикс первый элемент - и погнали сравнивать со следующими строками.

Рабочее решение без особых оптимизаций:

const longestCommonPrefix = (strs) => {
    let prefix = strs[0];

    for(let i = 1; i < strs.length; i++) {
        let j = 0;
        while(j <= strs[i].length) {
          
          if(strs[i][j] !== prefix[j]) {
            prefix = prefix.slice(0, j)
            break;
          }
          j++;
        }
    }
    
    return prefix;
};

Leetcode #20: Valid Parentheses

Классическая, уже не раз пройденная задача почему-то далась не с первого раза. В любом случае, кучу проверок в блоке if считаю правильным заменять словарём.

/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function (s) {

    if (!s || s.length % 2) {
        return false;
    }

    const map = {
        '(': ')',
        '[': ']',
        '{': '}',
    }

    const stack = [];

    for (let i = 0; i < s.length; i++) {
        const currentChar = s[i];

        if (map[currentChar]) {
            stack.push(currentChar);
        } else {
            const top = stack.pop();
            if(map[top] !== currentChar) {
                return false;
            }
        }
    }

    return stack.length === 0;
};

Задачи с собеседований. Контекст выполнения.

Задача 1. Что выведется в консоль? Почему?

    let baz = 0;

    let foo = {
        bar1: function() { return this.baz },
        bar2: () => this.baz,
        baz: 1
    }

    let fooCopy = {
        bar1: foo.bar1,
        bar2: foo.bar2,
        baz: 2
    }

    console.log(fooCopy.bar1());
    console.log(fooCopy.bar2());

Давайте думать.

* This - это указатель на объект, поля и свойства которого может использовать функция внутри своего кода. Объект называется контекстом выполнения.

* Контекст определяется через:
- Вызов функции через точку: obj.foo()
- Привязку через call, bind и apply.

* This указывает на поля или методы объекта, а не переменные (хотя переменные и являются в каком-то смысле полями объектов).

* Функции-стрелки наследуют контекст от функции, в которой были определены, - своего лексического окружения.

* Мы видим, что копии присвоено два метода: один - классическая функция, другой - стрелка.

* Вызван ли метод foo.bar1, присвоенный копии, через точку - иначе говоря, привязан к какому-то контексту выполнения? Да! Следовательно, выведет 2.

* Внутри какого метода находится функция-стрелка? Никакого. Значит, this будет унаследован из глобального объекта. Указан ли строгий режим? Считаем, что по-умолчанию указан. Значит, вернется undefined.

Задача 2. Что вернут функции? Почему?

function outerFunction() {
  this.value = 10;

  return function innerFunction(x) {
    this.value += x;
    return this.value;
  };
}

const instance1 = new outerFunction();
const instance2 = outerFunction();

console.log(instance1(5));
console.log(instance2(5));

Что здесь нужно знать:

1. Классические функции можно вызывать как конструкторы - неважно, с большой буквы или с маленькой они будут называться. Это не Реакт-компоненты.

2. Если конструктор:
- Ничего явно не возвращает, то возвращает конструируемый объект.
- Явно возвращает примитив - он игнорируется, возвращается конструируемый объект. Но! Если вызывать конструктор без new - вернется этот примитив.
- Явно возвращается объект - возвращается этот объект, с new и без.

3. Функции являются объектами.

В данном случае функция всегда будет возвращать замыкание, которое обращается к полю глобального объекта и его увеличивает.

Поэтому первый вызов выведет 15, а второй - 20.

Задачи с собеседований. Цепочки промисов.

Какая последовательность выведется в консоль?

const p = new Promise((_, reject) => {
        setTimeout(() => {
            console.log('reject')
            reject();
        }, 2000)
    })

    p.then(
        () => console.log('10'),
        () => console.log('11')
    ).then(
        () => console.log('13'),
        () => console.log('14')
    )

    p.then(
        () => console.log('18'),
        () => console.log('19')
    )

    p.then(
        () => console.log('23'),
        () => console.log('24')
    )

Нужно понимать следующее:

1. Регистратор обработчиков then принимают две функции: на успешное выполнение промиса и на его реджект.

2. Обработчики регистрируются в порядке объявления в синхронном коде.

3. Каждый обработчик возвращает новый промис.

4. Из обработчика можно:
- Явно что-то вернуть (таким образом неявно вернув резолвнутый промис)
- Резолвнуть промис (и вернуть резолвнутое значение)
- Реджектнуть промис (и вернуть реджектнутый промис)
- Бросить ошибку (и вернуть реджектнутый промис с этой ошибкой)
- Ничего явно не возвращать - и резолвнуть промис со значением undefined.

5. Следовательно, в коде отработают последовательно три обработчика реджекта, а затем вызовется обработчик успешного выполнения промиса в первой цепочке:

Reject, 11, 19, 24, 13

Leetcode 26. Remove Duplicates from Sorted Array

На примере этой задачи удобно понять и применить метод двух указателей.

Этот метод можно применять, когда:
- на вход подается линейная (массив, строка...) упорядоченная структура;
- требуется слить два (отсортированных) массива, проверить симметрию данных (valid palindrome), найти минимальную разницу между элементами, найти самую длинную подстроку без повторений - либо, как здесь, найти количество уникальных элементов; и другие подобные задачи.
- Сложность по времени не должна превышать O(n). Как правило, сложность по памяти не превышает О(1).

Он неприменим для нелинейных структур, таких как деревья.

Этот подход включает такие модификации, как "плавающее окно" или обход двух структур параллельно.

Вот решение:

var removeDuplicates = function(nums) {

    if(!nums.length) return 0;

    let i = 0;
    let j = 1;

    while(j < nums.length) {
        if(nums[i] !== nums[j]) {
            nums[i+1] = nums[j];
            i++;
        }
        j++;
    }

    return i+1;
};

Leetcode 27. Remove Elements

Аналогичная задача. Обходим массив с начала и конца, пока не избавимся от всего лишнего слева.

Ссыль на задачу: https://leetcode.com/problems/remove-element/

var removeElement = function(nums, val) {
    let i = 0;
    let j = nums.length-1;

    while(i <= j) {
        if(nums[i] === val) {
            nums[i] = nums[j];
            j--;
        } else {
            i++;
        }
    }

    return i;
};

Leetcode 27. Plus One

Смысл задачи - прибавить единицу к большому числу. Число может содержать до 100 цифр. Оно представлено в виде массива.

Решить можно двумя способами. Один хотят увидеть интервьюеры, а второй - однострочник, который раздует ваше эго :)

Начнем с приятного :) Соль задачи в том, что число большое. То есть, преобразовать к Number не выйдет.
Пригодится знание, что BigInt допускает операции только со своим типом. Прибавить единицу к BigInt явно - нельзя: сначала приведите ее к тому же типу.
Также важно знать, что конструктор BigInt принимает строки и числа.

var plusOne = function(digits) => (BigInt(digits.join('')) + BigInt(1)).toString().split('').map(el => Number(el));

Классический вариант работает так:

1. Пробегаемся по массиву с конца.
2. На каждой итерации прибавляем к элементу 1 и проверяем, меньше ли он 10. Если меньше - подменяем его суммой и возвращаем массив. Если больше - подменяем на 0 и идем дальше. Так бывает, когда элемент равен 9.
3. В случае, если число состоит из 9, все элементы заменятся на 0 и цикл завершится. Тогда к массиву прибавим единицу слева и вернем его.

/**
 * @param {number[]} digits
 * @return {number[]}
 */
var plusOne = function(digits) {
    for(let i = digits.length - 1; i >= 0; i--) {
        let currentDigit = digits[i] + 1;
        if(currentDigit < 10) {
            digits[i] = currentDigit;
            return digits;
        }
        digits[i] = 0;
    }

    digits.unshift(1); // внимание! Не возвращайте результат unshift. Вернет свой последний аргумент, а не массив.

    return digits;
};

Задачи с собеседований. Напишите кастомный метод массива.

Что от вас ждет собеседующий:

1. Понимания прототипного наследования.
2. Нюансов работы с экземпляром массива.

Возьмем для примера кастомный метод Array.some:

Array.prototype.customSome = function(func) {
    const result = [];

    for(let i = 0; i < this.length; i++) {
        if(func{this[i]}) result.push(this[i])
    }

    return result;
}

Leetcode 69: Sqrt(x).

Задача проста: написать свою функцию нахождения квадратного корня.

Что нужно знать из математики:

- Для 0 и 1 нужно возвращать их самих.
- Решение всегда в меньшей половине числа, если оно больше 2.

Что по алгоритму:
- Массив создавать не нужно! Для больших чисел это вызовет переполнение памяти.
- Быстрее всего работает двоичный поиск.
- Для случая, когда точного корня не найдено, возвращать надо правый указатель: он всегда на шаг меньше целевого числа.

Хотите потроллить интервьюера? Дайте ему такое решение: Math.floor(x ** 0.5) 😁

function mySqrt(x) {
    if(x < 2) {
        return x;
    }
    
    let rightPointer = Math.floor(x / 2);
    let leftPointer = 1;
    
    while(leftPointer <= rightPointer) {
        let midPointer = Math.floor((leftPointer + rightPointer) / 2);
        let value = midPointer * midPointer;
        if(value === x) {
            return midPointer;
        } else if(value > x) {
            rightPointer = midPointer - 1;
        } else {
            leftPointer = midPointer + 1;
        }
    }

    return rightPointer;
}

Все точки над SOLID

Лао-Цзы учил:

"Одно породило два.
Два породило три".

В случае с SOLID одно породило пять. За всеми принципами SOLID стоит один замысел:

Low coupling, high cohesion.

Coupling - это связанность. Cohesion - это связность.

Связанность - это уровень зависимостей в коде.
Высокая связанность - случайные, циклические зависимости.
Низкая связанность - минимальные зависимости.

Связность - это логическая связь между элементами кода.
Низкая связность - это логичная организация кода по модулям, утилитам, доменным областям, простые, понятные интерфейсы.

Каждый принцип SOLID выражает low coupling, high cohesion.

- SRP ограничивает сущности одной областью ответственности.

- OCP ограничивает модификацию сущность (но позволяет модифицировать в рамках ее ответственности).

- LSP позволяет пользоваться разными модификациями одной сущности, ничего принципиально не меняя.

- ISP помогает SRP: одна сущность не принимает 10 разных аргументов. Одна сущность принимает несколько интерфейсов, разделяющих принимаемое логические.

- DIP безупречно выражает low coupling. Зависимость должна приспосабливаться к клиентскому коду через интерфейс, а не наоборот. Результат - легкая подмена глобальной БД на локальную или продовской зависимости на моки для тестов без боли.

Подумайте об этом, чтобы не смущаться ни на собеседовании, ни в работе.

Leetcode 67: Add Binary.

В этой задаче, как и в прошлой, есть ожидаемое решение, а есть тролльский однострочник:

var addBinary = (a, b) => (BigInt('0b' + a) + BigInt('0b' + b)).toString(2);

Оставлю разбираться с его тонкостями для вас. 😁

Один из вариантов ожидаемого решения представлен ниже. В нём мы нормализуем данные, добавляя нули в более короткое. Это нужно, чтобы обойтись только одним циклом. Затем мы на каждой итерации проводим несколько вычислений:

- Что прибавить к результату
- Остаток от двоичного сложения

Если остаток сохранится после цикла, докидываем в результат.

Одна из оптимизаций этого решения - заранее создавать массив длиной maxLength, чтобы сэкономить на операциях вставки (в данном алгоритме мы каждый раз создаем новую строку).

var addBinary = function(a, b) {
    const maxLength = Math.max(a.length, b.length);
    a = a.padStart(maxLength, '0');
    b = b.padStart(maxLength, '0');
    let carry = 0;
    let result = '';

    for(let i = maxLength-1; i >= 0; i--) {
        const currentSumBits = Number(a[i]) + Number(b[i]) + carry;
        result = (currentSumBits % 2) + result;
        carry = Math.floor(currentSumBits / 2);
    }

    if(carry) result = carry + result;

    return result;
}

Задачи с собеседований. Путаница с ключами.

Вас спрашивают: что выведет в консоль?

const a = { a: 5 }
const b = { b: 10 }

const c = {};

c[a] = a;
c[b] = b;

console.log(c[a].a, c[b].b)

На первый взгляд, будет 5 и 10. Но это не так! Почему?

Дело в том, что стандартный объект в JS - это хеш-таблица. Почему? Чтобы обращаться к ключам объектов за O(1).

В стандартном объекте реализация хеш-таблицы простая: ключи (кроме символов) приводятся к строкам, строки - к хешу, по хешу движок ищет ключи.

Если привести объект к строке, будет 'Object object'.

В задаче мы дважды присваиваем объекту "c" поле 'Object object' со ссылкой на объект. Что происходит, когда одному полю значения присваиваются несколько раз? Сохраняется только последнее присвоенное значение.

В итоге, в поле c['Object object'] будет храниться ссылка на объект b. Поля "a" в объекте "c" не существует.

Поэтому результат такой: "undefined 10".

Изучите, к какому виду строки приводятся структуры в JS. И запомните принцип, что любая не-строковая структура, кроме Symbol, используемая как ключ объекта, приводится к строке.

Leetcode 70. Climbing Stairs.

Эта задача - база рекурсии и динамического программирования.

Запомним:
- ДП всегда итеративно и работает за O(n) по скорости и O(1) по памяти. Работает по принципу Bottom-Top: разворачивает задачу от базовых случаев к заданному пределу.
- Рекурсия с мемоизацией работает за O(n) по скорости и O(n) по памяти. Работает по принципу Top-Bottom: идет сверху вниз, пока не встретит базовый случай.

Рекурсивное решение на каждом шаге вычисляет комбинацию шагов для n-ной ступеньки, после чего спускается вниз и считает снова. Те, кто решал задачу чисел Фибоначчи, найдет код знакомым:

const memo = {};
var climbStairs = function(n) {
    if (n <= 1) return 1;

    if(memo[n]) return memo[n];

    const currentCalc = climbStairs(n-1) + climbStairs(n-2);
    memo[n] = currentCalc;
    return currentCalc;
};

Leetcode 70. Remove Duplicates from Sorted List

Эта задача не станет сюрпризом для тех, кто писал свой Linked List.

Дан указатель на голову листа. Создаем на него указатель. В цикле перебираем ноды: пока есть текущая и следующая ноды, проверяем, совпадают ли значения. Если совпадают - следующая за следующей нода становится на место следующей. Иначе следующая занимает место текущей.

Можно решить и рекурсивно, однако решение займет O(n) по памяти.

var deleteDuplicates = function(head) {

    let temp = head;

    while(temp && temp.next) {
        if(temp.next.val !== temp.val) {
            temp = temp.next;
        } else {
            temp.next = temp.next.next;
        }
    }

    return head;
};

Leetcode 94. In-order обход дерева.

Это простой рекурсивный обход бинарного дерева. О деревьях и типах обхода (DFS, BFS, In-Order, Post-Order, Pre-Order...) уже писал ранее.

Чтобы понимать этот код, нужно уяснить, как работает стек при рекурсии.

Функция traversal вызывается на корне дерева. Далее в стек помещаются последовательно все вызовы на левых нодах - до тех пор, пока в вызов не будет передан null. После этого наполнение стека закончится. Произойдет неявный возврат undefined. Интерпретатор сможет выполнить следующую операцию - закинуть в массив значение предыдущей ноды. Затем вызывается та же функция на правой ноде, и процесс повторяется до исчерпания дерева.

var inorderTraversal = function(root) {
  const result = [];

  function traversal(node) {
      if(node) {
        traversal(node.left);
        result.push(node.val)
        traversal(node.right)
      }
  }  

  traversal(root)

  return result;
};

Мои главные ошибки в программировании за 5 лет

Накопились, скажем так, точки роста. :) А именно:

1. Поверхностный анализ задач.
Чтобы решить задачу на 100%, нужно:
- внимательно прочитать задачу
- понять, какого результата ожидает заказчик
- понять, откуда брать данные и готовы ли они
- провести небольшой ресерч, как решать такую задачу
- обсудить с заказчиком все непонятные тонкости
- брать задачу в работу

Но моя автоматическая реакция - бегло прочесть задачу и сразу взять в работу. Заказчик ожидает, что я все понял. Если повезет и задача типовая, ожидания и реальность совпадают. Если нет - я запрашиваю информацию по ходу дела и ставлю задачу на паузу. Она переезжает в следующий спринт.

Что изучить, чтобы так не делать?

Лекция по анализу задач: www.youtube.com/watch?v=ugGT4T5HcsI&t=9263s
Курс по софт-скиллам: https://youtube.com/playlist?list=PLfDKoUW4baOdVtmuBkfLt649c2L8KqZmx&si=CVc2ekvITCVBIqlN

2. Программирование реализаций, а не интерфейсов.
Сначала пишу код, потом подгоняю интерфейс.
Это неверный подход. Ни о каком LSP или DI не может быть и речи, когда ты не знаешь заранее, что код принимает и возвращает. Ты не видишь место кода в системе.
Напротив, спроектированный заранее интерфейс создает Black Box, который задает написанию коду понятные рамки.
Теперь я проектирую систему заранее, а реализации пишу после.

3. Изучение решений вместо проблем.
Например, учу TypeScript, а не теорию типов и область применения типов данных.
Так можно стать мидлом, но не синьором.

4. Развитие только в технологии.
Скачок в карьере дает только понимание, как код конвертируется в ценность (например, выручку компании). Это помогает расставлять приоритеты, выбирать технологии не по хайпу, а по потребностям домена, и общаться с коллегами от бизнеса на их языке.

Чистая архитектура - зло?

В блоге "Кодируем" (@koduryem) узнал, что кто-то из нас говорит: чистая архитектура - творчество университетских программистов, раньше писали без них и все летало!

Я прокомментировал:

"Правильное применение абстракций связано с рефакторингом. Изначально приложение может быть минималистичным. С ростом кодовой базы растет сложность. Мы ее периодически сбиваем, делая рефакторинг по принципам чистой архитектуры. Вот и все. Минимализм важен, чистая архитектура - тоже важна, всему свое место."

Более того, накидывать абстракции заранее - нормально. Опытный разработчик может предсказать, в какую сторону будет расти проект, и заранее абстрагировать пару фабрик. Остальное применит в ходе рефакторинга. Неопытный абстрагирует все, что может, потому что хочет показать свой профессионализм. Другие споткнутся об его код, упадут и закричат на весь интернет, что чистая архитектура - зло. :)

Этим постом ставлю точку над срачем, зло чистая архитектура или нет ✅

ChatGPT уже заменил программистов?

Встречал на vc.ru статьи от СЕО маленьких компаний, которые с восторгом отзывались о GPT:

"Бот написал код по моему ТЗ, и я сам собрал его по инструкции. Мой программист мне больше ни к чему!"

Что здесь не так?

- Нет времени. Запустить продукт - мало, его нужно поддерживать, рефакторить, чинить и развивать.
- Нет экспертизы. Даже старшие разработчики не всегда понимают, как задать ChatGPT вопрос. Ответы O1-preview (лучшая модель OpenAI) слишком общие, и даже она ошибается.
- Нет ответственности. Бот ни за что не отвечает, юридическая база ответственности компаний-провайдеров ИИ отсутствует.

О массовых увольнениях программистов, как видите, не может быть и речи.

You don't know React

После 5 лет в разработке с радостью узнал, что Реакту еще учиться и учиться. Например:

- Compound Components Pattern, который реализует Open-Close Principle.
- Provider hell - лесенку оберток вокруг App - легко избежать через хелпер, принимающий массив компонентов и параметров.
- Каррирование коллбэков помогает делать чище JSX.

Это лишь мелочи из того, что я узнал. С одной стороны, заставляет усомниться в своем профессионализме. С другой - воодушевляет: пробелы в знаниях понятны, будущий уровень - тоже понятен.

Я продолжу инвестировать время в обучение: амбиции требуют больших компетенций. Заканчиваю материал по TypeScript, начинаю воркшоп по React от Anthony Alicea. В планах - "The Software Architect Mindset" от ArjanCodes и продолжить книгу Luca Mezzalira о микрофронтах.

Правда ли, что в 2025 работу во фронтенде найти сложнее?

Еще недавно было так: закинул резюме на HH, и HR сами пишут пачками. Но в 2025 всё поменялось.

Я сам столкнулся с этим, когда искал позицию синьора в конце 2024. Критерии были простые:

- Х2 к зарплате.
- Возможность в будущем стать тимлидом.

Делал, как раньше: написал резюме левой пяткой, выложил на Хабр Карьеру и hh. Думал, HR сами будут писать пачками. Но… компании смотрели - и не звали на собеседования.

Начал откликаться сам - впервые за всю карьеру. За неделю получил всего 2 приглашения - и не прошел даже HR-собеседование.

Этот результат сильно встревожил. Я не понимал, что делаю не так.

Решил разбираться и вложился в процесс:

- 50 тысяч рублей на карьерные консультации.
- 15 тысяч на подписки и Boosty экспертов, чаты «паровозиков»...
- 40+ видео с интервью.

В результате я оптимизировал резюме под HR и алгоритмы досок объявлений. Понял, как правильно подать свой опыт на скрининге и создать впечатление, что я отлично подхожу под вакансию.

Главное - научился, как не бояться того, что чего-то не знаю. Как грамотно говорить с HR и на техническом интервью - как специалист, а не студент на экзамене.

Вот тогда пошли офферы.

Я настолько обнаглел, что отказался от оффера на почти 300К, потому что они не захотели торговаться выше. :)

И наконец вышел на отличную работу синьором - по ТК, с классным ДМС и карьерными перспективами.

Так что да, стало сложнее. Но если подходить с умом — всё возможно!