Статья-решение второй задачи из списка для подготовки к IT собеседованиям Grind 75.

На вход подается строка s состоящая из символов '(', ')', '{', '}', '[' или ']'

Необходимо проверить, является ли строка валидной.

Строка является валидной, если соответствует следующим пунктам:

1) Открытые скобки должны быть закрыты скобками того же типа.
2) Открытые скобки должны быть закрыты в правильном порядке.
3) Каждая закрытая скобка имеет соответствующую открытую скобку того же типа.

Примеры:

Пример 1:
Input: s = "()"
Output: true

Пример 2:
Input: s = "()[]{}"
Output: true

Пример 3:
Input: s = "(]"
Output: false

Для решение данной задачи мы будем использовать структуру данных Stack, про нее можете прочитать тут.

Алгоритм для решения задачи будет следующим:

Сначала мы проверим, что длина строки больше одного символа. Затем мы объявим стек в виде массива и хеш-таблицу в виде закрытых скобок как ключей и открытых скобок как значений. Смысл в том, что мы будем проверять каждый символ строки. Если он будет равняться открытой скобке, то мы будем добавлять его в наш стек. Если нет, то мы будем проверять, является ли последний элемент нашего стека противоположным элементом закрытой скобке по типу. Если да, то мы удалим последний элемент с помощью правила "Последним пришел - Первым вышел". Все это позволит нам проверить, правильно ли сбалансирована строка. Если в конце стек будет пустым, значит все элементы были в правильном порядке.

Теперь приступим к реализации нашего алгоритма:

1) Создадим функцию isValid с одним параметром s, которая будет проверять переданную строку.

const isValid = (s) => {
 // code
}

2) После объявления функции в условии if проверим длину строки s. Если длина меньше или равна 1, то возвращаем false, так как строка с одной или менее символов не может быть сбалансированной, потому что у каждой открывающей скобки должна быть закрывающая.

if (s.length <= 1) return false

3) Объявим массив, который будет играть роль стека.

const stack = []

4) Объявим хэш-таблицу с ключами в виде закрытых скобок и значениями в виде открытых.

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

5) Запустим цикл for of, в котором переберем все символы char в переданной строке s.

for (let char of s) {
 // code
}

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

for (let char of s) {
  if (!braces[char]) {
    stack.push(char) 
  } else {
    // code
  }
}

7) Если char не является открывающей скобкой, то выполняется код в блоке else.

8) В блоке else проверим, соответствует ли последний элемент стека открывающей скобке для текущей закрывающей скобки char. Если да, то последний элемент удаляется из стека с помощью метода pop().

for (let char of s) {
  if (!braces[char]) {
    stack.push(char) 
  } else {
    if (stack[stack.length - 1] === braces[char]) {
      stack.pop()
    } else {
      // code
    }
  }
}

9) Если последний элемент стека не соответствует открывающей скобке для текущей закрывающей скобки, то возвращается false, так как скобки не сбалансированы.

for (let char of s) {
  if (!braces[char]) {
    stack.push(char) 
  } else {
    if (stack[stack.length - 1] === braces[char]) {
      stack.pop()
    } else {
      return false
    }
  }
}

10) По окончании цикла проверяем длину стека. Если она равна 0, то все скобки сбалансированы и возвращаем true. Если же длина стека не равна 0, то скобки не сбалансированы и возвращаем false.

Полный код функции:

const isValid = (s) => {
  if (s.length <= 1) return false
   
  const stack = []
  const braces = {
    ')': '(',
    ']': '[',
    '}': '{'
  }
   
  for (let char of s) {
    if (!braces[char]) {
      stack.push(char) 
    } else {
      if (stack[stack.length - 1] === braces[char]) {
        stack.pop()
      } else {
        return false
      }
    }
  }
  
  return stack.length === 0
}

Запустим код в тренажере и убедимся что мы прошли через все тесты.

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

Подписывайтесь на мой канал, в нем будут новые разборы и интересные статьи:)

Простая структура данных, которая представляет собой упорядоченную коллекцию элементов, в которую добавляют элементы и затем убирают их в обратном порядке с одного конца, который обычно называется вершиной стека, т.е первый добавленный элемент удаляют последним, а последний добавленный - первым, правило звучит так "Последним пришел - Первым вышел" или LIFO от англ. "last in, first out".

1. Push: добавление элемента на вершину стека.
2. Peek: получение значения верхнего элемента без его удаления.
3. Pop: удаление элемента с вершины стека.
4. isEmpty: проверка, пуст ли стек. Возвращает true, если стек пуст и false в противоположном случае.

Операция добавления и удаления элементов в стеке и очереди занимает О(1), в то время как операции поиска и получение произвольного элемента имеют сложность O(n). Структура Stack может быть реализована с использованием различных абстрактных типов данных, например, массивов или связанных списков. Важно выбрать оптимальную реализацию в зависимости от задачи, так как эффективность работы со стеками может сильно различаться в зависимости от используемых методов.

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

Структура Stack находит широкое применение в программировании:

- Управление вызовами функций в компьютерных программах (хранение локальных переменных и адреса возврата).

- Отмена и возврат действий в графических приложениях.

- Реализация алгоритмов обхода графов.

- Хранение временных данных в алгоритмах поиска и сортировки.

- Другие.

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

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

Спасибо за прочтение статьи, подписывайтесь на канал, в нем будут выходить новые интересные статьи и разборы задач с использованием структуры Stack.

Grind 75 - это набор из 75 задач по алгоритмам и структурам данных, которые рекомендуется решать для подготовки к техническим интервью в IT-компаниях. Эти задачи были собраны сообществом разработчиков и являются одним из наиболее популярных наборов задач для подготовки к техническим интервью.

Каждая статья будет посвящена решению одной задачи, которую мы будем разбирать на конкретных примерах и давать подробные объяснения каждого шага. Мы также будем обсуждать эффективность каждого алгоритма и его сложность.

В этой статье мы начнем с первой задачи TwoSum. Для начала попробуйте ее решить самостоятельно.

На вход подается 2 параметра:

1) nums - массив целых чисел

2) target - искомое целое число

Необходимо вернуть новый массив из 2-ух индексов массива nums, сумма чисел которых будет равняться искомому числу target.

Примеры:

Пример 1:
Параметры: nums = [2,7,11,15], target = 9
Результат: [0,1]
Пояснение: Потому что nums[0] + nums[1] == 9, мы возвращаем индексы [0, 1].

Пример 2:
Параметры: nums = [3,2,4], target = 6
Результат: [1,2]

Пример 3:
Параметры: nums = [3,3], target = 6
Результат: [0,1]

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

Объявим функцию twoSum и запишем два цикла внутри нее:

Прошу заметить, что j равняется i + 1, это было сделано для того, чтобы мы не брали в расчет элементы, которые остались слева от элемента i, потому что тогда мы будем проверять уже рассмотренные комбинации чисел, что не имеет смысла и может привести к повторным результатам.

Теперь осталось проверить, что сумма чисел i и j будет равняться числу target, если это так, то мы вернем индексы этих элементов [i, j]:

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

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

Алгоритм заключается в следующем:

1. Создаем пустой объект hash.

2. Проходим по всем элементам массива nums с помощью цикла for.

3. Для каждого элемента nums[i] вычисляем число, которое нам нужно для сложения с элементом nums[i], чтобы получить target, sub = target - nums[i].

Например: искомое число 10, элемент равен 7, следовательно sub = 3. В следующем шаге мы произведем проверку наличия sub в hash.

4. Проверяем, есть ли значение sub в объекте hash. Если есть, значит мы нашли два числа, которые в сумме дают target, и возвращаем массив с индексами этих чисел [i, hash[sub]].

5. Если значение sub не найдено в объекте hash, то добавляем текущий элемент nums[i] и его индекс i в объект hash.

Теперь осталось написать алгоритм:

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

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

Поздравляю, вы решили первую задачу из Grind 75.

Подписывайтесь на канал, чтобы не пропустить разбор следующих задач. Будем двигаться вместе на пути к улучшению своих навыков:)

TypeScript предоставляет глобальные utility types, которые можно использовать для общий преобразований. В этой статье мы рассмотрим большинство утилит с примерами.

Awaited<Type> - Позволяет получить тип значения, возвращаемого асинхронной функцией. Он извлекает тип, который оборачивается в Promise, и позволяет описать тип значения, которое будет возвращено при разрешении этого Promise.

Здесь тип Awaited используется для получения типа значения, которое будет возвращено при выполнении асинхронной функции fetchUserData.

Partial<Type> - Создает тип со всеми свойствами Type, которые становятся необязательными.

В первом примере с объектом user1, компилятор выдаст ошибку из-за того, что мы не заполнили все свойства, которые указали в типе User.

При использовании Partial<User> все свойства типа User стали необязательными.

Required<Type> - Устанавливает все свойства Type обязательными и работает противоположно утилите Partial.

Несмотря на то, что в типе User мы указали все свойства необязательными, мы использовали утилиту Required, которая преобразовала весь тип в обязательный, поэтому компилятор выдаст ошибку если мы не укажем все свойства в объекте.

Readonly<Type> - Добавляет флаг readonly ко всем свойствам Type.

Компилятор выдаст ошибку, потому что после преобразования утилитой Readonly все свойства типа Todo стали неизменяемыми.

Record<Keys, Type> - Создает объект, ключи которого являются Keys, а значения свойств Type.

В результате объект dogs будет содержать в себе ключи DogName и значения каждого ключа будут age и weight.

Pick<Type, Keys> - Создает новый тип, содержащий только указанные свойства Keys из исходного типа Type.

Например мы хотим создать объект только с именем и фамилией. Для этого мы будем использовать Pick, создадим новый тип FullName с этими свойствами.

Таким образом, Pick позволяет создавать новые типы, выбирая только необходимые свойства из исходного типа. Это может быть полезно, например, когда мы хотим передать только определенные свойства объекта в функцию или метод.

Omit<Type, Keys> - Создает новый тип из полей Type без ключей Keys.

В результате преобразований мы получили новый тип Titles, который содержит только title и sub_title.

Exclude<UnionType, ExcludedMembers> - Это тип, который исключает из объединения UnionType все типы, которые содержатся в ExcludedMembers.

Например, если у нас есть объединение типов MyUnion и мы хотим исключить из него типы "null" и "boolean", то мы можем использовать Exclude следующим образом:

В результате получим новое объединение типов MyNewUnion, которое будет содержать только типы string и number.

Extract<Type, Union> - Позволяет извлекать из объединения типов Union только те типы, которые являются подтипами Type.

В этом примере мы объявляем тип MyUnion, который представляет собой объединение типов string, number и boolean. Затем мы используем утилиту типов Extract, чтобы создать новый тип MyStringOrNumber, который содержит только типы string и number из объединения MyUnion.

NonNullable<Type> - Позволяет создавать новый тип, который исключает значения null и undefined из типа Type.

Мы объявляем тип MyType, который представляет собой объединение типов string, null и undefined. Затем мы используем утилиту типов NonNullable, чтобы создать новый тип MyNonNullType, который содержит только тип string без значений null и undefined.

Parameters<Type> - Позволяет извлекать типы параметров функции в виде кортежа.

Мы объявляем функцию myFunction, которая принимает три параметра разных типов. Затем мы используем утилиту типов Parameters, чтобы создать новый тип MyFunctionParams, который содержит типы параметров функции в виде кортежа.

ConstructorParameters<Type> - Позволяет извлекать типы параметров конструктора класса в виде кортежа.

Мы объявляем класс MyClass, который имеет конструктор, принимающий три параметра разных типов. Затем мы используем утилиту типов ConstructorParameters, чтобы создать новый тип MyClassParams, который содержит типы параметров конструктора в виде кортежа.

ReturnType<Type> - Позволяет извлекать тип возвращаемого значения функции.

Мы объявляем функцию myFunction, которая возвращает строку. Затем мы используем утилиту типов ReturnType, чтобы создать новый тип MyFunctionReturnType, который содержит тип возвращаемого значения функции.

InstanceType<Type> - Позволяет извлекать тип экземпляра класса.

Мы объявляем класс MyClass, который имеет свойство name и конструктор, который принимает строку и присваивает ее свойству name. Затем мы используем утилиту типов InstanceType, чтобы создать новый тип MyInstanceType, который содержит тип экземпляра класса.

ThisParameterType<Type> - Позволяет извлекать тип this из функции Type.

Мы объявили две функции:

Первая функция - toHex, мы обозначили, что ее параметр this имеет тип Number.

Вторая функция - numberToString, в параметрах с помощью ThisParameterType мы указали, что параметр n равняется this параметра функции toHex.

OmitThisParameter<Type> - Определяет функцию без типа this.

Добавляет тип this к функции Type.

В данной статье мы рассмотрели почти все utility types, конечно, в реальной работе большинство из этого скорее всего вам не пригодится, но для справки и личного роста ознакомиться с существующими утилитами и возможностями TS будет круто. Знания данных утилит помогут вам все больше познавать TS и создавать умные типы для любой ситуации.

Заглядывайте в мой телеграм канал - @days_on_front, там будут другие интересные статьи по TS, фронту и разработке в целом.

Буду рад обратной связи. Спасибо за внимание!

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

Для запуска проектов мы используем большое количество сервисов:

• pm2 или ts-node для запуска наших проектов на JS/TS
• Базы данных PostgreSQL, MySQL, MongoDB и т.д
• Веб-сервер nginx/apache
• Мониторинговые системы
• Redis или Memcache для кэширования данных
• и другие полезные вещи

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

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

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

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

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

Инструкция по установке докера:

• Mac
• Windows
• Ubuntu

Шаги по развертыванию докера:

1. Описать настройки контейнера - операционную систему, программы, команды для запуска.
2. Собрать билд (build) контейнера из раннее описанных настроек.
3. Запустить контейнер из созданного билда.

Перейдем в папку и инициализируем проект.

npm init -y

Будем использовать веб-сервер. Добавим express в проект.

npm install express

Создадим файл index.js и напишем простой код для веб-сервера.

Напишем настройки для докер контейнера, для этого создадим файл в корне проекта Dockerfile.

Любой конечный Dockerfile называется образом. Для нашего контейнера нужна операционная система, в этом нам поможет команда FROM. Команда собирает контейнер из указанного образа операционной системы. Докер поддерживает большинство доступных ОС, самые популярные из них это - Ubuntu, Debian. Синтаксис выглядит так:

FROM <BASE>:<VERSION>, где BASE - название образа, а VERSION - версия.

Добавим в наш файл следующую команду, скажем докеру, что мы хотим использовать образ ubuntu:18.04 в нашем контейнере.

Уже сейчас мы можем собрать билд контейнера. Перейдем в папку и введем команду docker build -t server-app .

Флаг -t позволяет нам указать имя нашего контейнера, а . говорит докеру где нужно искать Dockerfile. Докер найдет необходимый образ, скачает его и соберет наш билд. В консоли вы увидите что-то наподобие этого.

Мы добавили образ системы, но для запуска сервера на express нам необходимо установить nodejs и npm в нашу систему, для этого мы воспользуемся командой RUN

Добавим следующую строку в нашел образ.

Синтаксис выглядит так - RUN <command>, где command означает любую валидную операцию в командой строке.

Соберем образ еще раз.

Наш контейнер ничего не знает о сервере написанном в файле index.js, чтобы мы смогли запустить сервер, нам нужно скопировать файлы в наш контейнер. Для этого воспользуемся командой WORKDIR, чтобы указать рабочий каталог на который будут указывать все остальные команды по типу RUN, CMD, ENTRYPOINT, COPY и ADD.

Синтаксис команды выглядит так: WORKDIR <PATH>, где PATH - это путь до каталога.

Теперь воспользуемся командой COPY и скопируем файлы проекта в контейнер. Синтаксис: COPY <HOME_PATH>:<WORK_PATH>, где HOME_PATH - это путь до файла/папки, а WORK_PATH - это путь до места, куда мы хотим скопировать файлы.

Добавим в наш образ следующие строки:

Во-первых мы указали что путь /var/www является нашим корневым каталогом в контейнере.

Во-вторых указали, что хотим скопировать файл index.js в файл с названием index.js, т.к мы уже указали рабочий каталог, то он будет скопирован в папку /var/www

Попробуем запустить контейнер и посмотреть что мы успешно скопировали файл. Для этого воспользуемся командой CMD. Она будет выполняться после запуска контейнера и может быть только одна для всего докерфайла.

Синтаксис следующий: CMD [<COMMAND>, <PARAM_1>, <PARAM_N>], где COMMAND - название команды, PARAM_N - передаваемые параметры.

Добавим команду:

Соберем контейнер docker build -t server-app . и запустим контейнер docker run server-app

В результате вы должны увидеть название нашего файла:

Файл с сервером успешно скопирован в контейнер, осталось его запустить, но перед этим нам нужно установить зависимости из package.json, для этого немного изменим путь, скопировав всю папку с проектом целиком, а не только один index.js, потом добавим команду RUN для установки зависимостей и запустим сервер с помощью CMD:

Соберем образ и запустим:

Поздравляю, наш сервер запущен в контейнере!

Для запуска в фоновом режиме воспользуемся флагом -d. Запустим наш контейнер.

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

Для остановки контейнера напишите docker stop -t 0 <CONTAINER_ID>, где флаг -t 0 - говорит докеру немедленно остановить контейнер, аCONTAINER_ID - первые несколько символов названия контейнера.

Теперь попробуем зайти на localhost:3003 и получаем ошибку, почему? Потому что все что запускается внутри контейнера - остается внутри контейнера и наша хост машина ничего не знает о нем.

Для того чтобы что смогли получить доступ - нам нужно пробросить порт снаружи в контейнер. Команда EXPOSE добавляет информацию о порте для пользователя Dockerfile и несет только информационный характер. Для настоящего проброса при запуске контейнера нужно напрямую передать ему порт хоста и порт контейнера.

Синтаксис: -p <HOST_PORT>:<CONTAINER_PORT>

Добавим EXPOSE <PORT> в Dockerfile

Соберем контейнер и запустим с помощью команды docker run -d -p 4000:3003 server-app

Попробуйте перейти по адресу localhost:4000, поздравляю, сервер нам ответил.

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

Давайте создадим папку shared на уровень ниже относительно Dockerfile, чтобы при билде докер не подхватил его тоже, и внутрь папки поместим файл text.json.

Изменим наш index.js добавив отправку файла из папки shared.

Теперь соберем контейнер docker build -t server-app . и запустим его добавив новый флаг -v <HOST_ABSOLUTE_PATH>:<CONTAINER_ABSOLUTE_PATH>, где указываем абсолютный путь до папки и конечный путь внутри контейнера, команда запуска будет такой:

docker run -d -p 4000:3003 -v /Users/username/shared:/var/www/shared server-app

Попробуем перейти по localhost:4000 и видим что сервер прислал содержимое файла text.json, который мы пробросили в контейнер. Попробуйте изменить text.json и обновите страницу, вы увидите что контент так же изменился без сборки и перезапуска контейнера.

Проброс файловой системы применяют тогда, когда данные контейнера надо сохранить. Для этого выясняют, где в контейнере приложение хранит свои данные, и пробрасывают туда локальную папку из проекта. Содержимое пробрасываемых папок обязательно добавляют в .gitignore, оставляя в них только файл .gitkeep, чтобы не возникло приключений с отсутствующими папками (попробуйте прокинуть в контейнер папку, которой не существует на хосте, будет ошибка).

В данной статье мы изучили базовые команды, научились собирать, запускать и останавливать контейнер, поняли как пробрасывать порты и файлы. Данная статья погрузила в мир докера, но постоянно делать одни и те же действия в виде сборки и запуска из командой строки не очень удобно. Скоро мы расскажем про Docker Compose, который значительно облегчит вашу жизнь, а пока подписывайтесь на наш телеграмм канал.

Спасибо за внимание. Буду рад обратной связи:)