Online Sampling
Problem Statement
Write a program that takes a stream and reads value from it to maintain a random subset of k elements.
Problem Solving
- Instantly I think about a function that takes in a stream
- First fetches k values to fill a vector of size k.
- On further input decides whether to take this element or not based on psuedo random number.
- Then randomly select an index in the vector and write over that value the new value.
- But I am not sure, If I understand the question correctly.
- I'll probably code it and run it on the EPI judge and then get back here.
- Well this does not work.
- After understanding the solution which is quite similar with a stark difference which solves the issue.
- The random number generator is used to generate numbers from 0 - all number seen till now. If that number lies in 0 - k range then we replace that index with the new number.
- However here all subset generated in sequence only differ by 1 element.
Learning
- I have clearly to do a deep dive in probability as I had trouble understanding what makes a subset really random.
- The offline sampling problem gave a lot of clarity however this is new.
- Also the new random num generation lib constructs in c++ 11 needs to be defunct.
- Huh.. few tasks here. okay it's just okay to admit that there are few things I do not know and that as this progresses, so will I.
- Keep on...
No comments:
Post a Comment