#algorithms

Так, кто готовился к собесам, что за алгоритм решает следующую задачу:

есть N авторов с произвольным количеством книг у каждого (не более 10).
Нужно упаковать книги в наименьшее число рюкзаков (вместимость рюкзака не более 10 книг), при этом книги одного автора не должны находиться в разных рюкзаках.

#algorithms

Вам требуется оценить наличие книг автора A в магазинах книжной сети. На Ваш запрос в стороннюю АСУ, есть ли на складе магазинов сети определённое число книг N, система учёта по странной причине выдаёт по всем магазинам не точный остаток книг, а нормированную по всей сети и затем разбитую по 10%-ным бинам вероятность того, что в данном магазине есть как минимум N книг. Например, если в сети 3 магазина с 2, 15, 40 книг автора на складе, и Вы запрашиваете, есть ли в магазинах 50 книг, АСУ рассчитает вероятности как [2/50, 15/50, 40/50]=[0.04, 0.3, 0.8], применит насыщение до 1 (останутся те же числа т.к. у нас числа не превышают 1), нормирует на максимальное число 0,8 получит [0.05 , 0.375, 1. ], разобъёт на 10% бины и вернёт ответ [10%, 40%, 100%], Каждый запрос в систему платный, и Вы хотите выяснить если не точное количество книг автора во всех магазинах (так как система округляет бин в правую сторону), то хотя бы их помагазинное соотношение, но при этом минимизировать стоимость получения этой информации. Система ограничивает параметр N до N_MAX=100, то есть наличие больше ста книг проверить не получится. Изменить систему учёта нельзя, можно манипулировать только параметром N и числом отправленных запросов. Как будете действовать?

#algorithms #tries #consistenhashing #quadtrees #leakybucket #bloomfilter #raft #paxos

https://www.youtube.com/watch?v=xbgzl2maQUU

#algorithms #bloomfilter #hyperloglog #minhash #lshforest #fastquantile #rollingquantiles #python #codegems

https://youtu.be/rOi0fybeUf8?si=FvW-LWy8Bo0QFIer