Наиближайший общий предок

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

Условие задачи: дано бинарное дерево поиска, надо найти ближайшего родителя для обоих потомков.

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

Пример:

Ввод: [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
Вывод: 6
Объяснение: *на картинке

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

Максимальный подмассив

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

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

Подмассивом называется последовательная часть исходного массива.

Пример:

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

Объяснение: 4,-1,2,1] имеет наибольшую сумму 6.

Ввод: nums = [5,4,-1,7,8]
Вывод: 23

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

Переспелые апельсины

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

Условие задачи: дана двумерная решетка размера m x n, в каждой из ячеек может находится одно из следующих значений:
0 - пустая ячейка,
1 - созревший апельсин,
2 - переспевший апельсин.

Каждую минуту апельсины, находящие рядом (сверху, слева, снизу, вправа) с переспевшими - становятся переспевшими.

Необходимо подсчитать количество минут, за которое все апельсины превратятся из свежих в переспевшие. Если это невозможно, то в ответе должна получаться -1.

Пример:

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

Ввод: grid = [[2,1,1],[0,1,1],[1,0,1]]
Вывод: -1
Объяснение: переспевший фрукт не контактирует со спелыми плодами.

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

Слияние двух отсортированных массивов

Сложность: Лёгкая

Условие задачи: даны два массива, отсортированные в порядке неубывания, а также две переменные m и n, в которых хранится длина каждого из массивов.

Надо свзать оба массива в один в порядке неубывания.

Результирующий массив должен содержаться в массиве nums1.

Пример:

Ввод: nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
Вывод: [1,2,2,3,5,6]

Ввод: nums1 = [1], m = 1, nums2 = [], n = 0
Вывод: [1]

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

Нахождение опорного элемента

Сложность: Лёгкая

Условие задачи: дан массив, состоящий из целых чисел. Необходимо вернуть опорный элемент массива.

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

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

Пример:

Ввод: nums = [1,7,3,6,5,6]
Вывод: 3

Объяснение:
Left sum = nums[0] + nums[1] + nums[2] = 1 + 7 + 3 = 11
Right sum = nums[4] + nums[5] = 5 + 6 = 11

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

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

Объяснение:
Опорный элемент - 0.
Left sum = 0 (нет элементов левее индекса 0)
Right sum = nums[1] + nums[2] = 1 + -1 = 0

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

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

Сложность задачи: Средняя

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

Вы можете вернуть ответ в любом порядке. Если s не имеет палиндромной перестановки, вернуть пустой список.

Пример:
Ввод: s = "aabb"
Вывод: ["abba","baab"]

Ввод: s = "abc"
Вывод: []

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

Doodle Jump

Сложность задачи: Средняя

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

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

Пример:
Ввод: nums = [1,3,1,1,4]
Вывод: true
Объяснение: Переходим на 1 шаг от индекса 0 к 1, затем на 3 шага к последнему индексу.

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

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

Одно редактирование

Сложность задачи: Средняя

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

Говорят, что строка s находится на расстоянии редактирования от строки t, если вы можете:
• Вставить ровно один символ в s, чтобы получить t.
• Удалить ровно один символ из s, чтобы получить t.
• Заменить ровно один символ s другим символом, чтобы получить t.

Пример:
Ввод: s = "ab", t = "acb"
Вывод: true
Объяснение: Мы можем вставить 'c' в s, чтобы получить t.

Ввод: s = "", t = ""
Вывод: false

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

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

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

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

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

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

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

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

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

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

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

Изоморфизм строки

Сложность: Лёгкая

Условие задачи: даны две строки s и t. Просят проверить их на изоморфность.

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

Пример:

Ввод: s = "egg", t = "add"
Вывод: true

Объяснение: "e" <--> "t", "g" <--> "d"

Ввод: s = "foo", t = "bar"
Вывод: false

Объяснение: "f" <--> "b", "o" <--> "a", "o" <--> "r". Два символа из второй строки соответствуют одному символу из первой строки.

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

Поменяйте местами узлы парами

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

Пример 1 (картинка):
Input: head = [1,2,3,4]
Output: [2,1,4,3]

Пример 2:
Input: head = []
Output: []

Пример 3:
Input: head = [1]
Output: [1]

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

Стак через очередь

Сложность: Лёгкая

Условие задачи: необходимо реализовать стркутуру "последний зашел - первый вышел" используя только две очереди. Реализованная струкутура должна поддерживать функции обычного стака (добавления в стак, удаление верхнего элемента стака, возврат верхнего элемента стака, проверка на наличие элемнтов в стаке).

Пример:

Ввод: ["MyStack", "push", "push", "top", "pop", "empty"]
[[], [1], [2], [], [], []]
Вывод: [null, null, null, 2, 2, false]

Объяснение:
MyStack myStack = new MyStack();
myStack.push(1);
myStack.push(2);
myStack.top(); // return 2
myStack.pop(); // return 2
myStack.empty(); // return False

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

Уродливое число

Сложность: Лёгкая

Условие задачи: уродливое число - это целое положительное число, множителями которого являются только 2, 3 и 5.

Надо проверить, является ли подаваемое число уродливым.

Пример:

Ввод: n = 6
Вывод: true
Объяснение: 6 = 2 × 3

Ввод: n = 14
Вывод: false

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

Смена операции

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

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

В результате необходимо получить это самое произведение.

Пример:

Ввод: n = 2
Вывод: 1
Объяснение: 2 = 1 + 1, 1 × 1 = 1.

Ввод: n = 10
Вывод: 36
Объяснение: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36.

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

Групповые анаграммы

Сложность задачи: Средняя

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

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

Пример:
Ввод: strs = ["eat","tea","tan","ate","nat","bat"]
Вывод: [["bat"],["nat","tan"],["ate","eat","tea"]]

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

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

Треугольник Паскаля

Сложность задачи: Легкая

Условие задачи:
Дано целое число numRows, верните первые numRows треугольника Паскаля.

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

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

Ввод: numRows = 1
Вывод: [[1]]

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

Генерация скобок

Сложность задачи: Средняя

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

Пример:
Ввод: n = 3
Вывод: ["((()))","(()())","(())()","()(())","()()()"]

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

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

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

Сложность задачи: Средняя

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

Глубина целого числа — это количество списков, внутри которых оно находится. Например, во вложенном списке [1,[2,2],[[3],2],1] каждому целочисленному значению соответствует его глубина. Пусть maxDepth будет максимальной глубиной любого целого числа. Вес целого числа равен maxDepth - (глубина целого числа) + 1.

Верните сумму каждого целого числа во вложенном списке, умноженную на его вес.

Значения целых чисел во вложенном списке находятся в диапазоне [-100, 100].
Максимальная глубина любого целого числа меньше или равна 50.

Пример:
Ввод: nestedList = [[1,1],2,[1,1]]
Вывод: 8
Объяснение: Четыре единицы с весом 1, одна двойка с весом 2.
1*1 + 1*1 + 2*2 + 1*1 + 1*1 = 8

Ввод: nestedList = [1,[4,[6]]]
Вывод: 17

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

Знак произведения массива

Сложность задачи: Легкая

Условие задачи:
Существует функция signFunc(x), которая возвращает:
1, если x положительно
-1, если x отрицательно
0, если x равно 0.
Вам дается целочисленный массив nums. Пусть product - это произведение всех значений в массиве nums. Верните signFunc(product).

Пример:
Ввод: nums = [-1,-2,-3,-4,3,2,1]
Вывод: 1
Объяснение: Произведение всех значений в массиве равно 144, а signFunc(144) = 1.

Ввод: nums = [1,5,0,2,-3]
Вывод: 0

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

Наибольший общий префикс

Частота встречи задач на собеседованиях за последние шесть месяцев:
Facebook* — 21, Amazon — 16, Apple — 14, Adobe — 11, Google — 9, Microsoft — 6, Uber — 6.

Условие задачи:
Напишите функцию для поиска самого длинного общего префикса у массива строк. Если общего префикса нет, верните пустую строку.

Требуемая сложность:
O(S), S — сумма всех символов во всех строках.

Примеры:
Ввод: strs = ["flower","flow","flight"]
Вывод: "fl"

Ввод: strs = ["dog","racecar","car"]
Вывод: ""
Среди введенных строк нет общего префикса.

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

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