morfizm (morfizm) wrote,
morfizm
morfizm

Category:

Задачка

Столкнулся с красивой задачкой на работе.
* Объекты можно хэшировать в K buckets.
* Сгенерировать минимальное число объектов, хэши которых покрывают все K buckets для каждого 1 <= K <= N.
* Сколько получается объектов для N = 100? Для N = 200?

Про хэшфункцию заранее ничего неизвестно, кроме того, что она равномерная.
Можно решить задачу двумя вариантами - в одном известно, что хэшфункция имеет вид hash(d) % K, а в другом она совершенно произвольная (и может быть принципиально разной для разных значений K).
Tags: fun, polls questions and social games, software development, work
Subscribe
  • Post a new comment

    Error

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 42 comments