DEV Community: faangmaster

Задача с собеседования в Google: Sort Colors

faangmaster — Wed, 19 Nov 2025 12:09:27 +0000

Задача

Дан массив целых чисел. Значения могут быть только 0, 1 и 2. Нужно отсортировать на месте (без доп. памяти). Использовать библиотечные функции сортировки нельзя.

Например,

Input: nums = [2,0,2,1,1,0]
Output: [0,0,1,1,2,2]

Input: nums = [2,0,1]
Output: [0,1,2]

Ссылка на leetcode: https://leetcode.com/problems/sort-colors

Решение

Сортировки вроде QuickSort, MergeSort не подходят, т.к. используют дополнительную память. QuickSort - O(log(n)) для рекурсии, MergeSort - O(n) для временного массива.

Простые сортировки, вроде Bubble Sort, Insertion Sort, Selection Sort дополнительной памяти не требуют и работают за O(1), но временная сложность - O(n^2). Хотелось бы побыстрее.

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

В коде это выглядит так:

int zeros = 0, ones = 0, twos = 0;

//считаем, сколько у нас нулей, единичек и двоек
for (int num : nums) {
    if (num == 0) {
        zeros++;
    } else if (num == 1) {
        ones++;
    } else {
        twos++;
    }
}

//записываем нужное число нулей, единичек и двоек в порядке возрастания
int i = 0;
while (zeros > 0) {
    nums[i++] = 0;
    zeros--;
}
while (ones > 0) {
    nums[i++] = 1;
    ones--;
}
while (twos > 0) {
    nums[i++] = 2;
    twos--;
}

Time Complexity = O(2*n) = O(n)
Space Complexity = O(1)

Работает без доп. памяти за линейное время.

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

Dutch national flag problem

Вообще, это известная задача - Dutch national flag problem. Ее предложил Edsger W. Dijkstra. Он сам родом из Нидерландов.

Эту задачу можно решить за один проход при помощи трех указателей (Three pointers).

Для этого нужно объявить 3 указателя, которые делят массив на 4 области:
1) [0..left-1] — все нули
2) [left..current-1] — все единички
3) [current..right] - еще необработанная зона
4) [right+1..N-1] - все двойки

left - определяет границу, слева от которой, у нас только нули.
right - определяет границу, справа от которой, у нас только двойки.
current - текущий элемент, опеределяет две границы: 1) слева до left включительно - только единички 2) справа до right включительно - еще не известно (необработанная зона).

Например:

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

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

Изменять указатели будем до тех пор, пока current не станет больше right (current > right). В таком случае у нас исчезнет область 3 (необработанная), т.к. она [current..right], а в конце у нас current > right. Т.е. эта область станет пустой. Тогда у нас останутся три области, которые будут идти одна за другой в нужном нам порядке.

Инициализируем указатели следующими значениями:
left = 0
current = 0
right = N-1

Проверим, соблюдаются ли в начале наши инварианты:
1) [0..left-1] — все нули -> [0..-1] - пустая область, соблюдается
2) [left..current-1] — все единички -> [0..-1] -> пустая область, соблюдается
3) [current..right] - еще необработанная зона -> [0..N-1] - весь массив необработан, соблюдается
4) [right+1..N-1] - все двойки -> [N..N-1] - пустая область, соблюдается

При проходе массива мы можем встретить 3 значения (0, 1, 2). Давайте посмотрим, что делать при каждом из трех вариантов, чтобы сохранить наши инварианты (области):
1) nums[current] == 0.
Меняем местами nums[left] и nums[current], инкрементируем left и current. Тогда nums[left] станет равным 0 и можно расширить область с ноликами (left++). На nums[current] станет то, что было на nums[left]. А что там могло быть?

Если мы соблюдали инварианты - там могла быть единичка. Если единичка, то она встанет на место nums[current] = 1 и область с единичками можно расширить. Поэтому current++. Необработанная область уменьшится на 1, а область с двойками не изменится. Так, что в этом случае все инварианты соблюдаются.
Там мог быть нолик. Если область с единичками у нас пустая. left == current. Тогда swap, по факту, ничего не переставит. Мы увеличим область с ноликами, область с единичками останется пустой left == current.
Двойки там быть не могло, для этого left должно быть больше current.

2) nums[current] == 1. Делаем только current++. Области с ноликами и двойками не меняются. Область с единичками растет на 1 и область с необработанными числами сокращается на 1.

3) nums[current] == 2. Меняем местами nums[right] и nums[current], уменьшаем на единицу right: right--.
Это увеличит область с двойками на единицу. Остальные области не изменятся. Почему по аналогии нельзя увеличить current? В данном случае, nums[right] был в необработанной области и мы не знаем какое там было значение. Поэтому nums[current] после обмена останется неизвестным с необработанной зоне.

Почему мы выйдем из цикла? на каждой итерации мы увелициваем или current или уменьшаем right. Рано или поздно, current станет больше, чем right.

В коде это выглядит так:

public void sortColors(int[] nums) {
    int left = 0;
    int right = nums.length - 1;
    int current = 0;
    while (current <= right) {
        if (nums[current] == 0) {
            swap(nums, left, current);
            left++;
            current++;
        } else if (nums[current] == 1) {
            current++;
        } else {
            swap(nums, current, right);
            right--;
        }
    }
}

private void swap(int nums[], int i, int j) {
    int tmp = nums[i];
    nums[i] = nums[j];
    nums[j] = tmp;
}

Time Complexity = O(n)
Space Complexity = O(1).

Давайте теперь пройдем по шагам на примере:

Вначале: left == current == 0, right == N-1 == 5. Все области пустые, кроме необработанной. Отметил ее красным цветом.

Итерация 1:

nums[current] == 2. Меняем swap(current, right) местами и уменьшаем right на 1:

Оранжевым отметил область с двойками.

Итерация 2:

nums[current] == 0. Меняем swap(current, left) местами и увеличиваем left и current на единицу:

Зеленым отметил область с ноликами.

Итерация 3:

nums[current] == 0. Меняем swap(current, left) местами и увеличиваем left и current на единицу:

Итерация 4:

nums[current] == 2. Меняем swap(current, right) местами и уменьшаем right на 1:

Итерация 5:

nums[current] == 1. Увеличиваем current на единицу. Синим цветом отметил область с единичками:

Итерация 6:

nums[current] == 1. Увеличиваем current на единицу. Синим цветом отметил область с единичками:

Итерация 7:

current > right. Вываливаемся из цикла. Работа алгоритма закончена.

Задача с собеседования в Google: Russian Doll Envelopes

faangmaster — Fri, 14 Nov 2025 13:47:06 +0000

Задача

Дан двумерный массив envelopes, где envelopes[i] = [wᵢ, hᵢ] — ширина и высота i-го конверта.
Один конверт может быть вложен в другой, если его ширина и высота строго меньше ширины и высоты другого конверта.

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

Например,
envelopes = [[5,4],[6,4],[6,7],[2,3]]

Output: 3.
Можно вложить максимум 3 конверта друг в друга: [2,3] => [5,4] => [6,7]

Input: envelopes = [[1,1],[1,1],[1,1]]
Output: 1
По условию, конверты, одинаковые хотя бы по одному измерению, нельзя вкладывать друг в друга.

Ссылка на leetcode: https://leetcode.com/problems/russian-doll-envelopes/description/

Решение

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

Решение при помощи Динамического Программирования

Вообще, если вы уже решали другую задачу: Longest Increasing Subsequence, то можно заметить, что это похожая задача. Просто двумерная. Решение этой задачи при помощи динамического программирования есть у меня на youtube-канале: Longest Increasing Subsequence

Давайте применим подход bottom-up. Для этого разобьём задачу на подзадачи и установим связь между решениями подзадач и решением общей задачи.
Подзадача в нашем случае — это значение dp[i] - длина максимальной цепочки вложенных друг в друга конвертов, оканчивающейся на конверте i.

Следует также отметить отличие этой задачи от задачи Longest Increasing Subsequence: там относительный порядок элементов в подпоследовательности не может быть произвольным — он должен совпадать с их порядком в исходной последовательности. В нашей же задаче порядок в исходном массиве может быть произвольным, и сохранять его не нужно; важно лишь, чтобы выполнялось условие вложения одного конверта в другой. Поэтому, чтобы при вычислении dp[i] не ходить по всему массиву конвертов, мы можем отсортировать массив конвертов по его размерам в порядке возрастания, тогда нам достаточно будет проверять все конверты слева(меньшие) от текущего.

Сортировку сделаем по одному из имерений (например, ширине). Более того, если ширина конвертов одинаковая, отсортируем из по возрастанию второго измерения - высоты:

Arrays.sort(envelopes, (a, b) -> {
    if (a[0] == b[0]) {
        return Integer.compare(a[1], b[1]);    
    }
    return Integer.compare(a[0], b[0]);
});

Теперь осталось определить связь подзадач и общей задачей. Тут все также как и в Longest Increasing Subsequence. Для вычисления dp[i] нам нужно пройти по всем dp[j] слева от нашего конверта (меньшие), проверить, что они влезают в наш i-конверт.
Если конверт j влезает в текущий конверт i, то мы можем сделать цепочку из вложенных конвертов dp[j] + 1. Т.к. dp[j] - максимальная длинна вложенных конвертов, заканчивающаяся на конверте j, то если мы можем эту цепочку вложить в конверт i, то длина такой цепочки будет dp[j] + 1. Для вычисления dp[i], нужно найти максимум из {dp[j] + 1, j = 0..i - 1} среди тех конвертов j, которые влезают в i-конверт.
В коде это будет выглядеть так:

for (int j = 0; j < i; j++) {
    if (влезает ли j конверт в i конверт) {
        dp[i] = Math.max(dp[i], dp[j] + 1);
    }
}

Тогда ответом на задачу будет наибольший dp[i].

В коде все вместе это выглядит так:

    public int maxEnvelopes(int[][] envelopes) {
        //Сортируем по размерам
        Arrays.sort(envelopes, (a, b) -> {
            if (a[0] == b[0]) {
                return Integer.compare(a[1], b[1]);    
            }
            return Integer.compare(a[0], b[0]);
        });

        int[] dp = new int[envelopes.length];
        //Инициализиуем единичками
        //потому что каждый конверт сам по себе — цепочка длины 1.
        Arrays.fill(dp, 1);

        int result = 1;

        for (int i = 0; i < envelopes.length; i++) {
            for (int j = 0; j < i; j++) {
                //Влезает ли j конверт в i конверт
                if (envelopes[j][0] < envelopes[i][0] && envelopes[j][1] < envelopes[i][1]) {
                    //Вычисляем dp[i]
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            //находим цепочку максимальной длины
            result = Math.max(result, dp[i]);
        }

        return result;
    }

Time Complexity = O(n*log(n)) + O(n^2) = O(n^2). O(n*log(n)) - берется из сортировки.
Space Complexity = O(n) - на массив dp + O(log(n)) или O(n) - на сортировку = O(n).

Можно ли улучшить это решение? Да, при помощи бинарного поиска.

Решение при помощи Бинарного поиска

Это решение не очевидное и его я не разбирал для Longest Increasing Subsequence. Но ее также можно решить при помощи бинарного поиска.

Для начала, как и в предыдущем варианте решения, отсортируем конверты по одному из измерений, например по ширине. Затем с помощью бинарного поиска будем искать Longest Increasing Subsequence по высотам уже отсортированных конвертов.
Здесь важно учесть один частный случай: когда ширина совпадает. Если при равной ширине дополнительно отсортировать конверты по высоте по возрастанию, бинарный поиск, не учитывая ширину, может решить, что при большей высоте один конверт помещается в другой, хотя это не так.
Например, для набора [(3, 3), (3, 4)] ширина одинакова, и при сортировке по высоте по возрастанию кажется, что 3 < 4, и наш бинарный поиск будет считать, что конверты можно вложить друг в друга. Чтобы этого избежать, отсортируем немного иначе: по ширине — по возрастанию, а при равной ширине — по убыванию высоты:

Arrays.sort(envelopes, (a, b) -> {
    if (a[0] == b[0]) {
        return Integer.compare(b[1], a[1]);
    } else {
        return Integer.compare(a[0], b[0]);
    }
});

Теперь для отсотрированного массива применим бинарный поиск по высотам.

Для этого введем такое неочевидное состояние: tails[i] - минимальная высота конверта, на который заканчивается цепочка вложенных конвертов с длинной i + 1. Отличие от предыдущего варианта решения, где у нас в dp[i] мы хранили максимальную длину цепочки, которая заканчивается на i-конверте. Тут мы храним не длину, а минимально возможное значение последнего элемента. В качестве значений у нас будут высоты конвертов.

Далее алгоритм следующий. Инициализирум текущую найденную максимальную длинну цепочки вложенных конвертов 0:

int size = 0

Идем циклом по отсортированному массиву конвертов слева направо. На каждом шаге цикла (для каждого конверта), делаем бинарный поиск по массиву tails в пределах: [0..size), для поиска минимального индекса left, такого, что dp[left] >= h.h - высота текущего конверта.
Если такого элемента нет, т.е. высота текущего конверта больше всех текущих хвостов цепочек, то мы можем создать новую более длинную цепочку с нашим текущим конвертом в конце этой цепочки. Для этого увеличим size на единицу:

//вывалились за пределы, такого элемента нет
//наш конверт больше остальных, поэтому есть цепочка на единицу больше с //нашим конвертом
tails[size] = h
if (left == size) {
    size++;
}

Если мы нашли такой элемент, то это значит, что на текущем месте tails[left]>=h и нам нужно обновить это значение, чтобы сохранялось свойство, что в tails[i] мы храним наименьшие конверты, на которые заканчивается цепочка длины i+1.

Все вместе в коде это выглядит так:

public int maxEnvelopes(int[][] envelopes) {
    //Сортируем по ширине конвертов
    //Если ширина одинаковая - по высоте в порядке убывания
    //Иначе подход с бинарным поиском будет считать что если высота больше, то можно конверты вложить, т.к. он не смотрит на ширину
    Arrays.sort(envelopes, (a, b) -> {
        if (a[0] == b[0]) {
            return Integer.compare(b[1], a[1]);
        } else {
            return Integer.compare(a[0], b[0]);
        }
    });

    //tails[i] - минимальная высота конверта, на который заканчивается цепочка вложенных конвертов с длинной i + 1
    int[] tails = new int[envelopes.length];
    int size = 0;

    for (int i = 0; i < envelopes.length; i++) {
        int h = envelopes[i][1];

        int left = 0, right = size;
        while (left < right) {
            int mid = (left + right) >>> 1;
            if (tails[mid] < h) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }

        tails[left] = h;
        if (left == size) {
            size++;
        }
    }

    return size;
}

Такое решение работает на O(n*log(n)) по времени и O(n) по памяти.

Retries

faangmaster — Sat, 25 Oct 2025 12:04:47 +0000

Рассмотрим две компоненты: A и B, которые взаимодействуют через RPC. Например, компонента A вызывает некую функцию/API компоненты B TPS0 раз в секунду. Например, QPS = TPS0 = 1000 вызовов в секунду.

Во время вызовов в продакшене на практике возникают временные (transient) ошибки, которые быстро появляются и исчезают. К ним относятся сетевые сбои, кратковременная перегрузка сервиса, таймауты и т. д.

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

Но какая оптимальная стратегия ретраев?

Ограниченное и неограниченное число ретраев и последствия

Рассмотрим стратегию с ограниченным числом повторных попыток. Если возникает transient-ошибка, мы повторяем вызов, пока он не завершится успешно, но не более n раз. По истечении n попыток прекращаем повторения и возвращаем ошибку.

Очевидное следствие такого подхода — рост нагрузки на сервис B. Давайте рассчитаем это увеличение.

Увеличение нагрузки на компоненту B.

Пусть вначале мы делаем TPS0 запросов в секунду. Пусть вероятность успешного завершения вызова p. Тогда с первого раза успешно завершатся TPS0p вызовов. Для оставшихся TPS0(1-p) запросов мы сделаем ретрай. Т.е. мы уже сделаем TPS0 + TPS0(1-p) запросов после первого ретрая. Аналогично, из них TPS0(1-p)p завершатся успешно, и нам надо будет повторить запрос для TPS0(1-p)(1-p) запросов. Т.е. после второго ретрая мы сделаем

TPS0 + TPS0(1-p) + TPS0(1-p)^2

запросов. И т.д.
После n-ретраев мы сделаем:

TPS0 + TPS0(1-p) + TPS0(1-p)^2 + ... + TPS0(1-p)^n

запросов.
Или:

TPS0(1 + (1-p) + (1-p)^2 + ... + (1-p)^n)

В скобках у нас геометрическая прогрессия. Формула суммы геометрический прогрессии:

Sn = b1(1-q^n)/(1-q)

В нашем случае:

b1 = 1, q = (1-p), n => n+1 (первый вызов + n ретраев).

Тогда

TPS1 = TPS0 (1-(1-p)^(n+1))/(1-(1-p)) = TPS0(1 - (1-p)^(n+1))/p

Давайте посчитаем значения для некоторых p и n:
1) p = 99%, n = 5, TPS0 = 1000 => TPS1 = TPS0 * 1,0101010101. Рост на чуть более чем 1%. TPS1 = 1010.
2) p = 90%, n = 5, TPS0 = 1000 => TPS1 = TPS0 * 1.11111 = 1111. Рост на 11.1%
3) p = 50%, n = 5, TPS0 = 1000 => TPS1 = TPS0 * 1.96875 = 1968. Рост на 96.7%.
4) p = 10%, n = 5, TPS0 = 1000 => TPS1 = TPS0 * 4.68559 = 4685. Рост на 368%.

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

На графике это выглядит вот так:

Зависимость нелинейная: чем хуже работает сервис B, тем быстрее растёт число запросов.

Что будет, если не ограничивать число ретраев?

В нашей формуле:

TPS1 = TPS0(1 - (1-p)^(n+1))/p

При n->бесконечности, (1-p)^(n+1) стремится к нулю. Тогда при n -> бесконечности формула упрощается до:

TPS1 = TPS0/p

При p->0, число запросов возрастает до бесконечности. В то время как при ограчисенном n оно ограниченно. Если изобразить это на одном графике:

Вначале графики очень близки друг к другу. При уменьшении p, число ретраев при неограниченном n растет до бесконечности.

Сколько запросов мы будем делать при p = 0 (сервис B упал)?

В нашей формуле надо устремить p->0 и посчитать предел:

TPS1 = TPS0(1 - (1-p)^(n+1))/p

TPS1(p->0) = lim (TPS0(1 - (1-p)^(n+1))/p), p->0

По правилу Лопиталя возьмем производную числителя и значенателя:

Производная знаменателя = p' = 1
Производная числителя = TPS0 * (0 - (n + 1) * (1 - p) ^ n * (0 - 1)) = TPS0 * (n + 1) * (1 - p) ^ n. p -> 0 => TPS0 * (n + 1)

Тогда предел равен = TPS0 * (n + 1) / 1 = TPS (n + 1)

Полученная формула для p = 0:

TPS1 = TPS0 * (n + 1)

Для n = 5: TPS1 = 1000 * (5 + 1) = 6000.

Этот предел можно посчитать проще. При p = 0, мы сделаем 1000 запросов в самом начале, потом еще 5*1000 попыток. Итого - 6000 запросов.

При n-> бесконечности мы будем делать бесконечное число запросов.

Вероятность успешного завершения вызова при n-ретраях

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

P(хотя бы одна успешная попытка) = 1 - P(вероятность, что все попытки завершаться фейлом).

Вероятность, что первая попытка завершится провалом: 1-p.
Вероятность, что n-попыток завершатся провалом: (1-p)^n.

Тогда вероятность того, что хотя бы одна будет успешной::
P = 1 - (1 - p)^n

Графики вероятности успеха от вероятности успеха одной попытки для разных n выглядит так:

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

Потенциальные проблемы и решения

С одной стороны, чем больше число попыток, тем выше вероятность успешного завершения операции — это помогает скрывать временные (transient) ошибки. С другой стороны, как только у вызываемой компоненты возникают реальные проблемы (p → 0), мы резко увеличиваем на неё нагрузку: чем хуже её состояние, тем сильнее мы её нагружаем. В результате возникает так называемый retry storm: компонента, едва начав работать нестабильно, быстро перегружается и окончательно выходит из строя.
Более того, компоненту B будет сложно поднять, например, мы ее починили, но при подъеме на нее обрушиться трафик в разы больший, чем был изначально.

Что делать, чтобы это предотвратить?

Ограничивайте число ретраев. Как мы видели ранее, если число ретраев не ограничивать, то при малых p, нагрузка растет до бесконечности. При ограниченном n, есть предел числа ретраев: (n + 1) * TPS0
Используйте exponential backoff. Это стратегия, при которой интервал между ретраями постепенно увеличивается. Между первой и второй попыткой пауза небольшая, между второй и третьей — больше, между третьей и четвёртой — ещё больше и т. д. Такой подход снижает нагрузку на проблемную компоненту и даёт ей время восстановиться.
Используйте circuit breaker. Когда компонента явно неисправна, правильнее прекратить все обращения к ней до её восстановления, а не доводить её до окончательной перегрузки и отказа.
Используйте rate limiting/throttling. Чтобы не перегружать компоненту B, ограничивайте максимум запросов в единицу времени.

Смотри также:
Некоторые подходы к архитектуре приложений в Amazon
Обработка ошибок при вызове другой компоненты

Java ThreadLocal Memory Leaks

faangmaster — Wed, 15 Oct 2025 15:22:08 +0000

Утечки памяти (Memory Leaks) в Java — это ситуации, когда объекты или метаданные классов больше не используются приложением, но сборщик мусора не может их удалить. В результате память расходуется неэффективно, что приводит к падению производительности и в крайних случаях — к ошибке OutOfMemoryError.
Существует множество сценариев, которые могут к этому привести. В этой статье я рассмотрю лишь пару примеров, связанных с ThreadLocal в Java.

Конструкция ThreadLocal позволяет хранить данные, которые будут доступны только конкретному thread-у.

Например,

public class Main {
    private static final ThreadLocal<Integer> counter =
            ThreadLocal.withInitial(() -> 0);

    public static void main(String[] args) throws InterruptedException {
        Runnable task = () -> {
            for (int i = 0; i < 3; i++) {
                int current = counter.get();
                counter.set(current + 1);
                System.out.printf("%s -> %d%n",
                        Thread.currentThread().getName(), counter.get());
            }
            counter.remove();
        };

        Thread t1 = new Thread(task, "Worker-1");
        Thread t2 = new Thread(task, "Worker-2");

        t1.start();
        t2.start();
        t1.join();
        t2.join();
    }
}

такой код напечатает:

Worker-2 -> 1
Worker-1 -> 1
Worker-2 -> 2
Worker-2 -> 3
Worker-1 -> 2
Worker-1 -> 3

Может напечатать в разном порядке, но каждый поток (Worker) будет считать независимо от другого начиная с 1. Эти потоки не будут влиять друг на друга через переменную counter.

Как ThreadLocal работает внутри

У всех объектов класса Thread в Java есть поле

ThreadLocal.ThreadLocalMap threadLocals;

Ключ в этой мапе - объект класса ThreadLocal (наша ThreadLocal переменная counter), а значение - значение нашей ThreadLocal переменной для этого потока.

Таким образом каждый поток может менять значения этой переменной не пересекаясь с другими потоками.

ThreadLocal и Thread Pools Java Heap Leaks

В Java можно использовать пулы долгоживущих потоков. Например, создать пул вручную:

ExecutorService workers = Executors.newFixedThreadPool(4);

Либо использовать пул потоков, который предоставляет контейнер приложений (Tomcat, GlassFish, Spring Boot со встроенным Tomcat). В этом случае каждый запрос к вашему приложению обрабатывается в отдельном потоке, при этом потоки не создаются каждый раз с нуля — они переиспользуются из пула.

Т.к. потоки живут долго, то важно правильно использовать ThreadLocal в связке в такими пулами.

Если не вызывать метод remove для ThreadLocal переменных, то это может привести к утечкам памяти.

Например, рассмотрим код:

public class Main {
 private static final ExecutorService workers = Executors.newFixedThreadPool(4);
 private static final ThreadLocal<byte[]> state = new ThreadLocal<>();

 public static void main(String[] args) {
  //Using this thread pool
  for (int i = 0; i < 100_000; i++) {
   workers.submit(() -> {
    state.set(some long payload);
    ......//do some work
   });
  }
  //Doing some other work
  .......
  //Shutdown of thread pool
  workers.shutdown();
 }
}

В данном случае у нас пул из четырёх потоков. В него мы отправляем 100 000 задач. В каждой задаче мы переопределяем значение ThreadLocal-переменной state в контексте одного из этих четырёх потоков. После того как мы закончили отправлять задачи и даже после того, как все они завершились, сами потоки продолжают жить. Соответственно, у каждого потока по-прежнему есть ссылка на значение вашей ThreadLocal-переменной. Даже если дальше в приложении этот ThreadPool или сама переменная уже не используется, потоки всё равно будут ссылаться на очень объёмные объекты, которые не будут собираться GC и будут ухудшать производительность приложения.
Поэтому после завершения каждой задачи нужно вызывать метод remove на ThreadLocal переменной:

public class Main {
 private static final ExecutorService workers = Executors.newFixedThreadPool(4);
 private static final ThreadLocal<byte[]> state = new ThreadLocal<>();

 public static void main(String[] args) {
  //Using this thread pool
  for (int i = 0; i < 100_000; i++) {
   workers.submit(() -> {
    try {
     state.set(some long payload);
     ......//do some work
    } finally {
     state.remove();
    }
   });
  }
  //Doing some other work
  .......
  //Shutdown of thread pool
  workers.shutdown();
 }
}

Добавление:

try {
 .....
} finally {
    state.remove();
}

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

ThreadLocal и Web Containers and Metaspace Memory Leaks

Давайте рассмотрим другой пример:

public final class MyState {
 private final byte[] payload = new byte[10 * 1024 * 1024]; // 10MB для наглядности
  .....
}
.....
Веб-фильтр - выполняется на каждом запросе к контейнеру приложения (например, в Томкате)

@WebFilter("/*")
public class MyFilter implements Filter {
 private static final ThreadLocal<MyState> state = new ThreadLocal<>();

 @Override 
 public void doFilter(ServletRequest req, ServletResponse res, FilterChain chain) throws IOException, ServletException {
  state.set(new MyState()); 
  ....
  chain.doFilter(req, res);
 }
}

В этом кейсе у нас есть веб-приложение, которое работает в контейнере (например, Tomcat). Есть веб-фильтр, который выполняется на каждый входящий запрос. Выполнение происходит в одном из потоков пула, предоставляемого контейнером приложений. В таком случае в качестве значения переменной ThreadLocal используется объект класса MyState.

Более того, в контейнере приложений существуют WebappClassLoader’ы: у каждого приложения внутри контейнера — свой, чтобы классы разных приложений не пересекались.

Если при redeploy приложения не перезапускать весь контейнер (просто положили новый JAR/WAR или нажали в админке redeploy), контейнер создаёт новый WebappClassLoader, а затем удаляет старый. Но т.к. у нас пул поток все еще живет, эти потоки все еще держат ссылки на MyState объекты. Более того, будет жив старый class definition MyClass. А он в свою очередь будет держать старую версию WebappClassLoader. Чем больше таких redeploy мы сделаем, тем больше старых версий WebappClassLoader у нас будет. Это все приводит к утечкам не только в Java Heap, но и в Metaspace. И можно получить

java.lang.OutOfMemoryError: Metaspace

Для фикса нам также нужно добавить:

try {
 .....
} finally {
    state.remove();
}

Jump Game

faangmaster — Tue, 17 Jun 2025 09:03:51 +0000

Задача

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

Нужно вернуть true, если мы можем достичь последний индекс, иначе false.

Пример 1:

nums = [2,3,1,1,4]
Результат: true
Прыжок на 1 шаг с индекса 0 до 1, затем прыжок на 3 шага до последнего индекса.

Пример 2:

nums = [3,2,1,0,4]
Результат: false
Вы всегда окажетесь на индексе 3, независимо от выбора. Максимальная длина прыжка на этом индексе — 0, что делает невозможным достижение последнего индекса.

Ссылка на leetcode: https://leetcode.com/problems/jump-game

Решение

Удобней решать задачу с конца и идти к началу.

Нам нужно достичь последней ячейки в массиве. Обозначим её индекс переменной goal. Очевидно, что если мы уже находимся в ячейке с последним индексом, то можем её достичь. Поэтому начнём обход массива с предпоследней ячейки.

Из ячейки с индексом i = 3 можно прыгнуть максимум на одну ячейку, то есть достичь ячейку с индексом 4. Таким образом, если мы окажемся в ячейке с индексом 3, мы сможем добраться до конца массива.
Поэтому изменим значение переменной goal на 3.

Переместим индекс i на одну ячейку влево.

Из ячейки с индексом i = 2 мы можем прыгнуть максимум на одну ячейку, то есть достичь ячейку с индексом 3. А на предыдущем шаге мы уже выяснили, что, достигнув ячейки с индексом 3, можно добраться до конца массива. Поэтому обновим goal = 2.

Переместим индекс i на одну ячейку влево.

Из ячейки с индексом i = 1 мы можем прыгнуть на 1, 2 или 3 ячейки, то есть достичь любую ячейку с индексом, не превышающим i + nums[i]. Очевидно, что в этом случае мы сможем достичь ячейку, которая в данный момент обозначена как goal (goal = 2).

Теперь мы можем сформулировать ключевое условие для обновления переменной goal: если i + nums[i] >= goal, то мы можем присвоить goal = i. Выражение i + nums[i] обозначает максимальный индекс ячейки, которую можно достичь из позиции i. Если из этой позиции можно допрыгнуть до текущего значения goal, это означает, что начиная с ячейки с индексом i, мы можем добраться до конца массива.

Последние пару итераций алгоритма:

из ячейки с индеком i = 0 мы можем допрыгнуть до ячеек и индексами 1 и 2. Очевидно, что мы сможем допрыгнуть до ячейки goal = 1.

Финальное состояние:

Если goal = 0, это означает, что существует способ добраться до конца массива, начиная с его начала.

Реализация алгоритма тривиальна: проходим по массиву с конца к началу, начиная с предпоследнего элемента. На каждом шаге проверяем: если i + nums[i] >= goal, то обновляем goal = i.

Если в конце выполнения goal == 0, значит, существует способ допрыгать до конца массива.

Time Complexity = O(N)
Space Complexity = O(1)

Реализация

public boolean canJump(int[] nums) {
    int goal = nums.length - 1;
    for (int i = nums.length - 2; i >= 0; i--) {
        if (i + nums[i] >= goal) {
            goal = i;
        }
    }
    return goal == 0;
}

Замощение домино и тримино

faangmaster — Thu, 29 May 2025 22:09:20 +0000

Задача.

У вас есть два вида плиток:

домино — прямоугольник 2 × 1;

тримино — L-образная плитка, состоящая из трёх клеток.

Обе плитки можно свободно поворачивать.

По данному целому n определите, сколькими способами можно замостить доску 2×n этими плитками. Поскольку ответ может быть очень большим, выведите его по модулю 10^9 + 7.

Замощением считается такое покрытие, при котором каждая клетка доски закрыта плиткой. Два замощения считаются разными, если существует пара клеток, соприкасающихся сторонами, которые в одном замощении укрыты одной плиткой, а в другом — двумя разными.

Например, для n = 3 таких замощений 5, как показано на картинке

Ссылка на leetcode: https://leetcode.com/problems/domino-and-tromino-tiling

Решение.

Когда в условии есть фраза "number of ways (число способов)" это верный признак того, что это задача на динамическое программирование.
Эта задача не исключение.

Давайте сначала попробуем руками "пощупать" различные варианты для малых n.

n = 0 -> 0

n = 1 -> 1.

n = 2 -> 2

n = 3 -> 5

Определим состояния

dp[i] — количество способов полностью замостить доску размером 2×i. Полностью означает, что не останется ни одной пустой клетки.

Введём ещё одно, второе, состояние — p[i] — количество способов замостить доску размером 2×i не полностью. Не полностью означает, что заполнены все клетки, кроме одной — последней в верхнем правом углу.
Например,

Соотношения

Выведем формулы для вычисление dp[i] и p[i].

Получить замощение доски 2×i можно 4 способами из предыдущих:

из двух разных частичных состояния p[i-1] методом добавления тримино, которые повернуты по разному:

Добавлением вертикального домино к dp[i-1]:

И наконец, добавление 2 горизонтальным домино к dp[i-2]:

Т.е. dp[i] = dp[i - 1] + dp[i - 2] + 2 * p[i - 1].

Теперь формула для p[i].

Получить p[i] можно 2 способами:

1 - из полностью замощенной доски 2x(i-2) добавив тримино:

2 - Добавив горизонтальное домино к частично замощенной доске p[i-1]:

Т.е. p[i] = p[i - 1] + dp[i - 2].

Реализация

class Solution {
    public int numTilings(int n) {
        if (n == 1) return 1;
        if (n == 2) return 2;

        long dp[] = new long[n + 1];
        long p[] = new long[n + 1];

        dp[0] = 0;
        dp[1] = 1;
        dp[2] = 2;
        p[0] = 0;
        p[1] = 0;
        p[2] = 1;

        int modulo = 1000000007;

        for (int i = 3; i <= n; i++) {
            dp[i] = (dp[i - 1] + dp[i - 2] + 2 * p[i - 1]) % modulo;
            p[i] = (p[i - 1] + dp[i - 2]) % modulo;
        }
        return (int)dp[n];
    }
}

Time Complexity = O(N)
Space Complexity = O(N)

System Design: Ticketmaster

faangmaster — Mon, 26 May 2025 23:40:27 +0000

Задача

Нужно сделать дизайн Ticketmaster. Ticketmaster — это онлайн-платформа, которая позволяет пользователям приобретать билеты на концерты, спортивные мероприятия, театральные постановки и другие live ивенты. Число ежедневных активных пользователей ~100M

Решение

Уточняем требования

Функциональные требования

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

Нефункциональные требования

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

Database Design

Ключевые сущности:
Event- информация о событии
Venue - площадка, где будет проводится мероприятие
Ticket - билеты
Performer - информация об исполнителе

API

Поиск события:

GET /search?keyword={keyword}&location={location}&type={type}&start_date={start_date}&end_date={end_date}.

Возвращает список событий Event[].

keyword - текст поиска,
location - населенный пункт, координаты центра и радиус поиска и т.д.
start_date, end_date - даты события
type - тип события

Просмотр события:

GET /event/eventId

возвращает Event, Venue, Performer, Tickets[]

eventId - id события

Бронирование:

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

API для резервирования:

POST /booking/reserve
header JWT | sessionToken
body:{
ticketIds
}

Для оплаты:

POST /booking/confirm
header JWT | sessionToken
body:{
ticketIds
paymentDetails
}

High Level Design

Опишем более детально основные таблицы:

Из интересного - Ticket должен иметь статус. Статус может быть available, booked, reserved. reserved - означает, что билет зарезервирован, но еще не оплачен. Он может перейти в статус booked, если его оплатили или в available если не оплатили за 5 минут.

High Level Architecture:

API Gateway отвечает за роутинг запросов от клиента к различным бэкенд сервисам, а также за аутентификацию и rate limiting.

Search сервис отвечает за поиск событий по различным критериям. Для начала он может просто делать SQL-запросы в базу.

Event сервис отвечает за чтение и запись событий в базу данных.

Booking сервис отвечает за резервирование и покупку билетов.

В качестве базы данных следует использовать базу с поддержкой ACID-транзакций, чтобы обеспечить строгую консистентность и исключить возможность бронирования одних и тех же билетов несколькими пользователями. Например, это может быть postgresql или MySQL.

Ticket Reserve - in-memory cache, например, Redis/Memcached. Там мы будем хранить билеты, которые зарезервировали, но еще не оплатили. Если их не оплатят в течении TTL, то они будут удалены из кэша.

Статус reserved не сохраняем в основной базе — остаются только available и booked. При выводе доступных билетов для события выбираем записи со статусом available и отсекаем те, что временно находятся в Ticket Reserve.

При бронировании будет вызван API-метод reserve, который добавит билеты в Ticket Reserve (кэш) с TTL 5 минут. Если пользователь не купит билеты за 5 минут - они будут удалены из Ticket Reserve и станут доступными для других пользователей. Если пользователь купит билеты (confirm API), то они также будут удалены из Ticket Reserve и будет выполнена запись в базу с изменение статуса билетов на booked.

Detailed Design/Deep Dives

Для того, чтобы удовлетворить нефункциональные требования по масштабируемости и high availability нам надо ускорить поиск и Event сервисы.

Для этого вместо SQL-запросов в сервисе Search используем ElasticSearch или Amazon OpenSearch. Данные для индексации будем передавать из основной базы по стриму, например через AWS Kinesis или Kafka. При каждом изменении в базе сразу отправляем update в ElasticSearch, чтобы оперативно переиндексировать записи. Это схема назымается CDC(Change Data Capture).

Также добавим кэш, который будет содержать популярные события.

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

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

Для соблюдения честности и порядка, очередь должна храниться в структуре данных типа LinkedHashMap. В качестве ключа — userId, в качестве значения — eventId и timestamp, отражающий момент, когда пользователь встал в очередь. Таким образом, первым в очереди будет пользователь, который подал запрос раньше остальных, и именно он получит приоритет на освободившиеся билеты.
Т.е. можно использовать следующую структуру данных для Waiting Users:
HashMap(key->EventId, value->LinkedHashMap(key->userId, value->timestamp)).

Аналогично для Ticket Reserve:
HashMap(key->EventId, value->LinkedHashMap(key->TicketId, value->timestamp))

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

Если число ивентов в базе станет большим, то можно партиционировать данные по EventId.

Waiting Users - in-memory cache. Там мы будем хранить пользователей, которые ожидают появление билетов, если нет доступных билетов.

36. Valid Sudoku.

faangmaster — Wed, 07 May 2025 00:27:19 +0000

Задача.

Определить, является ли корректным заполнение доски Судоку размером 9×9. Проверять нужно только заполненные клетки по следующим правилам:

Каждая строка должна содержать цифры от 1 до 9 без повторений.
Каждый столбец должен содержать цифры от 1 до 9 без повторений.
Каждый из девяти блоков размером 3×3 должен содержать цифры от 1 до 9 без повторений.

Ссылка на leetcode: https://leetcode.com/problems/valid-sudoku

Решение.

Пример:

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

1) Если клетка пуста, переходим к следующей.

2) Если клетка заполнена, проверяем, что в ней записано число от 1 до 9. В противном случае доска Судоку считается некорректной.

3) Если в этой строке такое число уже встречалось — доска некорректна.

4) Если в этом столбце такое число уже встречалось — доска некорректна.

5) Если в соответствующем 3×3 блоке такое число уже встречалось — доска некорректна.

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

В качестве такого хранилища можно использовать массив булевых значений: если число уже встречалось, соответствующий элемент устанавливается в true, в противном случае — в false.
Далее нам потребуется по 9 элементов для каждой строки, каждого столбца и каждого блока. Итого 9 × 9 + 9 × 9 + 9 × 9 = 81 × 3 = 243 ячейки для хранения статуса.

Например, для хранения чисел, которые мы уже видели в строках мы можем объявить массив:

boolean rows[][] = new boolean[9][9];

Тогда, если мы видели число 7 в строке 5, нам нужно выставить в true, значение в:

rows[4][6] = true

Наглядно, для нашего примера это выглядит так:

Строки у нас проиндексированы от 0 до 8. Числа в них: на позиции 0 число 1, на позиции 1 число 2 и т.д.

Для нашего примера, после обхода всей доски Судоку, значения в rows будут:

Например, в первой строке у нас выставлены в true значения для 3,5,7.

Аналогично, для столбцов:

В первом столбце (с индексом 0), у нас выставлены в true значения для 4,5,6,7,8.

Реализация

Пишем базовый обход всей доски Судоку:

public boolean isValidSudoku(char[][] board) {
    for (int i = 0; i < board.length; i++) {
        for (int j = 0; j < board[i].length; j++) {
        }
    }
    return true;
}

Добавляем тривиальные проверки. Если поле пустое, то переходим к следующей клетке, если не лежит в диапазоне от 1 до 9, то доска не валидна:

public boolean isValidSudoku(char[][] board) {
    for (int i = 0; i < board.length; i++) {
        for (int j = 0; j < board[i].length; j++) {
            if (board[i][j] == '.') {
                continue;
            }
            if (board[i][j] < '1' || board[i][j] > '9') {
                return false;
            }
        }
    }
    return true;
}

Добавляем проверки на то, что мы уже видели или нет такое число в текущей строке и текущем столбце:

public boolean isValidSudoku(char[][] board) {
    boolean rows[][] = new boolean[9][9];
    boolean cols[][] = new boolean[9][9];
    for (int i = 0; i < board.length; i++) {
        for (int j = 0; j < board[i].length; j++) {
            if (board[i][j] == '.') {
                continue;
            }
            if (board[i][j] < '1' || board[i][j] > '9') {
                return false;
            }

            int index = board[i][j] - '0' - 1;
            //уже видели такое число в текущей строке
            if (rows[i][index]) {
                return false;
            }
            rows[i][index] = true;

            //уже видели такое число в текущем столбце
            if (cols[j][index]) {
                return false;
            }
            cols[j][index] = true;

        }
    }
    return true;
}

И наконец, проверку на то, что уже видели в такое число в текущем блоке:

public boolean isValidSudoku(char[][] board) {
    boolean rows[][] = new boolean[9][9];
    boolean cols[][] = new boolean[9][9];
    boolean squares[][][] = new boolean[3][3][9];
    for (int i = 0; i < board.length; i++) {
        for (int j = 0; j < board[i].length; j++) {
            if (board[i][j] == '.') {
                continue;
            }
            if (board[i][j] < '1' || board[i][j] > '9') {
                return false;
            }
            int index = board[i][j] - '0' - 1;
            if (rows[i][index]) {
                return false;
            }
            rows[i][index] = true;
            if (cols[j][index]) {
                return false;
            }
            cols[j][index] = true;

            if (squares[i/3][j/3][index]) {
                return false;
            }
            squares[i/3][j/3][index] = true;
        }
    }
    return true;
}

Time Complexity = O(N*M), где N - число строк, M - число столбцов, т.к. мы обходим всю доску один раз.

Space Complexity = O(N * M) для хранения статуса видели ли мы или еще нет число в строке, столбце и блоке.

Оптимизация по памяти

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

Например, для первой строки в нашем случаем массив boolean можно заменить на одно число типа int:

true заменим на 1, false на 0 на соотвествующей позиции.

Чтобы выставить в числе бит на позиции x в 1 можно выполнить следующую битовую операцию:

value = value | (1 << x);
или
value |= (1 << x);

Чтобы проверить, выставлен ли бит на позиции x в 1, можно выполнить следующую проверку:

if ((value & (1 << x)) > 0) {
  ....
}

Зная это, можно сократить размерность наших массивов:

public boolean isValidSudoku(char[][] board) {
    int rows[] = new int[9];
    int cols[] = new int[9];
    int squares[][] = new int[3][3];
    for (int i = 0; i < board.length; i++) {
        for (int j = 0; j < board[i].length; j++) {
            if (board[i][j] == '.') {
                continue;
            }
            if (board[i][j] < '1' || board[i][j] > '9') {
                return false;
            }
            int index = board[i][j] - '0' - 1;
            int value = 1 << index;
            if ((rows[i] & value) > 0) {
                return false;
            }
            rows[i] |= value;
            if ((cols[j] & value) > 0) {
                return false;
            }
            cols[j] |= value;

            if ((squares[i/3][j/3] & value) > 0) {
                return false;
            }
            squares[i/3][j/3] |= value;
        }
    }
    return true;
}

Число требуемых ячеек памяти сократилось с 243 до 9 + 9 + 9 = 27.

Time Complexity = O(N * M) = O(N^2), т.к. N = M.
Space Complexity = O(N)

Вертикальный обход бинарного дерева. 314. Binary Tree Vertical Order Traversal.

faangmaster — Thu, 01 May 2025 09:28:59 +0000

Задача

Дано бинарное дерево. Нужно обойти дерево вертикально. Т.е. столбец за столбцом. В рамках одного столбца элементы должны быть сверху вниз.

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

Ссылка на leetcode: https://leetcode.com/problems/binary-tree-vertical-order-traversal

Например,

И случай, когда есть элементы 0 и 1, которые на одной строке и в одном столбце:

Решение

Почти все задачи на деревья - это задачи на применение DFS или BFS. В данном случае можно применить BFS и обходить дерево по слоям.

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

Например,

Элемент 9 в столбце 0, элементы 3 и 15 в столбце 1, элемент 20 в столбце 2, элемент 7 в столбце 3.

Как вычислить номер столбца для текущего элемента?

Например, можно указать номером столбца корня дерева - 0.

Тогда для левого ребенка номер столбца будет на единицу меньше, чем у родительской вершины - column - 1, а для правого на единицу больше column + 1.

Аналогично, для оставшихся вершин:

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

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

Реализация

Напишем вначале базовый обход дерева при помощи BFS:

public List<List<Integer>> verticalOrder(TreeNode root) {
    if (root == null) {
        return new ArrayList<>();
    }
    Queue<TreeNode> queue = new ArrayDeque<>();
    queue.offer(root);

    while (!queue.isEmpty()) {
        TreeNode node = queue.poll();

        if (node.left != null) {
            queue.offer(node.left);
        }

        if (node.right != null) {
            queue.offer(node.right);
        }
    }

    List<List<Integer>> result = new ArrayList<>();

    return result;
}

Добавим вычисление текущего столбца (для левого ребенка column - 1, для правого column + 1). Номера столбцов можно поместить в туже очередь queue, но придется помещать пары: вершина и номер столбца. Также можно в отдельную очередь:

public List<List<Integer>> verticalOrder(TreeNode root) {
    if (root == null) {
        return new ArrayList<>();
    }
    Queue<TreeNode> queue = new ArrayDeque<>();
    //Очередь, где храним столбец соответствующей вершины из queue
    Queue<Integer> columnsQueue = new ArrayDeque<>();
    queue.offer(root);
    columnsQueue.offer(0);

    while (!queue.isEmpty()) {
        TreeNode node = queue.poll();
        Integer column = columnsQueue.poll();

        if (node.left != null) {
            queue.offer(node.left);
            columnsQueue.offer(column - 1);
        }

        if (node.right != null) {
            queue.offer(node.right);
            columnsQueue.offer(column + 1);
        }
    }

    List<List<Integer>> result = new ArrayList<>();

    return result;
}

Добавим сохранение результата в HashMap, где ключ - это номер столбца, а значение это список вершин:

public List<List<Integer>> verticalOrder(TreeNode root) {
    if (root == null) {
        return new ArrayList<>();
    }
    Queue<TreeNode> queue = new ArrayDeque<>();
    Queue<Integer> columnsQueue = new ArrayDeque<>();
    queue.offer(root);
    columnsQueue.offer(0);

    Map<Integer, List<Integer>> map = new HashMap<>();

    while (!queue.isEmpty()) {
        TreeNode node = queue.poll();
        Integer column = columnsQueue.poll();

        if (!map.containsKey(column)) {
                map.put(column, new ArrayList<>());
        }
        map.get(column).add(node.val);


        if (node.left != null) {
            queue.offer(node.left);
            columnsQueue.offer(column - 1);
        }

        if (node.right != null) {
            queue.offer(node.right);
            columnsQueue.offer(column + 1);
        }
    }

    List<List<Integer>> result = new ArrayList<>();

    return result;
}

И наконец добавим трекинг максимального и минимального столбца и финальную трансформацию HashMap в список списков:

public List<List<Integer>> verticalOrder(TreeNode root) {
    if (root == null) {
        return new ArrayList<>();
    }
    Queue<TreeNode> queue = new ArrayDeque<>();
    Queue<Integer> columnsQueue = new ArrayDeque<>();
    queue.offer(root);
    columnsQueue.offer(0);

    int minColumn = Integer.MAX_VALUE;
    int maxColumn = Integer.MIN_VALUE;
    Map<Integer, List<Integer>> map = new HashMap<>();

    while (!queue.isEmpty()) {
        TreeNode node = queue.poll();
        Integer column = columnsQueue.poll();

        if (!map.containsKey(column)) {
                map.put(column, new ArrayList<>());
        }
        map.get(column).add(node.val);

        minColumn = Math.min(minColumn, column);
        maxColumn = Math.max(maxColumn, column);

        if (node.left != null) {
            queue.offer(node.left);
            columnsQueue.offer(column - 1);
        }

        if (node.right != null) {
            queue.offer(node.right);
            columnsQueue.offer(column + 1);
        }
    }

    List<List<Integer>> result = new ArrayList<>();

    for (int i = minColumn; i <= maxColumn; i++) {
        result.add(map.get(i));
    }

    return result;
}

Time Complexity - O(N), где N - число вершин в дереве, т.к. мы обходим все вершины в дереве по одному разу.

Space Complexity - O(N), т.к. мы используем дополнительно HashMap, а также Queue для BFS.

Численная проверка решения головоломки про топ 3 из 25 лошадей

faangmaster — Sat, 22 Feb 2025 16:02:43 +0000

Задача следующая:

Есть 25 лошадей. На ипподроме 5 дорожек. Надо определить 3 самые быстрые лошади за минимальное число заездов. Время замерять нельзя. Мы только знаем, кто в каком порядке финиширует. Можно считать, что время за которое каждая лошадь пробегает дистанцию не меняется от заезда к заезду.

Решение

Это можно сделать за 7 забегов.
Разбиваем на 5 групп по пять лошадей. Проводим 5 забегов (по одному на группу).
Из победителей в каждой группе формируем шестой забег. Победитель шестого забега - топ 1.
Формируем седьмой забег из:
1) Второго и третьего места из шестого забега.
2) Второго и третьего места из группы (группа в числе изначальных 5 забегов), из которой победитель шестого забега.
3) Второго места из группы (группа в числе изначальных 5 забегов), из которой лошадь, занявшая второе место в шестом забеге.

Победитель седьмего забега - топ 2, второе место в седьмом забеге - топ 3.

Код проверки

import java.util.*;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

public class Main {
    public static void main(String[] args) {
        boolean debugMode = false;
        int numberOfSimulations = 1000_000;

        for (int simulation = 0; simulation < numberOfSimulations; simulation++) {

            if (simulation % 100000 == 0) {
                System.out.println("Simulation number " + simulation);
            }

            simulate(debugMode);
        }
        System.out.println("No mismatches found, all " + numberOfSimulations + " passed!");
    }

    private static void simulate(boolean debugMode) {
        List<Horse> horses = Horses.init();
        if (debugMode) {
            System.out.println("Initial horses:" + horses);
        }
        List<HorseRace> horseRaces = Horses.splitIntoFiveGroups(horses);
        if (debugMode) {
            System.out.println("Five Groups: " + horseRaces);
        }
        horseRaces.forEach(HorseRace::race);
        if (debugMode) {
            System.out.println("Five Groups After Five Races: " + horseRaces);
        }
        HorseRace sixRace = Horses.getWinnersToFormSixRace(horseRaces);
        if (debugMode) {
            System.out.println("Six Race Before: " + sixRace);
        }
        sixRace.race();
        if (debugMode) {
            System.out.println("Six Race After: " + sixRace);
        }
        Map<Horse, HorseRace> horsesToInitialFiveRaces = Horses.indexHorsesToInitialFiveRaces(horseRaces);
        HorseRace sevenRace = new HorseRace();
        sevenRace.add(sixRace.getSecond());
        sevenRace.add(sixRace.getThird());
        HorseRace raceOfWinnerOfSixRace = horsesToInitialFiveRaces.get(sixRace.getWinner());
        sevenRace.add(raceOfWinnerOfSixRace.getSecond());
        sevenRace.add(raceOfWinnerOfSixRace.getThird());
        HorseRace raceOfSecondOfSixRace = horsesToInitialFiveRaces.get(sixRace.getSecond());
        sevenRace.add(raceOfSecondOfSixRace.getSecond());

        if (debugMode) {
            System.out.println("Seven Race Before: " + sevenRace);
        }
        sevenRace.race();
        if (debugMode) {
            System.out.println("Seven Race After: " + sevenRace);
        }

        List<Horse> identifiedTopThreeBySevenRaces = new ArrayList<>();
        identifiedTopThreeBySevenRaces.add(sixRace.getWinner());
        identifiedTopThreeBySevenRaces.add(sevenRace.getWinner());
        identifiedTopThreeBySevenRaces.add(sevenRace.getSecond());
        List<Horse> expectedTopThree = Horses.copySortAndGetTopThree(horses);
        if (debugMode) {
            System.out.println("Expected top three horses:" + expectedTopThree);
        }
        if (debugMode) {
            System.out.println("identifiedTopThreeBySevenRaces: " + identifiedTopThreeBySevenRaces);
        }

        if (!identifiedTopThreeBySevenRaces.equals(expectedTopThree)) {
            System.out.println("Mismatch found!");
            System.out.println("Expected top three horses:" + expectedTopThree);
            System.out.println("identifiedTopThreeBySevenRaces: " + identifiedTopThreeBySevenRaces);
            throw new RuntimeException("Mismatch found!");
        }
    }
}

class Horses {
    public static List<Horse> init() {
        List<Integer> raceTimes = new ArrayList<>(
                IntStream.range(0, 25)
                        .map(index -> index * 100)
                        .boxed()
                        .toList());
        Collections.shuffle(raceTimes);
        return IntStream.range(0, 25)
                .mapToObj(index -> new Horse(index, raceTimes.get(index)))
                .collect(Collectors.toList());
    }
    public static List<Horse> copySortAndGetTopThree(List<Horse> horses) {
        return horses.stream()
                .map(Horse::new)
                .sorted()
                .limit(3)
                .toList();
    }

    public static List<HorseRace> splitIntoFiveGroups(List<Horse> horses) {
        List<HorseRace> horseRaces = new ArrayList<>();
        for (int i = 0; i < horses.size(); i += 5) {
            HorseRace race = new HorseRace();
            for (int j = i; j < i + 5; j++) {
                race.add(horses.get(j));
            }
            horseRaces.add(race);
        }
        return horseRaces;
    }

    public static HorseRace getWinnersToFormSixRace(List<HorseRace> horseRaces) {
        return new HorseRace(
                horseRaces.stream()
                        .map(HorseRace::getWinner)
                        .collect(Collectors.toList()));
    }

    public static Map<Horse, HorseRace> indexHorsesToInitialFiveRaces(List<HorseRace> horseRaces) {
        Map<Horse, HorseRace> index = new HashMap<>();
        for (HorseRace horseRace : horseRaces) {
            for (Horse horse : horseRace.getHorses()) {
                index.put(horse, horseRace);
            }
        }
        return index;
    }
}

class Horse implements Comparable<Horse> {
    private final int index;
    private final int raceTime;

    public Horse(int index, int raceTime) {
        this.index = index;
        this.raceTime = raceTime;
    }

    public Horse(Horse horse) {
        this.index = horse.index;
        this.raceTime = horse.raceTime;
    }

    @Override
    public String toString() {
        return "Horse{" +
                "index=" + index +
                ", raceTime=" + raceTime +
                '}';
    }

    @Override
    public int compareTo(Horse horse) {
        return this.raceTime - horse.raceTime;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Horse horse = (Horse) o;
        return index == horse.index && raceTime == horse.raceTime;
    }

    @Override
    public int hashCode() {
        return Objects.hash(index, raceTime);
    }
}

class HorseRace {
    private final List<Horse> horses;

    public HorseRace() {
        this.horses = new ArrayList<>();
    }

    public HorseRace(List<Horse> horses) {
        this.horses = horses;
    }

    public void add(Horse horse) {
        if (this.horses.size() >= 5) {
            throw new IllegalArgumentException("Number of horses in a race is limited by 5");
        }
        this.horses.add(horse);
    }

    public List<Horse> getHorses() {
        return this.horses;
    }

    public void race() {
        Collections.sort(horses);
    }

    public Horse getWinner() {
        return horses.getFirst();
    }

    public Horse getSecond() {
        return horses.get(1);
    }

    public Horse getThird() {
        return horses.get(2);
    }

    @Override
    public String toString() {
        return "HorseRace{" +
                "horses=" + horses +
                '}';
    }
}

Второй, немного измененный, вариант, где время забега не целое уникальное число, а случайное вещественное число:

import java.util.*;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

public class Main {
    public static void main(String[] args) {
        boolean debugMode = false;
        int numberOfSimulations = 1000_000;

        for (int simulation = 0; simulation < numberOfSimulations; simulation++) {

            if (simulation % 100000 == 0) {
                System.out.println("Simulation number " + simulation);
            }

            simulate(debugMode);
        }
        System.out.println("No mismatches found, all " + numberOfSimulations + " passed!");
    }

    private static void simulate(boolean debugMode) {
        List<Horse> horses = Horses.init();
        if (debugMode) {
            System.out.println("Initial horses:" + horses);
        }
        List<HorseRace> horseRaces = Horses.splitIntoFiveGroups(horses);
        if (debugMode) {
            System.out.println("Five Groups: " + horseRaces);
        }
        horseRaces.forEach(HorseRace::race);
        if (debugMode) {
            System.out.println("Five Groups After Five Races: " + horseRaces);
        }
        HorseRace sixRace = Horses.getWinnersToFormSixRace(horseRaces);
        if (debugMode) {
            System.out.println("Six Race Before: " + sixRace);
        }
        sixRace.race();
        if (debugMode) {
            System.out.println("Six Race After: " + sixRace);
        }
        Map<Horse, HorseRace> horsesToInitialFiveRaces = Horses.indexHorsesToInitialFiveRaces(horseRaces);
        HorseRace sevenRace = new HorseRace();
        sevenRace.add(sixRace.getSecond());
        sevenRace.add(sixRace.getThird());
        HorseRace raceOfWinnerOfSixRace = horsesToInitialFiveRaces.get(sixRace.getWinner());
        sevenRace.add(raceOfWinnerOfSixRace.getSecond());
        sevenRace.add(raceOfWinnerOfSixRace.getThird());
        HorseRace raceOfSecondOfSixRace = horsesToInitialFiveRaces.get(sixRace.getSecond());
        sevenRace.add(raceOfSecondOfSixRace.getSecond());

        if (debugMode) {
            System.out.println("Seven Race Before: " + sevenRace);
        }
        sevenRace.race();
        if (debugMode) {
            System.out.println("Seven Race After: " + sevenRace);
        }

        List<Horse> identifiedTopThreeBySevenRaces = new ArrayList<>();
        identifiedTopThreeBySevenRaces.add(sixRace.getWinner());
        identifiedTopThreeBySevenRaces.add(sevenRace.getWinner());
        identifiedTopThreeBySevenRaces.add(sevenRace.getSecond());
        List<Horse> expectedTopThree = Horses.copySortAndGetTopThree(horses);
        if (debugMode) {
            System.out.println("Expected top three horses:" + expectedTopThree);
        }
        if (debugMode) {
            System.out.println("identifiedTopThreeBySevenRaces: " + identifiedTopThreeBySevenRaces);
        }

        if (!identifiedTopThreeBySevenRaces.equals(expectedTopThree)) {
            System.out.println("Mismatch found!");
            System.out.println("Expected top three horses:" + expectedTopThree);
            System.out.println("identifiedTopThreeBySevenRaces: " + identifiedTopThreeBySevenRaces);
            throw new RuntimeException("Mismatch found!");
        }
    }
}

class Horses {
    public static List<Horse> init() {
        Random random = new Random();
        return IntStream.range(0, 25)
                .mapToObj(index -> new Horse(index, random.nextDouble()))
                .collect(Collectors.toList());
    }
    public static List<Horse> copySortAndGetTopThree(List<Horse> horses) {
        return horses.stream()
                .map(Horse::new)
                .sorted()
                .limit(3)
                .toList();
    }

    public static List<HorseRace> splitIntoFiveGroups(List<Horse> horses) {
        List<HorseRace> horseRaces = new ArrayList<>();
        for (int i = 0; i < horses.size(); i += 5) {
            HorseRace race = new HorseRace();
            for (int j = i; j < i + 5; j++) {
                race.add(horses.get(j));
            }
            horseRaces.add(race);
        }
        return horseRaces;
    }

    public static HorseRace getWinnersToFormSixRace(List<HorseRace> horseRaces) {
        return new HorseRace(
                horseRaces.stream()
                        .map(HorseRace::getWinner)
                        .collect(Collectors.toList()));
    }

    public static Map<Horse, HorseRace> indexHorsesToInitialFiveRaces(List<HorseRace> horseRaces) {
        Map<Horse, HorseRace> index = new HashMap<>();
        for (HorseRace horseRace : horseRaces) {
            for (Horse horse : horseRace.getHorses()) {
                index.put(horse, horseRace);
            }
        }
        return index;
    }
}

class Horse implements Comparable<Horse> {
    private final int index;
    private final double raceTime;

    public Horse(int index, double raceTime) {
        this.index = index;
        this.raceTime = raceTime;
    }

    public Horse(Horse horse) {
        this.index = horse.index;
        this.raceTime = horse.raceTime;
    }

    @Override
    public String toString() {
        return "Horse{" +
                "index=" + index +
                ", raceTime=" + raceTime +
                '}';
    }

    @Override
    public int compareTo(Horse horse) {
        return Double.compare(this.raceTime, horse.raceTime);
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Horse horse = (Horse) o;
        return index == horse.index;
    }

    @Override
    public int hashCode() {
        return Objects.hash(index);
    }
}

class HorseRace {
    private final List<Horse> horses;

    public HorseRace() {
        this.horses = new ArrayList<>();
    }

    public HorseRace(List<Horse> horses) {
        this.horses = horses;
    }

    public void add(Horse horse) {
        if (this.horses.size() >= 5) {
            throw new IllegalArgumentException("Number of horses in a race is limited by 5");
        }
        this.horses.add(horse);
    }

    public List<Horse> getHorses() {
        return this.horses;
    }

    public void race() {
        Collections.sort(horses);
    }

    public Horse getWinner() {
        return horses.getFirst();
    }

    public Horse getSecond() {
        return horses.get(1);
    }

    public Horse getThird() {
        return horses.get(2);
    }

    @Override
    public String toString() {
        return "HorseRace{" +
                "horses=" + horses +
                '}';
    }
}

Задача с собеседования в Google: Максимальный Квадрат

faangmaster — Fri, 21 Feb 2025 09:35:08 +0000

Задача

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

Пример:

{"1","0","1","0","0"},
{"1","0","1","1","1"},
{"1","1","1","1","1"},
{"1","0","0","1","0"}

Ответ: 4. Тут есть несколько квадратов со стороной 1 и 2 клетки. Есть два квадрата со стороной 2 клетки. Т.е. размер стороны квадрата, максимального размера - 2. Площадь максимального квадрата - 4.

Ссылка на leetcode: https://leetcode.com/problems/maximal-square/description/

Решение.

Достаточно часто, когда в условии есть слова - найти максимальный, минимальный, оптимальный, найти число способов - это индикатор того, что задача на динамическое программирование.
Существует два подхода к решению задач на динамическое программирование:
top-down (recursion + memoization, от решения общей задачи к частным) и bottom-up (итеративный подход, от частных подзадач к решению общей задачи).

В данном случае рассмотрим bottom-up подход.
Для решения задачи bottom-up подходом нам требуется проделать 3 операции:
1) Определить состояние/решение подзадачи. Обычно, это одномерный массив dp[i] или двумерный массив dp[i][j], который определяет решение подзадачи. Например, в задаче про числа Фибоначчи, dp[i] - i-ое число Фибоначчи.
2) Определить связь решения более общей задачи с решениями подзадач. Это какая-то формула, которая связывает dp[i] с dp[i-1], dp[i-2], ... Или в двумерном случае dp[i][j] с dp[i-1][j], dp[i][j-1], dp[i-1][j-1], .... Обычно, это какая-то сумма, разность, максимум или минимум. И очень часто это еще + 1 к чему-то. В задаче, про числа Фибоначчи - это dp[i] = dp[i-1] + dp[i-2].
3) Определить базовый случай - решение тривиальной подзадачи. Обычно, это задать значение dp[0] или, dp[0][0], dp[0][1], dp[1][0] и т.д. Обычно, их надо инициализировать нулями или единицами.

Подзадачи/состояние

Одним из типичных вариантов для задания подзадачи/состояния является - решение задачи, если бы она заканчивалась в текущей точке. Например, я записывал видео решения задачи на динамическое программирование - наибольшая возрастающая подпоследовательность: https://www.youtube.com/watch?v=jSx2npfHBt0. Там случай был одномерный и dp[i] - означал размер возрастающей подпоследовательности, если бы она заканчивалась в элементе исходного массива с индексом i.
В данном случае, мы имеем дело с двумерным случаем. Поэтому нам нужно определить, что такое dp[i][j]. По аналогии с упомянутой задачей, определим dp[i][j] - решение задачи (размер квадрата), если бы он заканчивался в точке с координатами i, j. Что в данном случае означает - заканчиваться для квадрата? Это значит, что в точке i, j - правый нижний угол квадрата. Т.е. dp[i][j] - размер стороны квадрата, если бы у него был правый нижний угол в ячейке с координатами i, j.
Тогда максимум из всех dp[i][j] - будет размер наибольшего квадрата и решением задачи.

Связь задачи с подзадачами

Хорошо, мы определили, что такое dp[i][j]. Теперь, нужно определить связь между решениями более общей задачи с решениями подзадач.
Первое замечание - если в клетке у нас нолик, значит квадрат тут не может заканчиваться, поэтому dp[i][j] = 0, если arr[i][j] == "0".
Если там единица, то может. Но какого размера он будет? для этого нам надо посмотреть на соседние клетки. Причем только по диагонали влево, по горизонтали влево и по вертикали вверх. Смотреть на клетки, которые справа или снизу не надо, т.к. по определению dp[i][j] - наш квадрат должен заканчиваться в клетке (i, j).
Хорошо, а что если в одной из трех соседних клеток нолик? тогда, очевидно, квадрат не может продолжаться влево и вверх. Т.е. он будет размера 1.
Например, для клетки выделенной красным цветом, три соседние клетки выделенны зеленным. Среди них есть нолики, поэтому dp[i][j] = 1.

Давайте посмотрим другую клетку:

В трех соседних - все единички и для них значения dp - тоже равно 1. Тогда для клетки, выделенной красным цветом ответ будет 2.

Давайте посмотрим еще пример:

Слева исходный массив, справа - dp(размер стороны квадрата, который заканчивается в клетке i, j. Т.е. размер стороны квадрата, у которого правый нижний угол в клетке i, j). В клетках, соседних с красной, значение dp: 2, 1, 1. Правильным ответом, очевидно, в данном случае будет 2.
Еще одно соображение - размер квадрата, который заканчивается в клетке dp[i][j] на единицу больше, чем размер смежных квадратов. Но не всех или не всегда.
Правильным соотношением будет dp[i][j] = min(dp трех смежных клеток) + 1. Минимум нужен, т.к. квадрат нам нужно продлить во все три стороны и по какой-то из этих сторон он закончится. Это может произойти одновременно, но по одному из направлений он может оборваться раньше, т.к. встретится нолик.

Т.е. dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1

Базовый кейс

Для клеток, которые находятся на границе нашей матрицы, смежными будут клетки за границами массива. Для них нужно задать значения dp[i][j] как ноль.

Реализация в коде

    public int maximalSquare(char[][] matrix) {
        // Искомый, максмимальный размер стороны квадрата
        int maxSide = 0;
        //dp[i][j] - максимальный размер стороны квадрата, который заканчивается в клетке i, j
        int dp[][] = new int[matrix.length][matrix[0].length];
        //Цикл по всем элементам матрицы
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                if (matrix[i][j] == '1') {
                    //вычисление dp[i][j]
                    //Обновление maxSide  
                }
            }
        }
        //Нужно вернуть площадь квадрата
        return maxSide * maxSide;
    }

Дополним вычислением dp[i][j] и обновлением maxSide:

public int maximalSquare(char[][] matrix) {
    int maxSide = 0;
    int dp[][] = new int[matrix.length][matrix[0].length];
    for (int i = 0; i < matrix.length; i++) {
        for (int j = 0; j < matrix[0].length; j++) {
            if (matrix[i][j] == '1') {
                int left = ..
                int up = ...
                int diagonal = ...
                dp[i][j] = Math.min(Math.min(left, up), diagonal) + 1;
                maxSide = Math.max(maxSide, dp[i][j]);
            }
        }
    }
    return maxSide * maxSide;
}

Дополним вычислением значений left, up, diagonal с учетом того, что они могут быть за пределами массива:

public int maximalSquare(char[][] matrix) {
    int maxSide = 0;
    int dp[][] = new int[matrix.length][matrix[0].length];
    for (int i = 0; i < matrix.length; i++) {
        for (int j = 0; j < matrix[0].length; j++) {
            if (matrix[i][j] == '1') {
                int left = j - 1 >= 0 ? dp[i][j - 1] : 0;
                int up = i - 1 >= 0 ? dp[i - 1][j] : 0;
                int diagonal = i - 1 >= 0 && j - 1 >= 0 ? dp[i - 1][j - 1] : 0;
                dp[i][j] = Math.min(Math.min(left, up), diagonal) + 1;
                maxSide = Math.max(maxSide, dp[i][j]);
            }
        }
    }
    return maxSide * maxSide;
}

Time Complexity = O(N * M), где N - число строк в массиве. M - число столбцов. Нам нужно обойти все элементы массива, поэтому алгоритмическая сложность O(NM).
Space Complexity = O(N * M), т.к. нам надо хранить еще dp, который имеет размер такой же, как и исходный массив.

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

public int maximalSquare(char[][] matrix) {
    int maxSide = 0;
    int dp[][] = new int[matrix.length + 1][matrix[0].length + 1];
    for (int i = 0; i < matrix.length; i++) {
        for (int j = 0; j < matrix[0].length; j++) {
            if (matrix[i][j] == '1') {
                int left = dp[i + 1][j];
                int up = dp[i][j + 1];
                int diagonal = dp[i][j];
                dp[i + 1][j + 1] = Math.min(Math.min(left, up), diagonal) + 1;
                maxSide = Math.max(maxSide, dp[i + 1][j + 1]);
            }
        }
    }
    return maxSide * maxSide;
}

Можно ли улучшить данное решение? Нам в любом случае придется обходить все элементы массива, поэтому алгоритмическую сложность не улучшить. А вот сложность по памяти можно улучшить, т.к. для вычисления dp[i][j] нам нужна не вся матрица dp, а только 3 смежных элемента, которые находятся в двух соседних строках. Поэтому сложность по памяти можно улучшить, но я оставлю эту оптимизацию за рамками этого разбора.

Простая задача с собеседования в Google: Merge Strings Alternately

faangmaster — Tue, 31 Dec 2024 12:59:06 +0000

Задача.

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

Примеры:

Для строк "abc" и "pqk" результирующая строка будет "apbqck".
Для строк "abc" и "p" результирующая строка будет "apbc".

Ссылка на leetcode: https://leetcode.com/problems/merge-strings-alternately

Решение

Когда в условии задачи фигурируют две строки, два массива, два списка, то наиболее вероятным решением будет применения Two Pointers. Тем более если в условии задачи есть слово "смержить".
Еще одним соображением может быть применение части из алгоритма сортировки Merge Sort. Смотри тут список алгоритмов, которые нужно знать наизусть для собеседования по алгоритмам: Шпаргалка по основным алгоритмам для алгоритмического собеседования.
Можно подумать как адаптировать метод merge из алгоритма Merge Sort:

private static void merge(int[] arr, int left, int mid, int right, int buffer[]) {
    int i = left;
    int j = mid + 1;
    int k = 0;
    while (i <= mid && j <= right) {
        if (arr[i] > arr[j]) {
            buffer[k++] = arr[j++];
        } else {
            buffer[k++] = arr[i++];
        }
    }
    while (i <= mid) {
        buffer[k++] = arr[i++];
    }
    while (j <= right) {
        buffer[k++] = arr[j++];
    }
    k = 0;
    for (i = left; i <= right; i++) {
        arr[i] = buffer[k++];
    }
}

Этот метод также использует подход Two Pointers.

Как мы можем адаптировать этот метод для нашей задачи?

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

Давайте реализуем этот подход в коде:

    public String mergeAlternately(String word1, String word2) {
        StringBuilder sb = new StringBuilder();
        //Инициализируем два указателя
        int i = 0;
        int j = 0;
        while (i < word1.length() && j < word2.length()) {
            //Копируем символ из первой строки и увеличиваем первый индекс
            sb.append(word1.charAt(i++));
            //Копируем символ из второй строки и увеличиваем второй индекс
            sb.append(word2.charAt(j++));
        }
        //Копируем оставшився хвост из большей строки, если он есть
        while (i < word1.length()) {
            sb.append(word1.charAt(i++));
        }
        while (j < word2.length()) {
            sb.append(word2.charAt(j++));
        }
        return sb.toString();
    }

Временная сложность: O(N+M), где N - длинна первой строки, M - длинна второй строки.
Сложность по памяти: O(1), если не считать память на результирующую строку. Если считать, то O(N+M).

Можно ли улучшить данное решение?

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

Код решения:

    public String mergeAlternately(String word1, String word2) {
        StringBuilder sb = new StringBuilder();
        //Инициализируем один индекс для итерации по двум строкам
        int i = 0;
        //Заменяем условие в цикле с and на or, чтобы объединить все три цикла в один
        while (i < word1.length() || i < word2.length()) {
            if (i < word1.length()) {
                sb.append(word1.charAt(i));
            }
            if (i < word2.length()) {
                sb.append(word2.charAt(i));
            }
            i++;
        }
        return sb.toString();
    }

Давайте посмотрим, как это будет работать шаг за шагом на примере двух строк: "abc" и "pq".

Инициализируем i = 0:

i меньше длинны обеих строк, потому копируем первый символ из первой строки и первый символ из второй строки, и увеличиваем i на единицу:

i меньше длинны обеих строк, потому копируем вторые символы из первой и второй строк и увеличиваем i на единицу:

Теперь i меньше длинны первой строки, поэтому копируем третий символ из первой строки. Но i равно длинне второй строки, поэтому не ничего не делаем со второй строкой:

После этого i = 3, что больше или равно длинны обеих строк. Поэтому на этом работа алгоритма завершается.