Вопросы для подготовки к интервью

Bloom filter имеет вероятность false positive. Как зависит эта вероятность от параметров (размер массива m, число хеш-функций k, число элементов n)? Как выбрать оптимальные параметры?

Сравните Bloom filter и hash set (hash map). В каких сценариях Bloom filter предпочтительнее? Приведите примеры из реальных систем.

Дан массив целых чисел и целевое значение target. Найдите два числа, сумма которых равна target, и верните их индексы.

Дана строка, состоящая из символов '(', ')', '{', '}', '[', ']'. Определите, является ли она корректной скобочной последовательностью.

Дан отсортированный массив, из которого удалены некоторые элементы, и он сдвинут (rotated). Найдите минимальный элемент за O(log n).

Реализуйте функцию, которая объединяет два отсортированных связных списка в один отсортированный список.

Дан массив nums и число k. Найдите k-й по величине элемент в массиве (не k-й уникальный).

Реализуйте LRU Cache с операциями get и put за O(1).

Дан массив интервалов intervals[i] = [start, end]. Объедините все перекрывающиеся интервалы.

Дано бинарное дерево. Найдите диаметр дерева (длину наибольшего пути между любыми двумя узлами).

Реализуйте функцию, которая по заданной матрице 0 и 1 находит количество островов (связных компонент из единиц, связанность 4-сторонняя).

Реализуйте Trie (префиксное дерево) с операциями insert, search и startsWith.

Дан массив целых чисел. Найдите длину наибольшей возрастающей подпоследовательности (LIS).

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

Дан ориентированный граф. Реализуйте топологическую сортировку и определите, содержит ли граф цикл.

Реализуйте бинарный поиск по ответу: дан массив из n чисел и число k. Нужно разделить массив на k непрерывных подмассивов так, чтобы максимальная сумма подмассива была минимальной.

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

Реализуйте алгоритм поиска медианы в потоке чисел. Поддерживайте операции addNum(num) и findMedian() с оптимальной сложностью.

Дана строка s и массив слов words. Верните все начальные индексы подстрок в s, которые являются конкатенацией всех слов из words (в любом порядке). Все слова одинаковой длины.

Дан массив prices[] — цены акций по дням. Вы можете совершить не более k транзакций (купить и продать). Найдите максимальную прибыль.