#medium
Задача: 753. Cracking the Safe

Имеется сейф, защищенный паролем. Пароль представляет собой последовательность из n цифр, каждая из которых может находиться в диапазоне [0, k - 1]. Сейф имеет особый способ проверки пароля. Например, правильный пароль - "345", а вы вводите "012345": после ввода 0 последние 3 цифры - "0", что неверно. После ввода 1 последние 3 цифры - "01", что неверно. После ввода 2 последние 3 цифры - "012", что неверно.
После ввода 3 последние 3 цифры - "123", что неверно. После ввода 4 последние 3 цифры - "234", что неверно. После ввода 5 последние 3 цифры - "345", что верно, и сейф разблокируется. Верните любую строку минимальной длины, которая разблокирует сейф на определенном этапе ввода.

Пример:

Input: n = 1, k = 2
Output: "10"

👨‍💻 Алгоритм:

1⃣Создайте граф, где каждая вершина представляет собой строку длины n-1, а каждое ребро между двумя вершинами представляет собой добавление одной из цифр из диапазона [0, k-1].

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

3⃣Составьте итоговую строку, которая включает начальную вершину и все добавленные цифры.

😎 Решение:

fun crackSafe(n: Int, k: Int): String {
    val seen = mutableSetOf<String>()
    val result = StringBuilder()

    fun dfs(node: String) {
        for (x in 0 until k) {
            val neighbor = node + x
            if (!seen.contains(neighbor)) {
                seen.add(neighbor)
                dfs(neighbor.drop(1))
                result.append(x)
            }
        }
    }

    val startNode = "0".repeat(n - 1)
    dfs(startNode)

    result.append(startNode)
    return result.toString()
}

Ставь 👍 и забирай 📚 Базу знаний

#medium
Задача: 754. Reach a Number

Вы стоите в позиции 0 на бесконечной числовой прямой. В позиции target находится пункт назначения. Вы можете сделать некоторое количество ходов numMoves так, чтобы: на каждом ходу вы могли пойти либо налево, либо направо. Во время i-го хода (начиная с i == 1 до i == numMoves) вы делаете i шагов в выбранном направлении. Учитывая целое число target, верните минимальное количество ходов (т.е. минимальное numMoves), необходимое для достижения пункта назначения.

Пример:

Input: target = 2
Output: 3

👨‍💻 Алгоритм:

1⃣Инициализируйте переменную для текущей позиции (position) и счетчик шагов (steps).

2⃣Используйте цикл, чтобы добавлять к position текущее количество шагов и увеличивать steps.

3⃣Если position достигает или превышает target и разница между position и target четная, остановите цикл и верните steps.

😎 Решение:

fun reachTarget(target: Int): Int {
    var target = kotlin.math.abs(target)
    var position = 0
    var steps = 0
    while (position < target || (position - target) % 2 != 0) {
        steps++
        position += steps
    }
    return steps
}

Ставь 👍 и забирай 📚 Базу знаний

#medium
Задача: 755. Pour Water

Вам дана карта высот, представленная в виде целочисленного массива heights, где heights[i] - высота местности в точке i. Ширина в каждой точке равна 1. Вам также даны два целых числа volume и k. Единицы объема воды будут падать в точке k. Вода сначала падает в точке k и упирается в самую высокую местность или воду в этой точке. Затем она течет по следующим правилам: если капля в конечном итоге упадет, двигаясь влево, то двигайтесь влево. Иначе, если капля в конечном итоге упадет, двигаясь вправо, то двигайтесь вправо. Иначе поднимайтесь в текущее положение. Здесь "в конечном итоге упадет" означает, что капля в конечном итоге окажется на более низком уровне, если она будет двигаться в этом направлении. Кроме того, уровень означает высоту местности плюс вода в этом столбе. Мы можем предположить, что на двух сторонах, выходящих за пределы массива, есть бесконечно высокая местность. Также не может быть частичного равномерного распределения воды более чем на один блок сетки, и каждая единица воды должна находиться ровно в одном блоке.

Пример:

Input: heights = [2,1,1,2,1,2,2], volume = 4, k = 3
Output: [2,2,2,3,2,2,2]

👨‍💻 Алгоритм:

1⃣Инициализируйте цикл для добавления объема воды.

2⃣Для каждой единицы воды: Проверьте, может ли вода двигаться влево и упасть на более низкий уровень. Если нет, проверьте, может ли вода двигаться вправо и упасть на более низкий уровень. Если нет, добавьте воду в текущую позицию.

3⃣Повторите шаг 2, пока не будет добавлен весь объем воды.

😎 Решение:

fun pourWater(heights: IntArray, volume: Int, k: Int): IntArray {
    for (v in 0 until volume) {
        var dropIndex = k
        for (d in listOf(-1, 1)) {
            var i = k
            while (i + d in heights.indices && heights[i + d] <= heights[i]) {
                if (heights[i + d] < heights[i]) {
                    dropIndex = i + d
                }
                i += d
            }
            if (dropIndex != k) break
        }
        heights[dropIndex]++
    }
    return heights
}

Ставь 👍 и забирай 📚 Базу знаний

#medium
Задача: 756. Pyramid Transition Matrix

Вы складываете блоки так, чтобы получилась пирамида. Каждый блок имеет цвет, который представлен одной буквой. Каждый ряд блоков содержит на один блок меньше, чем ряд под ним, и располагается по центру сверху. Чтобы пирамида выглядела эстетично, допускаются только определенные треугольные узоры. Треугольный узор состоит из одного блока, уложенного поверх двух блоков. Шаблоны задаются в виде списка допустимых трехбуквенных строк, где первые два символа шаблона представляют левый и правый нижние блоки соответственно, а третий символ - верхний блок. Например, "ABC" представляет треугольный шаблон с блоком 'C', уложенным поверх блоков 'A' (слева) и 'B' (справа). Обратите внимание, что это отличается от "BAC", где "B" находится слева внизу, а "A" - справа внизу. Вы начинаете с нижнего ряда блоков bottom, заданного в виде одной строки, который вы должны использовать в качестве основания пирамиды. Учитывая bottom и allowed, верните true, если вы можете построить пирамиду до самой вершины так, чтобы каждый треугольный узор в пирамиде был в allowed, или false в противном случае.

Пример:

Input: bottom = "BCD", allowed = ["BCC","CDE","CEA","FFF"]
Output: true

👨‍💻 Алгоритм:

1⃣Создайте структуру данных для хранения допустимых треугольных узоров.

2⃣Напишите рекурсивную функцию, которая проверяет возможность построения следующего уровня пирамиды.

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

😎 Решение:

class Solution {
    fun pyramidTransition(bottom: String, allowed: List<String>): Boolean {
        val allowedDict = mutableMapOf<String, MutableList<Char>>()

        for (pattern in allowed) {
            val key = pattern.substring(0, 2)
            val value = pattern[2]
            allowedDict.computeIfAbsent(key) { mutableListOf() }.add(value)
        }

        return canBuild(bottom, allowedDict)
    }

    private fun canBuild(currentLevel: String, allowedDict: Map<String, List<Char>>): Boolean {
        if (currentLevel.length == 1) return true

        val nextLevelOptions = mutableListOf<List<Char>>()
        for (i in 0 until currentLevel.length - 1) {
            val key = currentLevel.substring(i, i + 2)
            if (!allowedDict.containsKey(key)) return false
            nextLevelOptions.add(allowedDict[key]!!)
        }

        return canBuildNextLevel(nextLevelOptions, 0, "", allowedDict)
    }

    private fun canBuildNextLevel(options: List<List<Char>>, index: Int, nextLevel: String, allowedDict: Map<String, List<Char>>): Boolean {
        if (index == options.size) return canBuild(nextLevel, allowedDict)
        for (option in options[index]) {
            if (canBuildNextLevel(options, index + 1, nextLevel + option, allowedDict)) return true
        }
        return false
    }
}

Ставь 👍 и забирай 📚 Базу знаний

#hard
Задача: 757. Set Intersection Size At Least Two

Вам дан двумерный целочисленный массив intervals, в котором intervals[i] = [starti, endi] представляет все целые числа от starti до endi включительно. Содержащее множество - это массив nums, в котором каждый интервал из intervals содержит не менее двух целых чисел в nums. Например, если intervals = [[1,3], [3,7], [8,9]], то [1,2,4,7,8,9] и [2,3,4,8,9] - содержащие множества. Верните минимально возможный размер содержащего множества.

Пример:

Input: intervals = [[1,3],[3,7],[8,9]]
Output: 5

👨‍💻 Алгоритм:

1⃣Отсортируйте интервалы по их конечным точкам.

2⃣Инициализируйте пустое множество для хранения чисел.

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

😎 Решение:

fun minSetSize(intervals: Array<IntArray>): Int {
    intervals.sortBy { it[1] }
    val nums = mutableListOf<Int>()
    for (interval in intervals) {
        val start = interval[0]
        val end = interval[1]
        if (nums.isEmpty() || nums.last() < start) {
            nums.add(end - 1)
            nums.add(end)
        } else if (nums.last() == end - 1) {
            nums.add(end)
        }
    }
    return nums.size
}

Ставь 👍 и забирай 📚 Базу знаний

На easyoffer 2.0 появится:
🎯 Тренажер "Проработка вопросов"

✅ Метод интервальных повторений и флеш-карточки
✅ Персональный подход изучения на основе ваших ответов
✅ Упор на самые частые вопросы

📌 Интервальные повторения по карточкам это научно доказанный метод эффективного обучения. Каждая карточка – это вопрос, который задают на собеседовании, вы можете выбрать "Не знаю", "Знаю", "Не спрашивать". После ответа вам показывается правильный ответ и возможность изучить вопрос подробнее (примеры ответов других людей). От ваших ответов зависит то, как часто карточки будут показываться на следующей тренировке. Трудные вопросы показываются чаще, простые – реже. Это позволяет бить в слабые места. Кроме того, изначальный порядок карточек зависит от частотности (вероятности встретить вопрос).

🚀 Благодаря этому тренажеру вы сможете очень быстро подготовиться к собеседованию, т.к. фокусируетесь отвечать на самые частые вопросы. Именно так готовился я сам, когда искал первую работу программистом.

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

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

#medium
Задача: 758. Bold Words in String

При наличии массива ключевых слов и строки a выделите все ключевые слова [i] жирным шрифтом. Все буквы между тегами <b> и </b> выделяются жирным шрифтом.

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

Пример:

Input: words = ["ab","bc"], s = "aabcd"
Output: "a<b>abc</b>d"

👨‍💻 Алгоритм:

1⃣Создайте массив для хранения флагов, указывающих, какие символы в строке a должны быть выделены жирным шрифтом.

2⃣Пройдите по каждому ключевому слову и отметьте соответствующие позиции в массиве флагов.

3⃣Постройте результирующую строку, добавляя теги <b> и </b> на основе массива флагов.

😎 Решение:

fun addBoldTags(keywords: Array<String>, s: String): String {
    val n = s.length
    val bold = BooleanArray(n)
    
    for (word in keywords) {
        var start = s.indexOf(word)
        while (start != -1) {
            for (i in start until start + word.length) {
                bold[i] = true
            }
            start = s.indexOf(word, start + 1)
        }
    }
    
    val result = StringBuilder()
    var i = 0
    while (i < n) {
        if (bold[i]) {
            result.append("<b>")
            while (i < n && bold[i]) {
                result.append(s[i])
                i++
            }
            result.append("</b>")
        } else {
            result.append(s[i])
            i++
        }
    }
    
    return result.toString()
}

Ставь 👍 и забирай 📚 Базу знаний

#hard
Задача: 759. Employee Free Time

Нам дан список schedule of employees, который представляет собой рабочее время каждого сотрудника. У каждого сотрудника есть список непересекающихся интервалов, и эти интервалы расположены в отсортированном порядке. Верните список конечных интервалов, представляющих общее свободное время положительной длины для всех сотрудников, также в отсортированном порядке. (Хотя мы представляем интервалы в форме [x, y], объекты внутри них являются интервалами, а не списками или массивами. Например, schedule[0][0].start = 1, schedule[0][0].end = 2, а schedule[0][0][0] не определено).Также мы не будем включать в наш ответ интервалы типа [5, 5], так как они имеют нулевую длину.

Пример:

Input: schedule = [[[1,2],[5,6]],[[1,3]],[[4,10]]]
Output: [[3,4]]

👨‍💻 Алгоритм:

1⃣Объедините все интервалы всех сотрудников в один список и отсортируйте его по начальным временам.

2⃣Объедините пересекающиеся интервалы в один.

3⃣Найдите промежутки между объединенными интервалами, представляющие свободное время.

😎 Решение:

class Interval(var start: Int, var end: Int)

fun employeeFreeTime(schedule: List<List<Interval>>): List<Interval> {
    val intervals = mutableListOf<Interval>()
    for (employee in schedule) {
        intervals.addAll(employee)
    }
    
    intervals.sortBy { it.start }
    
    val merged = mutableListOf<Interval>()
    for (interval in intervals) {
        if (merged.isEmpty() || merged.last().end < interval.start) {
            merged.add(interval)
        } else {
            merged.last().end = maxOf(merged.last().end, interval.end)
        }
    }
    
    val freeTime = mutableListOf<Interval>()
    for (i in 1 until merged.size) {
        if (merged[i].start > merged[i - 1].end) {
            freeTime.add(Interval(merged[i - 1].end, merged[i].start))
        }
    }
    
    return freeTime
}

Ставь 👍 и забирай 📚 Базу знаний

#easy
Задача: 760. Find Anagram Mappings

Вам даны два целочисленных массива nums1 и nums2, где nums2 - анаграмма nums1. Оба массива могут содержать дубликаты. Верните индексное отображение массива mapping из nums1 в nums2, где mapping[i] = j означает, что i-й элемент в nums1 появляется в nums2 по индексу j. Если ответов несколько, верните любой из них. Массив a является анаграммой массива b означает, что b создается путем случайного изменения порядка элементов в a.

Пример:

Input: nums1 = [12,28,46,32,50], nums2 = [50,12,32,46,28]
Output: [1,4,3,2,0]

👨‍💻 Алгоритм:

1⃣Создайте словарь для хранения индексов элементов в nums2.

2⃣Пройдите по элементам массива nums1 и для каждого элемента найдите соответствующий индекс в nums2, используя словарь.

3⃣Верните массив индексов.

😎 Решение:

fun anagramMapping(nums1: IntArray, nums2: IntArray): IntArray {
    val indexMap = mutableMapOf<Int, MutableList<Int>>()
    for (i in nums2.indices) {
        indexMap.computeIfAbsent(nums2[i]) { mutableListOf() }.add(i)
    }
    
    val mapping = IntArray(nums1.size)
    for (i in nums1.indices) {
        mapping[i] = indexMap[nums1[i]]!!.removeAt(indexMap[nums1[i]]!!.size - 1)
    }
    
    return mapping
}

Ставь 👍 и забирай 📚 Базу знаний

#hard
Задача: 761. Special Binary String

Специальные двоичные строки - это двоичные строки, обладающие следующими двумя свойствами: количество 0 равно количеству 1. Каждый префикс двоичной строки имеет не меньше 1, чем 0. Вам дана специальная двоичная строка s. Ход состоит в выборе двух последовательных, непустых специальных подстрок s и их обмене. Две строки являются последовательными, если последний символ первой строки находится ровно на один индекс раньше первого символа второй строки. Верните лексикографически наибольшую результирующую строку, возможную после применения указанных операций над строкой.

Пример:

Input: s = "11011000"
Output: "11100100"

👨‍💻 Алгоритм:

1⃣Определите, что специальная двоичная строка можно разбить на несколько специальных подстрок.

2⃣Рекурсивно примените к каждой подстроке этот алгоритм, чтобы найти лексикографически наибольшую строку.

3⃣Сортируйте полученные подстроки в лексикографическом порядке по убыванию и объединяйте их.

😎 Решение:

fun makeLargestSpecial(s: String): String {
    var count = 0
    var i = 0
    val substrs = mutableListOf<String>()
    for (j in s.indices) {
        count += if (s[j] == '1') 1 else -1
        if (count == 0) {
            substrs.add("1" + makeLargestSpecial(s.substring(i + 1, j)) + "0")
            i = j + 1
        }
    }
    return substrs.sortedDescending().joinToString("")
}

Ставь 👍 и забирай 📚 Базу знаний

#hard
Задача: 762. Prime Number of Set Bits in Binary Representation

Если даны два целых числа left и right, верните количество чисел в диапазоне [left, right], имеющих простое число битов в двоичном представлении. Напомним, что число битов в двоичном представлении - это количество единиц, присутствующих в числе 1. Например, 21 в двоичном представлении - это 10101, которое имеет 3 бита.

Пример:

Input: left = 10, right = 15
Output: 5

👨‍💻 Алгоритм:

1⃣Создайте функцию для подсчета количества единиц в двоичном представлении числа.

2⃣Создайте функцию для проверки, является ли число простым.

3⃣Пройдите через все числа в диапазоне [left, right] и подсчитайте числа, у которых количество битов в двоичном представлении является простым числом.

😎 Решение:

fun countPrimeSetBits(left: Int, right: Int): Int {
    fun countBits(x: Int): Int {
        return x.toString(2).count { it == '1' }
    }
    
    fun isPrime(x: Int): Boolean {
        if (x < 2) return false
        for (i in 2..Math.sqrt(x.toDouble()).toInt()) {
            if (x % i == 0) return false
        }
        return true
    }
    
    var count = 0
    for (num in left..right) {
        if (isPrime(countBits(num))) {
            count++
        }
    }
    return count
}

Ставь 👍 и забирай 📚 Базу знаний

#medium
Задача: 763. Partition Labels

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

Пример:

Input: s = "ababcbacadefegdehijhklij"
Output: [9,7,8]

👨‍💻 Алгоритм:

1⃣Создайте словарь для хранения последней позиции каждой буквы в строке.

2⃣Пройдите по строке, отслеживая максимальную позицию текущей части.

3⃣Когда текущая позиция совпадает с максимальной позицией, завершите часть и начните новую.

😎 Решение:

fun partitionLabels(s: String): List<Int> {
    val lastPos = IntArray(26)
    for (i in s.indices) {
        lastPos[s[i] - 'a'] = i
    }
    
    val partitions = mutableListOf<Int>()
    var j = 0
    var anchor = 0
    for (i in s.indices) {
        j = maxOf(j, lastPos[s[i] - 'a'])
        if (i == j) {
            partitions.add(i - anchor + 1)
            anchor = i + 1
        }
    }
    return partitions
}

Ставь 👍 и забирай 📚 Базу знаний

На easyoffer 2.0 появится новый раздел:
Задачи с собеседований

🟠Задачи на Алгоритмические, Live-coding и System Design из реальных собеседований
🟠Вероятность встретить ту или иную задачу
🟠Возможность подготовиться к задачам конкретной компании

Есть много сайтов, на которых можно тренироваться решать задачи, но у них у всех одна проблема – сами задачи люди просто выдумывают. На easyoffer 2.0 вы сможете готовиться к live-coding и system design секциям на основе задач из реальных собеседований. Вы можете найдете самые частые задачи и сделаете упор на их решение.

Считаные дни остались до старта краудфандинговой кампании, чтобы ускорить разработку easyoffer 2.0. Все кто, поддержал проект на этом этапе смогу получить 1 год доступа к сайту по цене месячной подписки, а те кто поддержат проект раньше других ито дешевле + получат существенный бонус. Следите за стартом 👉 в этом телеграм канале.

Задача: 1379. Find a Corresponding Node of a Binary Tree in a Clone of That Tree
Сложность: easy

Даны два бинарных дерева: original и cloned, а также ссылка на узел target в оригинальном дереве.

Дерево cloned является копией оригинального дерева.

Верните ссылку на тот же узел в дереве cloned.

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

Пример:

Input: tree = [7,4,3,null,null,6,19], target = 3
Output: 3
Explanation: In all examples the original and cloned trees are shown. The target node is a green node from the original tree. The answer is the yellow node from the cloned tree.

👨‍💻 Алгоритм:

1⃣Добавьте корень в очередь.

2⃣Пока очередь не пуста, извлекайте узел из очереди. Если узел является целевым, завершите выполнение. Добавьте сначала левый, затем правый дочерний узел в очередь.

3⃣Верните ссылку на найденный целевой узел.

😎 Решение:

class Solution {
    fun getTargetCopy(original: TreeNode?, cloned: TreeNode?, target: TreeNode?): TreeNode? {
        val queue_o: Queue<TreeNode?> = LinkedList()
        val queue_c: Queue<TreeNode?> = LinkedList()
        
        queue_o.add(original)
        queue_c.add(cloned)
        
        while (queue_o.isNotEmpty()) {
            val node_o = queue_o.poll()
            val node_c = queue_c.poll()
            
            if (node_o == target) {
                return node_c
            }
            
            if (node_o?.left != null) {
                queue_o.add(node_o.left)
                queue_c.add(node_c?.left)
            }
            if (node_o?.right != null) {
                queue_o.add(node_o.right)
                queue_c.add(node_c?.right)
            }
        }
        return null
    }
}

Ставь 👍 и забирай 📚 Базу знаний

Задача: 1036. Escape a Large Maze
Сложность: hard

Имеется сетка размером 1 миллион на 1 миллион на плоскости XY, координаты каждого квадрата сетки - (x, y). Мы начинаем с исходного квадрата = [sx, sy] и хотим достичь цели = [tx, ty]. Существует также массив заблокированных квадратов, где каждый заблокированный[i] = [xi, yi] представляет собой заблокированный квадрат с координатами (xi, yi). Каждый ход мы можем пройти один квадрат на север, восток, юг или запад, если квадрат не находится в массиве заблокированных квадратов. Нам также не разрешается выходить за пределы сетки. Возвращается true тогда и только тогда, когда можно достичь целевого квадрата из исходного квадрата с помощью последовательности правильных ходов.

Пример:

Input: blocked = [[0,1],[1,0]], source = [0,0], target = [0,2]
Output: false

👨‍💻 Алгоритм:

1⃣Обработка входных данных:
Загрузите координаты исходного квадрата sx, sy, целевого квадрата tx, ty и список заблокированных квадратов blocked.

2⃣Проверка простого случая:
Если список blocked пуст, верните true, так как путь не будет заблокирован.
Проверка начальной или целевой клетки:
Если исходная или целевая клетка заблокированы, верните false.

3⃣Поиск пути с использованием BFS или DFS:
Используйте алгоритм поиска в ширину (BFS) или поиска в глубину (DFS) для поиска пути от sx, sy до tx, ty, избегая заблокированных клеток.
Если обнаружен путь, верните true, в противном случае верните false.

😎 Решение:

class Solution {
    fun isEscapePossible(blocked: Array<IntArray>, source: IntArray, target: IntArray): Boolean {
        val blockedSet = blocked.map { it[0] to it[1] }.toSet()
        val source = source[0] to source[1]
        val target = target[0] to target[1]

        if (source in blockedSet || target in blockedSet) return false

        fun bfs(start: Pair<Int, Int>, end: Pair<Int, Int>): Boolean {
            val queue = ArrayDeque<Pair<Int, Int>>()
            queue.add(start)
            val visited = mutableSetOf(start)
            val directions = listOf(0 to 1, 1 to 0, 0 to -1, -1 to 0)
            val maxArea = blocked.size * (blocked.size - 1) / 2

            while (queue.isNotEmpty()) {
                if (visited.size > maxArea) return true
                val (x, y) = queue.removeFirst()
                for ((dx, dy) in directions) {
                    val nx = x + dx
                    val ny = y + dy
                    if (nx in 0 until 1_000_000 && ny in 0 until 1_000_000 && nx to ny !in visited && nx to ny !in blockedSet) {
                        if (nx to ny == end) return true
                        queue.add(nx to ny)
                        visited.add(nx to ny)
                    }
                }
            }
            return false
        }

        return bfs(source, target) && bfs(target, source)
    }
}

Ставь 👍 и забирай 📚 Базу знаний

На easyoffer 2.0 появится:
Тренажер "Реальное собеседование"

🟠 Сценарии вопросов из реального собеседования
🟠Возможность подготовиться к собеседованию в конкретную компанию
🟠Итоговая статистика (прошёл/не прошёл)

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

Уже в начале следующей недели стартует краудфандинг кампания, чтобы ускорить разработку easyoffer 2.0. Все кто, поддержал проект на этом этапе смогу получить 1 год доступа к сайту по цене месячной подписки. Первые 150 донатеров получать особо-выгодную цену и бонус. Следите за стартом 👉 в этом телеграм канале, в нем информация о старте будет опубликована за 6 часов до официального начала.

Задача: 897. Increasing Order Search Tree
Сложность: easy

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

Пример:

Input: root = [5,3,6,2,4,null,8,1,null,null,null,7,9]
Output: [1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9]

👨‍💻 Алгоритм:

1⃣Выполнить обход дерева в порядке in-order, чтобы получить список узлов.

2⃣Перестроить дерево, устанавливая каждый узел из списка как правый дочерний элемент предыдущего узла и устанавливая левые дочерние элементы в null.

3⃣Вернуть новый корень дерева (первый элемент списка).

😎 Решение:

class TreeNode(var `val`: Int = 0) {
    var left: TreeNode? = null
    var right: TreeNode? = null
}

fun increasingBST(root: TreeNode?): TreeNode? {
    val nodes = mutableListOf<TreeNode>()
    
    fun inorder(node: TreeNode?) {
        if (node == null) return
        inorder(node.left)
        nodes.add(node)
        inorder(node.right)
    }
    
    inorder(root)
    
    for (i in 0 until nodes.size - 1) {
        nodes[i].left = null
        nodes[i].right = nodes[i + 1]
    }
    
    nodes.last().left = null
    nodes.last().right = null
    return nodes.first()

Ставь 👍 и забирай 📚 Базу знаний

Задача: 918. Maximum Sum Circular Subarray
Сложность: medium

Если задан круговой целочисленный массив nums длины n, верните максимально возможную сумму непустого подмассива nums. Круговой массив означает, что конец массива соединяется с его началом. Формально, следующий элемент nums[i] равен nums[(i + 1) % n], а предыдущий элемент nums[i] равен nums[(i - 1 + n) % n]. Подмассив может включать каждый элемент фиксированного буфера nums не более одного раза. Формально, для подмассива nums[i], nums[i + 1], ..., nums[j] не существует i <= k1, k2 <= j, при этом k1 % n == k2 % n.

Пример:

Input: nums = [1,-2,3,-2]
Output: 3

👨‍💻 Алгоритм:

1⃣Найти стандартную максимальную сумму подмассива с помощью алгоритма Кадане.

2⃣Найти минимальную сумму подмассива с помощью алгоритма Кадане и вычесть ее из общей суммы массива.

3⃣Вернуть максимум между стандартной максимальной суммой подмассива и общей суммой массива минус минимальную сумму подмассива, если результат не равен 0 (чтобы учесть случай, когда все числа отрицательные).

😎 Решение:

class Solution {
    fun maxSubarraySumCircular(nums: IntArray): Int {
        fun kadane(arr: IntArray): Int {
            var currentSum = arr[0]
            var maxSum = arr[0]
            for (i in 1 until arr.size) {
                currentSum = maxOf(arr[i], currentSum + arr[i])
                maxSum = maxOf(maxSum, currentSum)
            }
            return maxSum
        }

        val maxKadane = kadane(nums)
        val totalSum = nums.sum()
        val minKadane = kadane(nums.map { -it }.toIntArray())

        return maxOf(maxKadane, if (totalSum + minKadane == 0) maxKadane else totalSum + minKadane)
    }
}

Ставь 👍 и забирай 📚 Базу знаний

Задача: 1012. Numbers With Repeated Digits
Сложность: hard

Задав целое число n, верните количество положительных целых чисел в диапазоне [1, n], у которых хотя бы одна цифра повторяется.

Пример:

Input: n = 20
Output: 1

👨‍💻 Алгоритм:

1⃣Вычисление всех чисел с уникальными цифрами:
Найдите количество чисел в диапазоне [1, n], у которых все цифры уникальны. Для этого используйте перебор всех чисел и проверку уникальности цифр.

2⃣Вычисление всех чисел в диапазоне [1, n]:
Это значение равно n, поскольку это количество всех чисел от 1 до n включительно.

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

😎 Решение:

class Solution {
    fun numDupDigitsAtMostN(n: Int): Int {
        fun countUniqueDigitNumbers(x: Int): Int {
            val s = x.toString()
            val n = s.length
            var res = (1 until n).sumBy { 9 * permutation(9, it - 1) }
            val used = mutableSetOf<Int>()
            for (i in s.indices) {
                for (j in (if (i == 0) 1 else 0) until (s[i] - '0')) {
                    if (!used.contains(j)) {
                        res += permutation(9 - i, n - i - 1)
                    }
                }
                if (used.contains(s[i] - '0' - '0')) {
                    break
                }
                used.add(s[i] - '0' - '0')
            }
            if (used.size == n) res += 1
            return res
        }

        fun permutation(m: Int, n: Int): Int {
            return if (n == 0) 1 else permutation(m, n - 1) * (m - n + 1)
        }

        return n - countUniqueDigitNumbers(n)
    }
}

Ставь 👍 и забирай 📚 Базу знаний

Задача: 422. Valid Word Square
Сложность: easy

Дан массив строк words, верните true, если он образует правильный квадрат слов.

Последовательность строк образует правильный квадрат слов, если k-я строка и k-й столбец читаются одинаково, где 0 <= k < max(numRows, numColumns).

Пример:

Input: words = ["abcd","bnrt","crmy","dtye"]
Output: true
Explanation:
The 1st row and 1st column both read "abcd".
The 2nd row and 2nd column both read "bnrt".
The 3rd row and 3rd column both read "crmy".
The 4th row and 4th column both read "dtye".
Therefore, it is a valid word square.

👨‍💻 Алгоритм:

1⃣Инициализируйте переменные: cols для максимальной длины слов в массиве, rows для количества строк в массиве words, и пустой массив newWords для хранения новых слов, представленных каждым столбцом.

2⃣Итерация по массиву words, определение максимальной длины слова для cols, проверка, что количество строк равно количеству столбцов. Если условие не выполняется, возвращаем false.

3⃣Для каждого столбца col от 0 до cols - 1, формируем строку newWord из символов на позиции (row, col) для каждой строки. Сохраняем newWord в массиве newWords. В конце, если newWords и words равны, возвращаем true, иначе false.

😎 Решение:

class Solution {
    fun validWordSquare(words: List<String>): Boolean {
        var cols = 0
        val rows = words.size
        val newWords = mutableListOf<String>()
        
        for (word in words) {
            cols = maxOf(cols, word.length)
        }

        if (cols != words[0].length || rows != cols) {
            return false
        }

        for (col in 0 until cols) {
            var newWord = ""
            for (row in 0 until rows) {
                if (col < words[row].length) {
                    newWord += words[row][col]
                }
            }
            newWords.add(newWord)
        }

        return words == newWords
    }
}

Ставь 👍 и забирай 📚 Базу знаний

На easyoffer 2.0 появится:
База тестовых заданий

🟠Тестовые задания для разных грейдов
🟠Фильтрация тестовых заданий по технологиям и компаниям

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

В течение 1-2 дней я объявлю о краудфандинг кампании, чтобы ускорить разработку easyoffer 2.0. Все кто, поддержал проект на этом этапе смогу получить 1 год доступа к сайту по цене месячной подписки и смогут попасть на закрытое бета-тестирование. А первые 150 донатеров получать особо-выгодную цену и бонус.

🚀 Следите за стартом 👉 в этом телеграм канале, в нем информация о старте будет опубликована за 6 часов до официального начала.