Судоку

Алгоритм:
1. Создайте функцию, которая проверяет, действительна ли данная матрица судоку или нет. Сохраните Hashmap для строки, столбца и полей. Если какое-либо число имеет частоту больше 1 в hashMap, верните false, иначе верните true;
2. Создайте рекурсивную функцию, которая принимает сетку и текущий индекс строки и столбца.
3. Проверьте базовые случаи:
⁃ Если индекс находится в конце матрицы, т.е. i=N-1 и j=N, тогда проверьте, безопасна ли сетка или нет, если безопасно, распечатайте сетку и верните true, иначе верните false.
⁃ Другой базовый случай — когда значение столбца равно N, т. е. j = N, затем происходит переход к следующей строке, т. е. i++ и j = 0.
4. Если текущий индекс не присвоен, то заполняем элемент от 1 до 9 и повторяем для всех 9 случаев индекс следующего элемента, т.е. i, j+1. если рекурсивный вызов возвращает true, разорвите цикл и верните true.
5. Если присвоен текущий индекс, вызовите рекурсивную функцию с индексом следующего элемента, т. е. i, j+1.

Сложность: O(9^(n*n)

Проверка строки-палиндрома

Строка называется палиндромом, если обратная сторона строки совпадает с ней. Например, «abba» является палиндромом, потому что обратная сторона «abba» будет равна «abba».

Алгоритм:
1. Инициализируйте две переменные: l с начала и h с конца данной строки.
2. Теперь мы сравним символы с индексами l и h друг с другом.
3. Если символы не равны, строка не является палиндромом.
4. Если символы равны, мы увеличим l и уменьшим h.
5. Шаги 2,3 и 4 будут повторяться до тех пор, пока (l < h) или мы не обнаружим неравные символы.
6. Если мы достигнем условия ( l < h ), это означает, что все соответствующие символы равны и строка является палиндромом.

Сложность: O(n)

Самая длинная палиндромная подпоследовательность (Longest Palindromic Subsequence)

LPS — это самая длинная последовательность символов, которая является палиндромом.

Алгоритм поиска LPS:
1. Создаем матрицу dp размером n x n, где n - длина исходной строки.
2. Заполняем главную диагональ матрицы значениями 1, так как каждый символ сам по себе является палиндромом длины 1.
3. Перебираем подпоследовательности строки разной длины и заполняем матрицу dp с помощью следующих правил:
- Если символы на текущих позициях равны, увеличиваем значение dpij на 2 и переходим к следующим символам (i+1, j-1).
- Если символы не равны, выбираем максимальное значение из dpi+1j и dpij-1 и записываем его в dpij.
4. Возвращаем значение dp0n-1, которое представляет длину самой длинной палиндромной подпоследовательности.

Сложность: O(n^2), где n - длина исходной строки.

Ханойская башня

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

Алгоритм:
1. Если на исходном стержне есть только один диск, переместите его на целевой стержень.
2. Если на исходном стержне есть больше одного диска, выполните следующие шаги:
- Переместите все диски, кроме самого большого, с исходного стержня на вспомогательный стержень.
- Переместите самый большой диск с исходного стержня на целевой стержень.
- Переместите все оставшиеся диски с вспомогательного стержня на целевой стержень.

Алгоритм: O(2^n), где n - количество дисков.

Алгоритмы замены страниц в операционных системах (FIFO)

Цель алгоритма: уменьшение количества ошибок страниц.

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

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

Сложность: O(n), где n — количество страниц.

Алгоритм оптимальной замены страниц

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

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

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

Сложность: O(n × f), где n — количество страниц, а f — количество кадров.

Least Recently Used алгоритм замены страниц

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

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

Most Recently Used алгоритм замены страниц

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

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

Матрица

Двумерная структура данных, состоящая из набора элементов, расположенных в строках и столбцах.

Каждый элемент матрицы идентифицируется индексами строки и столбца.

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

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

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

Первым сервисом, где внедрили новые алгоритмы, стала Яндекс Музыка. Туда внедрили трансформеную модель с 126 млн параметров и длиной истории пользователей 8192 (события в жизни пользователей). Прирост получился значительный, раньше максимальная конфигурация имела лишь 19 млн в энкодере. Затем технология распространилась на Яндекс Маркет и сейчас тестируется в других сервисах.

По результатам: в Яндекс Музыке пользователи стали на 20% чаще ставить лайки и добавлять в коллекции новые треки и исполнителей, а разнообразие рекомендаций выросло. . Кроме того, «Мою волну» стали слушать дольше и чаще.

Поворот элементов матрицы

Идея состоит в том, чтобы поочередно вращать все кольца элементов, начиная с самого дальнего.

Чтобы повернуть кольцо, нам нужно сделать следующее.
1. Переместить элементы верхнего ряда.
2. Переместить элементы последнего столбца.
3. Переместить элементы нижнего ряда.
4. Переместите элементы первого столбца.

Повторить вышеуказанные шаги для внутреннего кольца, пока оно есть.

Сложность: O(m*n), где m — количество строк, а n — количество столбцов.

Как узнать, является ли число степенью 2?

Чтобы определить, является ли число степенью 2, можно использовать следующий метод:

Проверьте, равно ли число 0. Если да, то 0 не является степенью 2.
Проверьте, является ли число положительным.
Если число положительное, используйте битовую операцию AND с числом (n - 1), где n - это число, которое вы проверяете.
Если результат операции AND равен 0, то число n является степенью 2.

Этот метод основан на том факте, что числа, являющиеся степенями 2, имеют только один бит, установленный в 1 в двоичном представлении (например, 2^3 = 8 в двоичном виде 1000, 2^4 = 16 в двоичном виде 10000). При вычитании единицы из таких чисел, все биты после первого устанавливаются в 1. Таким образом, если вы примените операцию AND к числу и его предшественнику, результат будет равен 0 только в том случае, если число является степенью 2.

Кодирование длин серий (Run-Length Encoding, RLE)

Метод сжатия данных, который основан на замене повторяющихся последовательностей символов кодом, состоящим из символа и длины этой последовательности.

Алгоритм:
1. Читаем символы исходной строки один за другим.
2. Если текущий символ повторяется, увеличиваем счетчик повторений.
3. Если текущий символ отличается от предыдущего или достигнут максимальный предел длины серии, записываем в выходной поток код, состоящий из повторяющегося символа и длины серии.
4. Повторяем шаги 2-3 до тех пор, пока не прочитаем все символы исходной строки.
5. Завершаем сжатие.

Сложность алгоритма зависит от размера исходной строки и количества повторяющихся символов. В худшем случае сложность: O(n^2), где n - размер строки.

Как мы научили навигатор лучше понимать намерения водителя

Раньше любое отклонение от маршрута — и пользователи слышали упрямое «Развернитесь»! Мы решили изменить этот подход.Новый алгоритм в нашем навигаторе:

1️⃣ использует дискриминацию маршрута,
2️⃣ применяет предпочтение рёбер,
3️⃣ учитывает контекст: случайные отклонения, движение по дворам, выбор маршрута,
4️⃣ и включает/отключает алгоритмы по умным триггерам.

Всё это, чтобы навигация в 2ГИС стала удобнее.Подробнее о математике и эвристиках — в статье.

Круговой сдвиг влево

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

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

Круговой сдвиг вправо

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

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

Ближайшая пара точек с использованием алгоритма «Разделяй и властвуй»

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

Алгоритм:
1. Найдите среднюю точку, которая равна P[n/2].
2. Разделите массив на две половины: от P[0] до P[n/2] и от P[n/2+1] до P[n-1].
3. Рекурсивно находим минимальные расстояния в обеих половинах, получая dl и dr.
4. Пусть d будет минимумом dl и dr.
5. Создайте массив «полосы», содержащий точки ближе, чем d к средней вертикальной линии, и отсортируйте его по координатам y.
6. Найдите наименьшее расстояние в массиве полос, рассматривая не более 7 точек после каждой точки.
7. Верните минимум d и расстояние, найденное на шаге 6, как ближайшую пару точек.

Сложность: O(n (Logn)^2)

Проверить, находится ли данная точка внутри или снаружи многоугольника?

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

Сложность: O(N)

Как проверить, лежит ли точка внутри заданных N точек выпуклого многоугольника?

Алгоритм:

1. Отсортируйте данные точки вместе с точкой запроса в порядке возрастания их значений по абсциссе. Если значения абсцисс любых двух точек одинаковы, отсортируйте их по значению ординаты.

2. Установите нижнюю левую точку в качестве начальной точки, а верхнюю правую точку в качестве конечной точки.

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

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

5. Проверьте, существует ли точка запроса в векторе, то она находится вне выпуклой оболочки. Поэтому верните «Нет».

6. Если точка не существует в векторе, то точка лежит внутри выпуклой оболочки.

Сложность: O(N * log(N))

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

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

Алгоритм:

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

2. Отсортируйте оставшиеся n-1 точек по углам вокруг P0 против часовой стрелки. Если углы одинаковы, сначала отдайте приоритет ближайшей точке.

3. Удалите точки с одинаковым углом, оставив только самую дальнюю от P0. Пусть размер нового массива будет m.

4. Если m меньше 3, верните «Выпуклая оболочка невозможна».

5. Создайте пустой стек «S» и поместите первые три точки в «S».

6. Обрабатываем оставшиеся m-3 точки одну за другой. Для каждой точки:
⁃ Пока ориентация двух верхних точек в стеке и «points[i]» не против часовой стрелки, извлекайте точки из стека
⁃ Положите «points[i]» в «S».

7. Стек «S» теперь содержит точки выпуклой оболочки.

Сложность: O(nLogn)