Пусть 1 у.е. компьютер требует за 1 элементарную операцию. Пусть записано некоторое двоичное число, начиная справа имеем k единиц до 0. При текущем балансе -(k+1) (credit: k, debit: 1), если k единиц снять со структуры, 1 положить, сколько нужно попросить у клиента, чтобы выйти в 0?

Правильный ответ:

• # Если откладывать одномерные интервалы [l, r] на двумерной плоскости, то в какой области будут находиться интервалы, пересекаемые с точкой x?
• # По какому признаку отрезок разбивается на две части в алгоритме быстрой сортировки (quick-sort)?
• # Пусть на вход алгоритма быстрой сортировки поступает N различных ключей. Тогда каким будет матожидание глубины рекурсии?
• # Предположим, что мы вставили различные k1,...,kn ключей в хэш-таблицу Блюм-фильтра с помощью хэш-функций h1(k),...,hs(k): k -> [0, m-1]. Какая будет вероятность ложного положительного срабатывания?
• # Какую высоту имеет красно-черное дерево с n внутреннеми вершинами (не считая Nil-листьев)?