Algorithmics: хакаем алгоритмические собесы

Description
Канал для людей, жаждущих совершенствования в мире программирования.

Здесь вы найдете глубокие знания об алгоритмах, структурах данных и подготовке к собеседованиям в IT.

Авторы: @tifongod и @avivasyuta

Наш блог: https://algorithmics-blog.github.io/
Advertising
We recommend to visit

Рассказываю про крипту и инвестиции на понятном языке.

Сотрудничество — @TGowner999

Больше информации о нашей сети: https://t.me/TGownerTOP

Last updated 1 month, 2 weeks ago

Утро начинается не с кофе.

Сотрудничество: @evoanna (по всем вопросам, только мне писать)

Канал в реестре: https://clck.ru/3FCQfU

Last updated 5 days, 22 hours ago

Самые любимые рецепты для Вас!

Контакт: @khaitbayev

Доверенные менеджеры тут:
https://t.me/+reWsclRikXIxOTcy

Ссылка для приглашения: https://t.me/+wsrt9bX3G1U3Zjg6

Last updated 4 weeks ago

2 months, 1 week ago

Префиксное дерево (Trie)

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

Вот пример структуры узла Trie.

```

type TrieNode = {
children: { [key: string]: TrieNode };
isEndOfWord: boolean;
}

```

```

type TrieNode struct {
Children map[rune]*TrieNode
IsEndOfWord bool
}

```

Каждый узел имеет мапу children, где ключом является символ, а значением — следующий узел, представляющий символ в этом слове. Узел isEndOfWord помечает конец слова.

Простыми словами, если мы хотим добавить слова «cat» в дерево, нам нужно разбить его посимвольно и каждый символ будет представлять собой отдельную ноду. Иерархия нод будет выстроена в соответствии с порядком слов, то есть в нашем примере: «c» -> «a» -> «t».

Вот так можно визуализировать префиксное дерево, в котором содержаться слова cat, car, cart, care, dog, dot, и dove:

```

(root) / \ c d / | a o / \ / | \

t r g t v
/ \ |
e t e*

```

### Пример работы с Trie

Допустим, мы хотим сохранить слова «cat» и «car». Префиксное дерево будет выглядеть следующим образом:

  1. Корневой узел содержит ссылки на узлы c, которые ведут к поддереву для символа a.
  2. Узел a ветвится на узлы t и r, представляющие слова «cat» и «car».
  3. В узлах t и r флаг isEndOfWord установлен в true, указывая, что здесь заканчиваются слова.

### Основные операции в Trie

  1. Добавление слова — добавление слова в Trie выполняется за O(N), где N — длина слова. Мы последовательно проходим каждый символ слова и либо создаем новый узел, если он не существует, либо переходим к существующему.

  2. Поиск слова — поиск также выполняется за O(N). Для поиска слова достаточно пройти по каждому символу слова. Если на каком-то этапе путь отсутствует, значит, слово не найдено.

  3. Поиск по префиксу — уникальная особенность Trie. Чтобы найти все слова, начинающиеся с заданного префикса, можно просто дойти до конца префикса, а затем собрать все слова, начиная с этого узла.

### Преимущества и недостатки Trie

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

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

  3. Недостатком является узкая специализация данной структуры. Данная структура позволяет искать только по точному совпадению префикса. То есть, например, если вам нужно искать слово не по префиксу, а по любой возможной подстроке, или учесть опечатки — классический Trie становится бесполезным. Не смотря на то, что некоторые модификации данной структуры могут решить часть проблем, не факт что данная структура будет оптимальным выбором для решения подобных задач.

#trie

3 months ago
[Максимальная сумма парных элементов связного списка](https://algorithmics-blog.github.io/blog/maximum_twin_sum_of_a_linked_list/)

Максимальная сумма парных элементов связного списка

Продолжаем изучение связанных списков и сегодня у нас новая задача.

Сложность: 🟡 Средняя

ℹ️ Описание

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

Парный элемент для i'го считается элемент с индексом n - i - 1, где 0 <= i <= n / 2 - 1. То есть, для первого элемента списка парным будет считаться последний элемент списка, для второго - предпоследний и так далее.

⚠️ Ограничения

— Список всегда имеет четное количество элементов
— Количество элементов лежит в диапазоне от 2 до 100 000
— Значение элемента лежит в диапазоне от 1 до 100 000

1️⃣ Пример

Элементы списка: [5,4,2,1]

Ответ: 6

Пояснение: В списке есть 2 пары элементов: [5, 1] и [4, 2]. Сумма обоих пар равна 6.

2️⃣ Пример

Входные данные: [4,2,2,3]

Ответ: 7

Пояснение: В списке есть 2 пары элементов: [4, 3] и [2, 2]. Максимальная сумма равна 7.

3️⃣ Пример

Входные данные: [1,100000]

Ответ: 100001

Реализация

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

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

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

➡️ Решение через преобразование в массив

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

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

currentListElement — будем перемещать по списку последовательно.
oddElementList — будем двигать через два элемента за раз. В связном списке это делается следующим образом:

```

oddElementList = oddElementList.Next.Next

```

Таким образом, когда указатель oddElementList достигнет конца списка, указатель currentListElement будет указывать на начало второй половины нашего списка.

После этого останется только пройтись до конца списка указателем currentListElement, доставая для каждого следующего элемента его пару из стека и находя максимальную сумму.

➡️ Решение через стек

Итак, оптимальное решение

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

Чтобы быстро находить пары, можно создать вспомогательный список, развернутый в обратном порядке. Для изменения порядка списка можно написать простую функцию reverseList (изменение происходит in-place без создания нового списка).

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

Данное решение будет более оптимальным по памяти, так как изменение порядка происходит in-place и не требует дополнительного пространства под массив или стек.

➡️ Оптимальное решение

#medium #linked_list

3 months, 2 weeks ago
***🔸*****Получение элемента из списка**

🔸Получение элемента из списка

Метод предназначен для получения значения узла по указанному индексу.

В первую очередь нужно проверить корректность индекса. Если он меньше 0 или больше или равен размеру списка size, возвращается -1, так как такой индекс недопустим.

Далее необходимо пройти по списку от его головы и найти элемент с нужным индексом. Для этого мы запускаем цикл, который выполняется до тех пор, пока i < index. Инициализируем переменную curr, которая изначально равна head то есть ссылке на первый элемент списка. Далее на каждой итерации цикла в переменную curr записывается ссылка на следующий элемент в списке через curr.next.

Если удалось найти нужный элемент в списке, то возвращаем его значение в качестве ответа, иначе возвращаем -1.

🔸Добавление элемента в список по индексу

В первую очередь нужно проверить корректность индекса. Если он меньше 0 или больше или равен размеру списка size, то выходим из функции и не выполняем вставку.

Следующим шагом увеличиваем внутреннюю переменную size на единицу, так происходит добавление элемента.

Если индекс равен 0, то происходит вставка в начало списка. Это означает, что нам достаточно создать новый элемент, указать в его next ссылку на текущий head списка и заменить текущий head новым элементом, после чего выйти из функции.

Если же индекс не равен 0, то нам нужно добавить элемент перед тем, который находится на позиции равной index. Мы выделили отдельный внутренний метод findPrevNode. Вызвав этот метод мы получаем предшествующий переданному индексу узел prev. Если такой узел существует, то нам достаточно в next нового элемента добавить ссылку из prev.next, а в prev.next положить ссылку на новый элемент. Таким образом новый элемент встраивается в цепочку узлов списка на заданную позицию.

🔸Добавление элемента в начало списка

Так как у нас уже есть универсальный метод для вставки элементов по индексу, мы можем им воспользоваться для вставки в начало. Для этого просто вызовем метод с нулевым индексом this.addAtIndex(0, val)

🔸Добавление элемента в конец списка

Так как у нас уже есть универсальный метод для вставки элементов по индексу, мы можем им воспользоваться для вставки в конец. Для этого просто вызовем метод с индексом равным длине списка this.addAtIndex(this.size, val)

🔸Удаление элемента

В первую очередь нужно проверить корректность индекса. Если индекс меньше 0 или больше или равен размеру списка, метод завершает работу, так как такой индекс некорректен.

Далее необходимо уменьшить значение переменной size на единицу, так как происходит удаление.

Если индекс равен нулю, значит происходит удаление первого элемента. В этом случае достаточно изменить head списка на head.next.

Если же индекс не равен нулю, то нужно сначала найти элемент, который находится перед удаляемым. Затем нужно проставить ссылку с предыдущего на следующий элементprev.next = prev.next.next.

Посмотреть реализацию в блоге
#linked_list #medium

5 months ago

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

Основные операции побитового сдвига

Левый сдвиг (<<)

Каждый бит числа сдвигается влево на заданное количество позиций.

Пример

1010 << 1 = 10100

Эта операция эквивалентна умножению числа на 2 для каждого сдвига.

Правый сдвиг (>>)

Каждый бит числа сдвигается вправо на заданное количество позиций.

Пример

1010 >> 1 = 0101 = 101

Эта операция эквивалентна делению числа на 2 для каждого сдвига.

---------

Примеры использования:

- Быстрое умножение и деление:
- Маскирование битов
- Шифрование и сжатие данных:

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

5 months ago

Наименования битов

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

1. Старший бит (Most Significant Bit, MSB)

Это бит, который имеет наибольший вес в двоичном числе и находится в крайней левой позиции.
Например, в числе 1000 (в двоичной системе) старший бит равен 1.

2. Младший бит (Least Significant Bit, LSB)

Это бит, который имеет наименьший вес в двоичном числе и находится в крайней правой позиции.
Например, в числе 1000 (в двоичной системе) младший бит равен 0.

3. Средние биты (Intermediate Bits)

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

4. Установленный бит

Это бит, значение которого равно 1 в двоичном представлении числа.

5. Значимый бит

Значимые биты — это биты, которые существенно влияют на значение числа. Обычно это все биты, начиная с первого установленного бита до младшего бита.
Например, в числе 0010110 (в двоичной системе) значимые биты — 10110.

6. Последний установленный бит (Last Set Bit)

Это самый правый бит, который имеет значение 1 в двоичном представлении числа. Этот бит также иногда называют младшим установленным битом.

5 months, 1 week ago

Вес Хэмминга

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

Вес Хэмминга (Hamming weight) также известный как популяционное число (population count), представляет собой количество единичных (установленных) битов в двоичном представлении числа.
Формально, для числа ? вес Хэмминга определяется как сумма всех битов числа ? в его двоичной форме.

Примеры

1️⃣ Число 5

- Двоичное представление: 101
- Вес Хэмминга: 2 (два бита установлены в 1)

2️⃣ Число 13

- Двоичное представление: 1101
- Вес Хэмминга: 3 (три бита установлены в 1)

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

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

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

Обработка сигналов. Вес Хэмминга может применяться для анализа и фильтрации сигналов, а также для оценки шума.

7 months, 3 weeks ago

Привет. Сегодня я бы хотел обсудить с вами один интересный вопрос, который не касается алгоритмов, но напрямую относится к работе.

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

В чем суть. Есть условно два стула.

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

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

Расскажите, что вы думаете по этому поводу? Какой вариант для вас более предпочтительный? Или может у вас есть другие идеи?

7 months, 4 weeks ago

Сколько нужно стрел, чтобы лопнуть все воздушные шары

Сложность: ? Средняя

ℹ️ Описание

К плоской стене, представляющей плоскость XY, приклеено несколько сферических воздушных шаров. Шары представлены в виде двумерного целочисленного массива points, где points[i] = [xstart, xend] обозначает шар, горизонтальный диаметр которой простирается между xstart и xend. Вы не знаете точных координат Y воздушных шаров.

Вы можете выстрелить стрелой прямо вертикально (в положительном направлении Y) из разных точек вдоль оси X. Воздушный шар с xstart, xend разрывается стрелой, выпущенной в x, если x start <= x <= xend. Нет ограничений на количество выпущенных стрел.

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

⚠️ Ограничения

— В массиве points может быть от 1 до 105 элементов
— 2^31 <= xstart < xend <= 2^31 - 1

*1️⃣* Пример

Входные данные**

points = [[10,16],[2,8],[1,6],[7,12]]
Ответ: 2

Пояснение

— Выстрелите стрелой в точку x = 6, лопнув шарики [2, 8] и [1, 6].
— Выстрелите стрелой в точку x = 11, лопнув шарики [10, 16] и [7, 12].

2️⃣ Прим**ер

Входные данные**

points = [[1,2],[3,4],[5,6],[7,8]]
Ответ: 4

Пояснение

Для каждого воздушного шара нужно выпустить одну стрелу, всего получится 4 стрелы.

3️⃣ Прим**ер

Входные данные**

points = [[1,2],[2,3],[3,4],[4,5]]
Ответ: 2

Пояснение

— Выстрелите стрелой в точку x = 2, лопнув шарики [1, 2] и [2, 3].
— Выстрелите стрелой в точку x = 4, лопнув шарики [3, 4] и [4, 5].

Решение

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

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

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

Исходя из этого мы можем сформировать крайне простой алгоритм:

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

Посмотреть реализацию в блоге

#arrays#medium

8 months, 2 weeks ago

Сжатие строки

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

Сложность: ? Средняя

ℹ️ Описание

Дана строка в виде массива символов. Необходимо написать функцию, которая сожмет входящий массив и вернет количество символов в сжатом массиве по следующему принципу:
— Если символ повторяется больше одного раза подряд, нужно заменить всю подстроку на строку ['a', 'n'], где a - исходный символ, n - количество повторений этого символа, идущих подряд. В случае если n — многозначное число, каждая цифра должна быть добавлена отдельным символом.
— Если буква не повторяется - оставить ее без изменений.

Все изменения нужно совершить in-place, в качестве ответа функции вернуть количество символов в сжатой строке.

⚠️ Ограничения

— Длина входящего массива от 1 до 2000 символов
— Элементы массива - символы латиницы, цифры или знаки

*1️⃣* Пример

Входные данные**

```

chars = ["a","a","b","b","c","c","c"]

```

Ответ

```

6

```

Исходный массив должен быть преобразован в

```

chars = ["a","2","b","2","c","3"]

```

2️⃣ Прим**ер

Входные данные**

```

chars = ["a"]

```

Ответ

```

1

```

3️⃣ Пример
Входные данные

```

chars = ["a","b","b","b","b","b","b","b","b","b","b","b","b"]

```

Ответ

```

4

```

Исходный массив должен быть преобразован в

```

chars = ["a","b","1","2"]

```

Решение

Задача решается достаточно элементарно, главная загвоздка - замена элементов in-place.

Для решение задачи нам понадобятся несколько индексов:
— Индекс текущего элемента lastElemIdx
— Индекс начала последовательности одинаковых элементов firstElemIdx
— Индекс элемента, который будет заменен при сжатии строки newPositionIdx. Для эффективности решения мы будем заменять элементы исходного массива, а после «отрежем» хвост. В противном случае нам бы пришлось вырезать повторяющиеся символы, смещая хвост массива на n элементов влево, что значительно замедлит алгоритм.

Далее нам достаточно аккуратно обойти и модифицировать исходный массив.

Посмотреть реализацию в блоге

#arrays#medium

10 months, 1 week ago

`` console.log(
__
_ / /|
|\ \/_/
\_\| / __
\/_/__\ .-=='/~\
____,__/__,_____,______)/ /{~}}}
-,------,----,-----,---,\'-' {{~}}
jgs '-==.}/
`)

```

Сегодня не будет задач!

Cегодня мы поздравляем всех наших подписчиц с прекрасным женским днем.
Будьте красивыми, счастливыми и прокаченными в алгоритмах!

С праздником! ?

We recommend to visit

Рассказываю про крипту и инвестиции на понятном языке.

Сотрудничество — @TGowner999

Больше информации о нашей сети: https://t.me/TGownerTOP

Last updated 1 month, 2 weeks ago

Утро начинается не с кофе.

Сотрудничество: @evoanna (по всем вопросам, только мне писать)

Канал в реестре: https://clck.ru/3FCQfU

Last updated 5 days, 22 hours ago

Самые любимые рецепты для Вас!

Контакт: @khaitbayev

Доверенные менеджеры тут:
https://t.me/+reWsclRikXIxOTcy

Ссылка для приглашения: https://t.me/+wsrt9bX3G1U3Zjg6

Last updated 4 weeks ago