Медиана двух отсортированных массивов

Частота встречи задач на собеседованиях за последние шесть месяцев:
Amazon — 32, Apple — 23, Google — 19, Goldman Sachs — 18, Adobe — 16.

Имея два отсортированных массива nums1 и nums2 размера m и n соответственно, вернуть медиану этих массивов. Общая сложность времени выполнения должна быть O(log (m+n)).

Примеры:
Ввод: nums1 = [1,3], nums2 = [2]
Вывод: 2.00000
Объяснение: объединенный массив = [1,2,3], а медиана 2.

Ввод: nums1 = [1,2], nums2 = [3,4]
Вывод: 2.50000
Объяснение: объединенный массив = [1,2,3,4], а медиана (2 + 3) / 2 = 2.5.

Решение задачи на Java

Весовая сумма списка

Частота встречи задач на собеседованиях за последние шесть месяцев:
Facebook* — 88, LinkedIn — 36, Amazon — 5

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

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

Примеры:
Ввод: nestedList = [[1,1],2,[1,1]]
Вывод: 10
Объяснение: четыре единицы имеют глубину 2, одна двойка at имеет глубину 1. 1*2 + 1*2 + 2*1 + 1*2 + 1*2 = 10.

Ввод: nestedList = [0]
Вывод: 0

Решение задачи

* — организация, признанная экстремистской на территории РФ.

Поиск мажоритарного элемента

Частота встречи задач на собеседованиях за последние шесть месяцев:
Amazon — 10, Google — 8, Apple — 8, Microsoft — 6, Bloomberg — 6, Adobe — 6

Условие задачи:
Дан массив nums размера n. Требуется вернуть мажоритарный элемент.

Мажоритарный элемент - это элемент, который появляется более n / 2 раз. Вы можете быть уверены, что мажоритарный элемент всегда существует в массиве.

Примеры:
Ввод: nums = [4,2,4]
Вывод: 4

Ввод: nums = [8, 8, 6, 6, 6, 8, 8]
Вывод: 8

Решение задачи

Число-палиндром

Условие задачи:
Получив целое число x, вернуть true, если x является палиндромом. Целое число является палиндромом, если оно читается одинаково как в прямом, так и в обратном порядке.

Примеры:
Ввод: х = 121
Вывод: true
Объяснение: 121 читается как 121 слева направо и справа налево.

Ввод: х = -121
Вывод: false
Объяснение: Слева направо это -121. Справа налево получается 121-. Следовательно, это не палиндром.

Ввод: х = 10
Вывод: false

Решение задачи

Единственный элемент

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

Вы должны реализовать решение с линейной сложностью и использовать только постоянное дополнительное пространство.

Пример:
Ввод: nums = [8, 8, 6]
Вывод: 6

Ввод: nums = [4, 1, 2, 1, 2]
Вывод: 4

Решение задачи

Контейнер с наибольшим количеством воды

Вам дан целочисленный массив height длины n. Нарисовано n вертикальных линий, две конечные точки i-й линии равны (i, 0) и (i, height[i]). Найдите две линии, которые вместе с осью абсцисс образуют контейнер, содержащий наибольшее количество воды. Верните максимальное количество воды, которое может храниться в контейнере. Обратите внимание, что вы не можете наклонять контейнер.

Пример 1 (картинка):
Ввод: height = [1,8,6,2,5,4,8,3,7]
Вывод: 49
Объяснение: Вышеуказанные вертикальные линии представлены массивом [1,8,6,2,5,4,8,3,7]. В этом случае максимальная площадь воды (синяя секция), которую может содержать контейнер, составляет 49.

Пример 2:
Ввод: height = [1,1]
Вывод: 1

Решение задачи

Добавление строк

Условие задачи:
Даны два неотрицательных целых числа, str1 и str2, представленные в виде строки. Требуется вернуть сумму str1 и str2 в виде строки.

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

Примеры:
Ввод: str1 = "11", str2 = "123"
Вывод: 134

Ввод: str1 = "456", str2 = "77"
Вывод: 533

Решение задачи

3Sum Closest

Имея целочисленный массив nums длины n и целочисленную target, найдите три целых числа в nums, сумма которых ближе всего к target. Верните сумму трех целых чисел. Каждый вход будет иметь ровно одно решение.

Ввод: nums = [-1,2,1,-4], target = 1 Вывод: 2
Сумма, ближайшая к цели, равна 2. (-1 + 2 + 1 = 2).

Ввод: nums = [0,0,0], target = 1
Вывод: 0

Решение задачи

Числа Фибоначчи

Условие задачи:
Числа Фибоначчи, обычно обозначаемые F(n), образуют последовательность, называемую последовательностью Фибоначчи, так что каждое число является суммой двух предыдущих, начиная с 0 и 1.

F(0) = 0, F(1) = 1
F(n) = F(n - 1) + F(n - 2), for n > 1.

Вам дано число n. Требуется найти F(n).

Примеры:
Ввод: n = 2
Вывод: 1
Объяснение: F(2) = F(1) + F(0) = 1 + 0 = 1.

Ввод: n = 3
Вывод: 2

Решение задачи

Буквенные комбинации номера телефона

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

Примеры:
Ввод: nums = "23"
Вывод: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]

Ввод: digits = ""
Вывод: []

Ввод: digits = "2"
Вывод: ["a","b","c"]

Решение задачи

Создание скобок

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

Ввод: n = 3
Вывод: ["((()))","(()())","(())()","()(())","()()()"]

Ввод: n = 1
Вывод: ["()"]

Решение задачи

Допустимая анаграмма

Условие задачи:
Даны две строки s и t, верните true, если t является анаграммой s и false в противном случае.

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

Примеры:
Ввод: s = "anagram", t = "nagaram"
Вывод: true
Ввод: s = "rat", t = "car"
Вывод: false

Решение задачи

Самая длинная палиндромная подстрока

Условие задачи:
Дана строка s. Требуется вернуть самую длинную палиндромную подстроку в s.

Примеры:
Ввод: s = "babad"
Вывод: "bab"
Объяснение: "aba" также является правильным ответом.

Ввод: s = "cbbd"
Вывод: "bb"

Решение задачи

Поиск дубликата

Условие задачи:
Дан массив целых чисел nums, содержащий n + 1 целых чисел, где каждое целое число находится в диапазоне [1, n] включительно.

В nums есть только одно повторяющееся число, верните это повторяющееся число.

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

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

Примеры:
Ввод: nums = [1,3,4,2,2]
Вывод: 2

Ввод: nums = [3,1,3,4,2]
Вывод: 3

Решение задачи

Уникальное количество вхождений

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

Пример:
Ввод: arr = [1,2,2,1,1,3]
Вывод: true
Объяснение: Значение 1 имеет 3 вхождения, 2 имеет 2, а 3 имеет 1. Никакие два значения не имеют одинакового количества вхождений.

Ввод: arr = [1,2]
Вывод: false

Решение задачи

Улавливание дождевой воды

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

Ввод: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Вывод: 6
Объяснение: Вышеприведенная карта высот (черный участок) представлена массивом [0,1,0,2,1,0,1,3,2,1,2,1]. В этом случае задерживается 6 единиц дождевой воды (синяя секция).

Пример 2:
Ввод: height = [4,2,0,3,2,5]
Вывод: 9

Решение задачи

Сумма минимумов подмассива

Условие задачи:
Дан массив целых чисел arr. Требуется найти сумму min(b), где b колеблется по каждому (непрерывному) подмассиву arr. Поскольку ответ может быть большим, верните ответ по модулю 10^9 + 7.

Пример:
Ввод: arr = [3,1,2,4]
Вывод: 17
Объяснение:
Подмассивы [3], [1], [2], [4], [3,1], [1,2], [2,4], [3,1,2], [1,2,4], [3,1,2,4].
Минимумы 3, 1, 2, 4, 1, 1, 2, 1, 1, 1.
Их сумма равна 17.

Ввод: arr = [11,81,94,43,3]
Вывод: 444

Решение задачи

Приветствую всех, на связи админ! Какие у вас будут пожелания по доработке контента на нашем канале? 🤔🤔🤔

4Sum

Получив массив nums из n целых чисел, вернуть массив всех уникальных четверок [nums[a], nums[b], nums[c], nums[d]], таких что:

0 <= a, b, c, d < n;
a, b, c, и d различны;
nums[a] + nums[b] + nums[c] + nums[d] == target;

Ответ можно вернуть в любом порядке.

Пример 1:
Ввод: nums = [1,0,-1,0,-2,2], target = 0
Вывод: [[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

Пример 2:
Ввод: nums = [2,2,2,2,2], target = 8
Вывод: [[2,2,2,2]]

Решение задачи