Новый сервер в кольце
Кластер кэша устроен как кольцо хешей: числа от 0 до 2⁶⁴ − 1, после самого большого снова идёт ноль. На кольце стоят точки серверов (у сервера их может быть несколько — виртуальные узлы). Ключ принадлежит серверу первой точки, которая строго больше хеша ключа; если таких нет, круг замыкается, и ключ принадлежит серверу самой первой точки кольца.
В кластер добавляют новые точки (новый сервер). Сколько ключей сменят сервер и сколько ключей окажется на самом загруженном сервере после добавления? Два теста построены из настоящих адресов страниц legost.in так же, как в статье.
Вход
Число точек n (1 ≤ n ≤ 100 000), затем n строк «хеш сервер». Число новых точек m (1 ≤ m ≤ 10 000) и m строк в том же формате. Число ключей q (1 ≤ q ≤ 200 000) и строка из q хешей ключей. Хеши — целые от 0 до 2⁶⁴ − 1, номера серверов — целые от 1 до 10⁹. Хеши точек различны.
Выход
Две строки: сколько ключей сменили сервер и сколько ключей у самого загруженного сервера после добавления.
Примеры
Пример 1
3 100 1 200 2 300 3 1 250 4 7 50 150 220 260 299 300 350
1 3
Ограничения
- Время · Python
- 5000 мс
- Время · Go
- 1000 мс
- Память
- 256 МБ
- Проверка
- 7 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Отсортируйте точки по хешу. Каким алгоритмом найти первую точку, строго большую данного числа?
2Подсказка 2
Что делать с ключом, у которого хеш больше хеша всех точек? Посмотрите на второй пример.
3Идея
Владелец ключа — это верхняя граница хеша ключа в отсортированном массиве точек, взятая по модулю числа точек: индекс, равный длине массива, превращается в ноль — так замыкается круг. Считаем владельцев до и после добавления и сравниваем.
4Разбор
Сортируем исходные точки, для каждого ключа находим bisect_right(hashes, key) % n — номер точки, затем её сервер. То же самое для объединения старых и новых точек. Число несовпадений — ответ на первый вопрос; словарь «сервер → число ключей» после добавления — на второй.
Хеши доходят до 2⁶⁴ − 1: в Go это uint64, а не int64, иначе большие хеши станут отрицательными и порядок сломается. В Python целые не ограничены.
4+Решение
5Сложность
Сортировка O((n + m) log(n + m)), поиск — O(q log(n + m)).
6Типичные ошибки
- Без замыкания. Ключ правее последней точки отдают последнему серверу, а должен достаться первому. Ловится первым примером.
- «Больше или равно» вместо «строго больше». По условию ключ с хешем, равным хешу точки, уходит к следующей точке. Последний тест проверяет именно это.
- int64 в Go. Хеши больше 2⁶³ становятся отрицательными.