fbpx

Coding Interview Questions-Reservoir Sampling

Reservoir Sampling is an algorithm for sampling elements from a stream of data. Imagine you are given a really large stream of data elements, for example:

  • Queries on DuckDuckGo searches in June
  • Products bought at Sainsbury’s during the Christmas season
  • Names in the white pages guide.

Let me put in these easy words imagine the following “dating” game show. The contestant, a bachelorette, is seated at a table with an empty chair. The host introduces the first suitor; the bachelorette has to invite him to sit with her and be her current “date”. Next, the host introduces the second suitor. Now the girl gets the choice of whether she will keep her current “date” or replace him with the new suitor. She can use a variety of means to make her decision, such as asking questions or making the two suitors compete in some way. After that, the host introduces the third suitor, and again the girl can choose to either keep or replace her current “date.” After showing n suitors this way, the game show ends, and the girl goes on a real date with the suitor she kept at the end, the “winner” of the show.

Imagine one contestant who simply flips a coin to decide whether or not to swap her current “date”. Is this “fair” to the suitors, i.e., is the probability distribution of the winner uniform over all the suitors? The answer is no because it is much more likely for the last few suitors to win than the first few suitors. The very first suitor is most unfortunate of all since if he wants to go on a date with the girl, he has to survive n-1 coin flips. The last suitor has the best chances — he only needs to win a single coin flip

If you like video animations and your good in making videos you can sell your videos using this link if you don’t like money forget it, my friend.

import random

def reservoir_sampling(iterator, k):
result = []
n = 0
for item in iterator:
n = n + 1
if len(result) < k:
print(result)
result.append(item)
else:
j = int(random.random() * n)
if j < k:
result[j] = item
print('else:', result)

return result


if __name__ == "__main__":
stream = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
k = 5
print(reservoir_sampling(stream, k))

Cheers,
Zaid Alissa Almaliki


← Previous Post

15 Comments

  1. It’s really a great and useful piece of info. I’m satisfied that you shared this helpful information with us. Please keep us up to date like this. Thank you for sharing.|

  2. You made some decent points there. I looked on the web to learn more about the issue and found most individuals will go along with your views on this web site.|

  3. Evan Plummer

    Asking questions are actually nice thing if you are not understanding anything entirely, but this paragraph provides fastidious understanding even.|

    http://salinasallred60.blogieren.com/Erstes-Blog-b1/videopad-nch-crack-b1-p2.htm

  4. Hello, I read your new stuff like every week. Your writing style is awesome, keep doing what you’re doing!|

  5. Right here is the right website for anybody who wants to understand this topic. You know a whole lot its almost hard to argue with you (not that I personally would want to…HaHa). You definitely put a new spin on a subject which has been discussed for ages. Great stuff, just great!|

  6. Thank you for the auspicious writeup. It in fact was a amusement account it. Look advanced to more added agreeable from you! However, how could we communicate?|

  7. Please let me know if you’re looking for a article author for your site. You have some really great articles and I think I would be a good asset. If you ever want to take some of the load off, I’d love to write some articles for your blog in exchange for a link back to mine. Please shoot me an email if interested. Many thanks!|

  8. Pretty great post. I just stumbled upon your weblog and wanted to mention that I have really enjoyed surfing around your blog posts. After all I’ll be subscribing to your feed and I’m hoping you write again very soon!|

  9. At this time it appears like WordPress is the top blogging platform out there right now. (from what I’ve read) Is that what you are using on your blog?|

  10. I’ve been exploring for a bit for any high-quality articles or blog posts in this kind of area . Exploring in Yahoo I ultimately stumbled upon this site. Reading this information So i’m satisfied to show that I’ve an incredibly good uncanny feeling I found out just what I needed. I such a lot for sure will make sure to don?t disregard this web site and provides it a glance regularly.|

  11. Wow! Finally I got a weblog from where I can genuinely get useful data concerning my study and knowledge.|

  12. Wow! This blog looks exactly like my old one! It’s on a completely different topic but it has pretty much the same layout and design. Excellent choice of colors!|

  13. Woah! I’m really digging the template/theme of this site. It’s simple, yet effective. A lot of times it’s difficult to get that “perfect balance” between usability and visual appeal. I must say that you’ve done a amazing job with this. In addition, the blog loads extremely quick for me on Internet explorer. Outstanding Blog!|

  14. An intriguing discussion is definitely worth comment. There’s no doubt that that you ought to write more about this subject matter, it may not be a taboo matter but usually folks don’t talk about such subjects. To the next! Kind regards!!|

  15. I was reading some of your posts on this internet site and I believe this internet site is very informative! Continue posting.

Leave a Reply

Your email address will not be published. Required fields are marked *