Приветствуем вас! В данном канале будут публиковаться разборы задач с собеседований с сайта LeetCode.

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

Частота встречи задач на собеседованиях за последние шесть месяцев:
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"]
Вывод: ""
Среди введенных строк нет общего префикса.

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

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

Суммы чисел

Частота встречи задач на собеседованиях за последние шесть месяцев:
Amazon — 107, Adobe — 52, Apple — 44, Microsoft — 43, Google — 40.

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

Примеры:
Ввод: nums = [2,7,11,15], target = 9
Вывод: [0,1]
Поскольку nums [0] + nums [1] == 9, мы возвращаем [0, 1].

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

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

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

Длина последнего слова в строке

Частота встречи задач на собеседованиях за последние шесть месяцев:
Amazon — 3, Microsoft — 2, Google — 3.

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

Слово — это максимальная подстрока, состоящая только из символов, не содержащих пробелов.

Требуемая сложность:
O(N), N - длина строки.

Примеры:
Ввод: s = "Hello World"
Вывод: 5
Объяснение: Последнее слово строки s "World" имеет длину 5.

Ввод: s = " fly me to the moon "
Вывод: 4
Объяснение: Последнее слово строки s "moon" имеет длину 4.

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

Квадратный корень

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

Условие задачи:
Рассматриваем неотрицательное целое число x. Требуется вычислить и вернуть квадратный корень из x. Поскольку возвращаемый тип является целым числом, десятичные цифры усекаются, и возвращается только целочисленная часть результата.

Примеры:
Ввод: x = 4
Вывод: 2

Ввод: x = 8
Вывод: 2
Объяснение: Квадратный корень из 8 равен 2,82842..., и поскольку десятичная часть усечена, возвращается 2.

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

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

Частота встречи задач на собеседованиях за последние шесть месяцев:
LinledIn — 42, Amazon — 34, Apple — 20, Microsoft — 18, Google — 16, Adobe —16

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

Примеры:
Ввод: nums = [-2, 1, 4, -1, 2, -3]
Вывод: 6
Объяснение: [1, 4, -1, 2] будет иметь максимальную сумму, равную 6

Ввод: nums = [4]
Вывод: 4

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

Самая длинная подстрока без повторяющихся символов

Частота встречи задач на собеседованиях за последние шесть месяцев:
Amazon — 60, Microsoft — 34, Bloomberg — 19.

Для заданной строки s найдите длину самой длинной подстроки без повторяющихся символов.

Примеры:
Ввод: s = "abcabcbb"
Вывод: 3
Объяснение: Ответ "abc" длиной 3.

Ввод: s = "bbbbb"
Вывод: 1
Объяснение: Ответ "b" длиной 1.

Ввод: s = "pwwkew"
Вывод: 3
Объяснение: Ответ "wke" длиной 3.
Обратите внимание, что ответ должен быть подстрокой, «pwke» — это подпоследовательность, а не подстрока.

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