Bloomberg | Phone | Reservoir Sampling
2122

Given a distinct array of elements. Find n non-repeating random elemnents.

For ex: [2,4,1,-19,56,23,0,34,112,5] , n =3
Output: [ 112,56,23]

Constraints:

  1. Each number has to get equal chance to be in the random set
  2. What is the complexity of the solution?
Comments (5)