Задача на Аналитика

Изначально у вас нет предметов. Вам поступают запросы, вида добавь предмет с названием s_i и веса w_i.
А еще бывают запросы вида: вытащи мне из набора предметов учитывая их вероятности.

Пример.
У вас есть предметы:
"abc" - 4
"qq" - 2
"bbb" - 6
Тогда вероятность того что вернете строку "abc" равно 4/12, вероятность вернуть "qq" равно 2/12, вероятность вернуть "bbb" вернуть 6/12.

После добавили предмет "post" веса 5
Ваши вероятности станут следующими:
abc - 4/17, qq - 2/17, bbb-6/17, post-5/17.
(Честно сам не понял условия, пока собеседующий не дал пример)

Решение:

Во первых заметим, что у нас нет операции удаления, это нам сильно облегчит задачу.
Пусть вам пришел запрос добавить первый предмет в набор, пусть его веса равен 3. Давайте в массиве who на отрезке [1, 3] поставим число 1.
Т.е who[1] = who[2]=who[3] = 1, а остальные пока нули.

После вам сказали добавить второй предмет в набор, пусть его вес равен 2, давайте поставим в массиве who на отрезке [4, 5] число 2.
То есть у вас получится такой массив who = [1, 1, 1, 2, 2, 0, 0, 0, 0, 0, ...0].

Думаю вы поняли что тут происходит.
Теперь запустим randint на отрезке 1, до суммы весов предметов.
Пусть выпало число pos, тогда who[pos] и будет предметом который нужно вернуть.

В комментариях расскажите что можно оптимизировать в этом решение.