Offline Sampling

Offline sampling 

Problem Statement 

Write a program that taken a vector on n integers and return a random sample of size k. All sample must be equally likely. 

Problem Solving

• At first, I had trouble understanding what exactly is a sample,how do measure a probability of such a permutation. 
• After a while I thought that may be generating randomness could be used by a lib function like rand()
• We could use rand() k times to generate a number between 0-n and then selecting it. we will loop this until we have found unique k indexes. 
• This works however this does not sound about right. 
• To do this we also would require a set to store what indexes have been selected and whether a selected index is already used or not. 
• The only problem with this is the extra over head of first storing and searching in a set. 
• We could further remove this by moving the selected element to the end of the array and then using rand() only from 1 - (n-1) . This does it in linear time without the use of any extra memory. 
• Find Code here.

 

Learning

• This problem was hard to think and easier to understand and implement. 
• The key hint is that if you have k elements found how do you select the k + 1 element. 
• This problem is a really useful one as I had never solved this problem before. 
• Also this problem was once asked in some interview, the question was how to shuffle a deck of cards. 
• So yeah this is one key concept I have learned using this problem.