4 ms·

> You can't uniformly sample an unbounded set. I was asked to do this as an interview question at google! It was about log file processing not math (sample an

• CamperBob2 2y ago
  What's the correct answer (and what was yours?)
  • seanhunter 2y ago
    The usual trick to sampling one line at random with uniform probability from an arbitrarily large file or stream is worth knowing because people have been asking this as an interview question for >20years at this point[1]. 1. Store the first line with probability p=1 2. When the second line arrives, either keep the first line or with p=.5 drop it and replace it with the second line 3. Continue in this manner with each line. That is to say on the n-th line you either keep the line you have or with p=1/n you drop the line you have and replace the stored line with the new n-th line[2] 4. When you reach the end of the stream or the user quits the program or whatever, return the line you have stored. This will have been selected with uniform probability from the lines you have received. You can sketch the grid for a few lines you can see at every point you have all the lines with uniform probability. It's worth noting that by doing the algorithm in this way you are not in fact ever selecting with uniform probability from an unbounded set so noone is going to revoke your maths license or anything. You are only ever choosing between two things (keep the thing you have or drop it and replace it with a specific new thing). An intuition behind the proof that this does not violate any laws is that in the case of a truly infinite stream this algorithm would never terminate. [1] I know because over 20 years ago I was asked this as an interview question. [2] It's something like this probability. If I was actually answering the question I would work it out properly to be sure.
    • owyn 2y ago
      Yep that was my answer too. I didn't get the job so I'm just guessing but I'm pretty sure that's it.
• racional 2y ago
  It was definitely a dorky question, and a glaring sign of the interviewer's lack of maturity to blithely burn through your precious time in this manner. But if you're going to play Google's game, this what you're going to get apparently. So what was your answer? One guesses that they weren't so much interested in a correct answer (since it's a bullshit question anyway) but that you were willing to give it a college try (and reference some concepts about limits, and perhaps the geometric layout of this "file system" in the Doctor Who universe they were apparently hoping to roll out this system in, the speed of light, etc). In order to, you know, pass their dipshit filter.
  • pedrosorio 2y ago
    Given the description about "sampling from an infinite" something, it's likely this was intended as a variation on reservoir sampling. https://en.wikipedia.org/wiki/Reservoir_sampling https://en.wikipedia.org/wiki/Reservoir_sampling
    • owyn 2y ago
      Yes, I'm sure that's what they were looking for. I hadn't heard of it before but I improvised my way in that direction until the interview was over. :)
      • racional 2y ago
        The "guess my Easter egg" interview pattern. As if this what they do all day: ask each other fundamentally useless questions with no meaningful answer (that anyone would actually care about), and which you aren't expected to provide an actual working answer to, anyway. But which have a cute partial (shibboleth) answer embedded in them. Which if you manage to come up with (under interview time constraints and pressure) -- and most importantly: if you ignore the request to actually solve the problem as stated -- will tell the person asking "how you think".
  • hcks 2y ago
    "I refuse categorically to entertain fun maths problems."
• hansvm 2y ago
  If I had to guess, what they wanted was to sample from a finite set you're only allowed to stream ("unbounded" just means you don't know the bound). Or if it really is unbounded, they still just want a uniform sample up to that point (i.e., still bounded).