eins's blog

By eins, history, 5 years ago, translation, In English

Hello to everybody!

There is the next task. There is a set of objects, numbered from 1 to n. It is necessary to choose from it a random object such that has not been selected before (need to select no more than n objects). The task itself to do this with O(1) memory and less, than O(n) time.

Perfectly, it needed a function with paremeters like next_object_id(n, current_id, seed), that returns id of the next previously unselected random item.

Is the problem solvable with such requirements?

If there are already developments on this topic, please give a hint on which query to search.

Full text and comments »

  • Vote: I like it
  • -20
  • Vote: I do not like it