Алгоритм Кнута-Морриса-Пратта: префикс-функция

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

В чем задача префикс-функции? Она подсчитывает префиксы строки. Точнее, части строки, которые являются её же суффиксами.

Например, в строке "abab" префиксо-суффиксы - это "ab".

Функция всегда принимает строку и возвращает массив (вектор, итератор...) чисел - тех самых префиксов. Этот массив используется в КМП для подсчета отступа, если найденное частичное вхождение строки прерывается.

И префикс-функцию, и использующий ее алгоритм КМП можно сделать через два указателя.

const prefix = (str) => {
    if(typeof str !== 'string') {
        throw new Error('В префикс-функцию переданы данные не строкового типа')
    }

    const prefixTable = Array(str.length).fill(0);
    let i = 1,
        j = 0;

    while(i < str.length) {
        while(j > 0 && str[i] !== str[j]) {
            j = prefixTable[j-1];
        }
        if(str[i] === str[j]) {
            j++;
        }
        prefixTable[i] = j;
        i++;
    }

    return prefixTable;
}

Алгоритм Кнута-Морриса-Пратта: тело алгоритма

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

Но вернемся к алгоритму.

Как видите, во многом он похож на префикс-функцию. Тот же while для отката индекса j на каждом цикле, та же проверка на совпадение. Только индекс i указывает на символы текста, а j - на подстроку.

Всё гениальное - просто.

const KMP = (text, substr) => {
const pi = prefix(substr);

if(!pi) {
return null;
}

let j = 0;
let i = 0;

while(i < text.length) {
while(text[i] !== substr[j] && j > 0) {
j = pi[j - 1];
}

if(text[i] === substr[j]) {
j++;
}

if(j === substr.length) {
return i - j + 1;
}
i++;
}

return -1;
}

Про рекурсию

Много воды утекло с тех пор, как я переключился с деревьев на алгоритмы поиска подстрок. Многое забыл. Со вчерашнего вечера разбираю AVL-деревья: как увеличивать параметр высоты нод при добавлении новых и выполнять балансировку.

Вспомнил, что для вставки, удаления и поиска в сбалансированных деревьях идеально подходит рекурсия. Почему? Две причины: сложность основных операций - O(logN), а сущность операций - обход одинаковых нод. Балансировка и обработка высот выполняется уже после добавления ноды. В цикле это сложно сделать, а вот рекурсия каким-то образом "восходит" назад к корню.

И вот ночью мне снится сон про рекурсию. В котором увидел, что...

Рекурсивная функция может обрабатывать данные в обратном порядке!

Нужно только вызывать блок обработки данных после рекурсивного вызова.

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

Вот пример рекурсивного обхода массива с конца:

const rec = [0, 4, 8, 11, 14, 15, 17, 18, 20, 22]

const foo = (arr, index) => {
if(index === arr.length) {
return;
}
foo(arr, index+1);
console.log(arr[index])
}

foo(rec, 0)

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

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.