Вопросы на собеседовании: Алгоритмы и код

Дан двумерный массив (изображение) и координаты начальной точки. Реализуйте алгоритм flood fill: перекрасьте начальную точку и все связанные (4-связность) точки того же цвета в новый цвет.

Напишите класс для сэмплирования элементов с заданными вероятностями (weighted random sampling). Класс принимает массив пар (элемент, вероятность) и метод sample() возвращает элемент согласно распределению.

Реализуйте класс для weighted random sampling: метод sample() возвращает элемент с заданной вероятностью. Оптимизируйте время запроса до O(1) с помощью Alias Method.

Реализуйте сэмплирование из дискретного распределения, заданного гистограммой (может содержать float-веса). Оптимизируйте до O(log n) на запрос.

Для каждого числа из массива B найдите число из массива A, дающее максимальный XOR. Реализуйте наивное решение, затем оптимизируйте.

Напишите функцию: зная среднее 5 чисел и одно из чисел, верните среднее оставшихся 4.

Реализуйте Bloom filter. Объясните принцип работы и напишите код.

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).