AVL-дерево. Начало.

Прежде чем погружаться в понятия и код, разберемся с базой: что это и зачем.

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

AVL-дерево, в свою очередь, - самобалансирующаяся разновидность бинарного дерева поиска.

Что это значит?

Это значит, что в AVL-дереве за гарантированное O(log N) выполняются:

- вставка
- удаление
- поиск.

Фантастические показатели! В AVL-дереве с ~1.000.000 элементов поиск будет выполнен, в худшем случае, за 20 операций. Гарантированно.

Обычное бинарное дерево поиска не похвастается такими показателями. Почему? Если последовательно добавлять элементы по возрастанию или убыванию, BST радостно выродится в связанный список.

Цена производительности - сложность. AVL-дерево сходу поймет далеко не каждый программист, а на доске напишет разве что человек дождя. Если данные нужно часто вставлять и удалять, то появляются дополнительные накладки на вращения. Эту проблему решают Красно-Чёрные деревья, более популярный вид сбалансированных структур.

В следующем посте я опишу основные сущности и операции, а после перейдем к коду.

#AVL #деревья #структурыДанных

AVL-дерево. Сущности и методы.

Элементарные и не очень составляющие структуры, такие как поля класса, я называю сущностями. Действия над ними - методами.

Сущности AVL-дерева, помимо типичных для BST:

- height: поле отдельно взятой ноды, описывающее количество нисходящих нод от неё до листа. По высоте root-ноды дерева определяется и высота дерева (а по высоте - N в log N). Используется для вычисления balance factor.
- balance factor: поле отдельно взятой ноды, описывающее разницу между высотами её правого и левого поддеревьев. Это как весы. Нормальный вес колеблется в пределах [-1, 0, 1]; показатели выше или ниже вызывают вращения дерева.

Методы AVL-дерева:

- обычные для BST операции вставки, удаления, поиска, получения минимального и максимального элементов. Вставка и удаление отличаются тем, что после рекурсивного вызова описаны действия над высотой и balance factor-ом, а также балансировка. Рекурсия помогает обойти дерево в высоту в обратном порядке: это ключ к пониманию балансировки деревьев. Обратный обход можно сделать и явно, с помощью итерации и стека, но я не вижу в этом смысла: код усложнится, а выигрыша по скорости нет.
- balance: метод, внутри которого вызываются вращения.
- setbalanceFactor: вычисляет показатель этого поля.
- setHeight: устанавливает изначальный показатель высоты ноды.
- updateHeight: обновляет высоту на основе высот потомков.
- rotate: вращают дерево. Бывают четырёх видов: влево, вправо, вправо-влево, влево-вправо.

В следующем посте покажу дерево, а после - подробно опишу методы.

#AVL #деревья #структурыДанных

AVL-дерево. Код

Прежде чем разбирать методы, посмотрим на готовое дерево:

class AVLNode {
    constructor(key) {
        this.key = key;
        this.left = null;
        this.right = null;
        this.height = 1;
        this.balanceFactor = 0;
    }
}

class AVLTree {
    constructor() {
        this.root = null;
    }

    search(key) {
        const _search = (node, key) => {
            if(!node) {
                return null;
            }

            if(node.key === key) {
                return node;
            }

            if(key > node.key) {
                return _search(node.right, key);
            }

            return _search(node.left, key);
        }

        return _search(this.root, key);
    }

    /** обоабатывает случаи с null-нодами */
    getHeight(node) {
        return node ? node.height : 0;
    }

    setBalanceFactor(node) {
        node.balanceFactor = this.height(node.left) - this.height(node.right);
        return node;
    }

    /** Вычисляет высоту ноды на основе двух потомков  */
    updateHeight(node) {
        node.height = 1 + Math.max(this.height(node.left), this.height(node.right));
    }

    rotateRight(x) {
        const y = x.left;
        const T2 = y.right;

        y.right = x;
        x.left = T2;

        this.updateHeight(x);
        this.updateHeight(y)

        return y;
    }

    rotateLeft(x) {
        const y = x.right;
        const T2 = y.left;

        y.left = x;
        x.right = T2;

        this.updateHeight(x);
        this.updateHeight(y)

        return y;
    }

    rotateRightLeft(x) {
        x.right = this.rotateRight(x.right)
        return this.rotateLeft(x);
    }

    rotateLeftRight(x) {
        x.left = this.rotateLeft(x.left)
        return this.rotateRight(x);
    }

    balance(node, key) {
        const balanceFactor = node.balanceFactor;

        if(balanceFactor < -1) {
            if(key > node.right.key) {
                return this.rotateLeft(node);
            }
            return this.rotateRightLeft(node);
        } else if(balanceFactor > 1 ) {
            if(key < node.left.key) {
                return this.rotateRight(node);
            }
            return this.rotateLeftRight(node);
        }

        return node;
    }


    add(key) {
        const _add = (node, key) => {
            if(node === null) {
                return new AVLNode(key);
            }

            if(node.key > key) {
                node.left = _add(node.left, key, node);
            } else if(node.key < key) {
                node.right = _add(node.right, key, node);
            }

            this.updateHeight(node);
            this.setBalanceFactor(node);

            return this.balance(node, key)
        }

        this.root = _add(this.root, key, null);
        return this;
    }

    delete(key) {
        const _delete = (node, key) => {
            if(!node) {
                return node;
            }

            if(node.key > key) {
                node.left = _delete(node.left, key)
            } else if(node.key < key) {
                node.right = _delete(node.right, key)
            } else {
                if(!node.left) {
                    return node.right;
                }
                if(!node.right) {
                    return node.left;
                }

                const theBiggerLeft = this.getMax(node.left);
                node.key = theBiggerLeft.key;
                node.left = _delete(node.left, theBiggerLeft.key)
            }

            this.updateHeight(node);
            this.setBalanceFactor(node);
            return this.balance(node);
        }

        this.root = _delete(this.root, key);
        return this;
    }

    getMin(node) {
        if(!node.left) {
            return node;
        }
        return this.getMin(node.left)
    }

    getMax(node) {
        if(!node.right) {
            return node;
        }
        return this.getMax(node.right)
    }
}

#AVL #деревья #структурыДанных

Leetcode: 2824. Count Pairs Whose Sum is Less than Target

Ссылка на задачу: https://leetcode.com/problems/count-pairs-whose-sum-is-less-than-target/description/

Это одна из самых простых задач на работу с массивом. Решить можно двумя путями: за O(n^2) и за O(n log n). Наивный перебор первого пути описывать нет смысла, сразу перейду ко второму.

Он включает две стадии:

1. Сортировка массива.
Здесь бутылочное горлышко: общая сложность равна сложности сортировки. Разные методы работают лучше с определенными данными, важно уточнять вид данных. Я взял встроенный метод sort движка V8. В среднем он выполняется за O(n log n).

2. Обработка отсортированного массива.
Выполняется за O(n).
Логика второго шага:
- указатели двигаются навстречу и завершают цикл, когда их значения совпадают.
- на каждой итерации проверяем, выполняется ли условие.
- если условие выполняется, делаем вывод:
☝️условие также будет выполнять пара из элемента sortedArray[left] и любого другого элемента до right, включая и его самого.
тогда вычисляем, сколько всего элементов между left и right, включая right, и добавляем к итоговой сумме пар.
- иначе отбрасываем правый элемент.

Вот код решения:

const countPairs = (nums, target) => {
    const sorted = nums.sort((a, b) => a - b);
    
    let count = 0;
    let left = 0;
    let right = sorted.length - 1;

    while(left < right) {
        if(sorted[left] + sorted[right] < target) {
            count += right - left;
            left++;
        } else {
            right--;
        }
    }

    return count;
};

#leetcode #array #twoPointers

AVL-дерево. Методы, часть 1

Разберем сперва методы работы с вершинами. Напомню, вершина - это количество нод между отдельно взятой нодой и листом. По соотношению вершин дочерних нод структура определяет, надо ли балансировать деревце.

- getHeight(node)
Возвращает либо значение height для текущей ноды, либо 0, если нода является листом (null).

- updateHeight(node)
Докидывает +1 к вершине ноды на пути обратной рекурсии.

- setBalanceFactor(node)
На основе вершин потомков вычисляет balanceFactor, по которому алгоритм определяет, нужно ли вращение. Возвращает ноду для удобства.

#AVL #деревья #структурыДанных

Leetcode: 2000. Reverse prefix.

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

Простая задача, не так ли? Зачем же их решать?

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

Решение без встроенных методов может быть таким:

const reversePrefix = (word, ch) => {
    if(!ch) return word;
    
    for(let i = 0; i < word.length; i++) {
        if(word[i] === ch) {
            let j = i;
            let prefix = '';
            let suffix = '';
          
            while(j >= 0) {
                prefix += word[j];
                j--;
            }
          
            j = i + 1;
            while(j < word.length) {
                suffix += word[j];
                j++;
            }
          
            return `${prefix}${suffix}`
        }
    }
  
  return word;
}

Задачи с собеседований. Отформатировать данные по дате

Задача: Имеются данные формата:

[{
name: "Товар 1",
paid: true,
cost: 79,
date: "2023-06-21T11:22:00.000Z",
}],

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

Задача вскрыла, что задание нужно читать въедливо. Решал час из отведенных 30 минут, потому что переписывал под непродуманные условия.

Решение:

const transformData = (data, paidOnly = false) => {
    if (!Array.isArray(data) || !data.length) {
        return null;
    }

    const hashMap = new Map();

    let i = 0;
    
    while (i < data.length) {
        const { date, name, paid, cost } = data[i];

        if (paidOnly && !paid) {
            i++;
            continue;
        }

        const dateToDay = date.slice(0, 10); 
        const currentDate = hashMap.get(dateToDay);

        const purchase = {
            name,
            cost,
        }

        if (!currentDate) {
            hashMap.set(dateToDay, {
                total: cost,
                purchases: [purchase],
            })
            i++;
            continue;
        }

        hashMap.set(dateToDay, {
            total: currentDate.total + cost,
            purchases: [...currentDate.purchases, purchase]
        })

        i++;
    }

    return hashMap;
}

Leetcode. 2367. Number of Arithmetic Triplets

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

const arithmeticTriplets = function(nums, diff)  // bruteforce
    let count = 0;

    for (let i = 0; i < nums.length; i++) {
        let firstNumber = nums[i] + diff;
        let secondNumber = nums[i] + (diff * 2);

        let triplet = [];

        let j = i+1;

        while(j < nums.length) {
            if(nums[j] === firstNumber) {
                triplet.push(nums[j]);
            }
            j++;
        }

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

        if(hasTriplet.length === 2) {
            count++;
            hasTriplet = [];
        }
    }

    return count;

};

https://leetcode.com/problems/number-of-arithmetic-triplets

Архитектура приложений

Пара соображений о топике.

Выбор архитектурной стратегии зависит от предполагаемой неопределенности в проекте.

🐝Наивысшая неопределенность - в стартапе с одним приложением. Неизвестны ни представления (мобильная платформа или только веб?), ни источники данных (сегодня он один, завтра - новый), ни уровень безопасности и отказоустойчивости, ни степень интерактивности приложения. Известно немногое: ресурсов у компании мало, предметная область - одна, развитие итеративное, быстрое.

В этом случае я исходил бы из максимальной гибкости архитектуры. Модульность, микросервисность, маленькое ядро. Популярные технологии с потенциалом быстрейшего вывода в прод.

🐳 Наименьшая неопределенность - в проекте Газпрома по мониторнигу температуры труб. Известно ТЗ, типы данных, представление, высочайшие требования к безопасности и отказоустойчивости, сроки поставлены заранее. Расширение предполагается только в новых источниках данных и способах вывода.

Если ресурсы или сроки ограничены, я предпочел бы монолит. Иначе - микросервисный подход, как наиболее современный и отказоустойчивый. Технологии выбирал бы по испытанности, но не избегал бы редких.

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

#проектирование

DRY vs WET vs AHA, или "duplicate-code-driven" подход!

В работе часто думал: когда самое удачное время абстрагировать логику?

Чтобы ответить адекватно, вспомним главный принцип программиста-прагматика:

"Мы знаем только то, что проект будет изменяться".

Если городить абстракции заранее - приходим к преждевременной оптимизации и затратам времени на то, что, скорее всего, изменится. Известный архитектурный принцип говорит: на стадии MVP (minimum valuable product) создавайте монолит, и только после бизнес-тестирования переходите к любым видам архитектуры, требующим вложений времени.

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

Как я вижу подход к разработке, выгодный и бизнесу, и разработчикам:

1. Делаем фичу;
2. Если это очевидно переиспользуемый код (например, он принимает строку и разворачивает ее), то сразу абстрагируем в утилиту;
3. Иначе, если нужно, дублируем код, изменяя под конкретные кейсы. Не дважды, как говорит WET (write everything twice), а сколько понадобится - пока не убедимся, что поняли, как абстракция должна работать.
4. Проводим рефакторинг, абстрагируя код и заменяя дубликаты.

Этот подход отвечает принципу AHA, или Avoid Hasty Abstractions.

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

#проектирование

Тайна анимаций: срыв покровов с браузерных оптимизаций.

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

За примером далеко ходить не надо. В поиске умных часов я нагуглил известный российский магазин Apple. Спустя пять секунд созерцания лоадера я буквально испытал боль - и перешел в соседний магазин ссылкой ниже. Узнай это основатель, раздал бы IT-отделу по шапке.

Анимации могут испортить UX уже после загрузки. Способов повредить у них два:

⤵️ Анимировать "тяжелые" свойства элементов, особенно на сложных SPA;

⤵️ Неразумно исполнять асинхронный код.

Раскрою по-очереди.

➡️ Браузер отображает приложение за несколько последовательных шагов:

🔹Создание DOM
🔹Создание CSSOM
🔹Создание Render Tree на их основе
🔹Layout
🔹Painting
🔹Compositing

Нас интересуют последние три стадии.

⛔️ На стадии Layout браузер пересчитывает весь макет. Да, весь! Даже если напрямую изменять размер одной кнопки. Затем выполняет следующие стадии. Анимировать размеры блоков - плохая идея.
⚠️ На стадии Painting браузер рисует физические пиксели, включая цвета. Эти операции менее затратны, но нежелательны, так как Compositing все еще выполняется в довесок.
✅ На стадии Compositing браузер делит приложение на слои композиции (stacking context). Ориентируется он на CSS-правила элементов, такие как transform, opacity и will-change. Таким образом, анимация происходит на отдельном слое, не затрагивающем остальной макет. Движок пропускает предыдущие этапы и сразу выполняет анимацию. Гениально и просто.

➡️ Допустить ошибку в асинхронной работе можно, привязав к requestAnimationFrame (или другому интервальному API) тяжелый код. Браузер просто не уложится в отведенное время, выделенное на один кадр анимации, и пользователь увидит фризы.

Имея это в виду, мы избегнем грубых ошибок в UX.

А следующая статья будет про утечки памяти на фронтенде. Stay tuned! ✌️

Утечки памяти: ликбез.

Мы на frontend редко работаем с памятью. В отличие от братьев с бэка, которые перекладывают байты в C++, мы просто отписываемся от событий в коллбэке, который возвращает useEffect. Этот коллбэк - один из инструментов профилактики утечек памяти.

🔹 Что такое утечка памяти?
Это сущность, которая застряла в памяти без всякой пользы. Сущность может быть объектом, массивом, нодой DOM-дерева, даже экземпляром лексического окружения, созданного замыканием.

🔹Как возникают утечки памяти?
Сценарий прост: создали на что-то ссылку, попользовались, забыли ссылку удалить. А потом снова. И снова. И снова. Как мы помним, SPA не перезагружаются, чтобы очистить память между переходами. Память копит утечки, приложение работает все медленнее.
В мире React классический источник утечек - асинхронный код. Подписки на события, код работы с API. Когда страница или компонент демонтируется, браузер продолжит старательно выполнять ненужную работу.

🔹Как избежать утечек памяти?
Представьте, что браузерное API - это окна для пушек на борту корабля. Каждый обработчик событий и другие асинхронные вызовы - заряженная пушка. Заряжайте батарею браузерного API внимательно. Велите команде после боя очищать стволы и укатывать пушки. Отписывайтесь от событий, очищайте requestAnimationFrame, удаляйте лишние замыкания.

🔹Как искать утечки памяти?
Пользуйтесь профилировщиком памяти в Хроме. Пошагово:
1. Загрузите приложение.
2. В профилировщике сделайте снимок кучи (именно там застревают лишние объекты).
3. Поделайте активности.
4. Сделайте еще один снимок кучи.
5. Фильтруйте по объектам, распределенным между снимками; отсортируйте по размеру занимаемой памяти.

С некоторой вероятностью вы увидите, где утечки.
Есть еще множество инструментов диагностики утечек. Ищите.

🔹Как быстро и наглядно создать утечку памяти?

const html = document.querySelector('html');

const foo = () => {
    return () => {
        return html;
    }
}

const leak = foo();

Ищите одно из замыканий (анонимных функций) в списке Function на втором снепшоте памяти.

Leetcode #13: Roman to number.

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

Без проблем! Стартую новый алгоритмический марафон. Условия:

- Уровень easy. Почему не сложнее? Во-первых, сложные задачи на Leetcode складываются из простых. Во-вторых, мой карьерный трек предполагает рост в проектирование и управление. В третьих, easy - это не просто, это база.
- Каждый день решать и публиковать по 2-3 задачи, пока моя компания не найдет меня.

Начнем с классики: https://leetcode.com/problems/roman-to-integer/

Вот решение через обратный цикл:

const romanToInt = (s) => {
    const romanNumerals = {
        "I": 1,
        "V": 5,
        "X": 10,
        "L": 50,
        "C": 100,
        "D": 500,
        "M": 1000
    };

    const array = s.split('');
    let acc = 0;

    for(let i = array.length-1; i >= 0; i--) {
      
        const currentNum = romanNumerals[array[i]];
        const previousNum = romanNumerals[array[i-1]];

        if(previousNum < currentNum) {
            acc += (currentNum - previousNum);
            i--;
            continue;
        }
        acc += currentNum;
    }

    return acc;
};

А вот - прямая итерация через reduce с забавной техникой сложения. Зачем она? Чтобы порадовать себя однострочником и нестандартной арифметикой:

const romanToInt = (s) => {
    const romanNumerals = {
        "I": 1,
        "V": 5,
        "X": 10,
        "L": 50,
        "C": 100,
        "D": 500,
        "M": 1000
    };

    return s.split('').reduce((acc, curr, i, arr) => {
        const currentNum = romanNumerals[curr];
        const nextNum = romanNumerals[arr[i+1]]

        return acc + (currentNum < nextNum ? -currentNum : currentNum)
    }, 0);
};

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;
};