3 ms·

“When we spotted it, it was incredibly obvious,” said Stern, 17. “There were just massive alphabetical votes at random hours.” Reminds me of an interview quest

“When we spotted it, it was incredibly obvious,” said Stern, 17. “There were just massive alphabetical votes at random hours.” Reminds me of an interview question: How would you do a reasonably good job of randomizing an incoming stream of items, while minimizing auxiliary storage?

greiskul 8y ago
Never heard of this question, how do you do that? Do you mean getting a random sample from an incoming stream, using only O(1) space?
- stcredzero 8y ago
  I'm thinking of randomizing the entire stream, and getting something that looks "reasonably random" to casual inspection by human beings, using only O(1) space.
  - DuskStar 8y ago
    It's easy if you don't need exact results! For instance if you want 1/2 votes for A, 1/3 for B and 1/6 for C, well you roll a die and vote A for 1-3, B for 4-5 and C for 6 - do this enough times and it'll approximate that distribution! Things only get difficult if you need exact results OR start doing things to make it "look" random - breaking up long runs of one vote, that sort of thing. (which of course makes it look distinctly nonrandom to someone with a stats background)
    - stcredzero 8y ago
      It's easy if you don't need exact results!\ I didn't mean randomizing the votes. Perhaps I should have written "shuffling." I meant randomizing the order of the stream.
      - willbw 8y ago
        hmm you can randomise the time at which you next put something into the stream right? I am thinking you can sleep() until the next time, just by doing rand() * someMultiplier * aSecond
        stcredzero 8y ago
        How do you do that and wind up with a stochastic O(1) space as opposed to O(n) space? (Remember, O(n/K) is O(n))
      - DuskStar 8y ago
        Randomly choosing the votes sequentially with no memory is arbitrarily close to being the same thing as shuffling for sufficiently high numbers of votes.
        stcredzero 8y ago
        Except that the votes will come in with names in alphabetical order, which is one of the factors cited in the article which got the students caught.
      - Dylan16807 8y ago
        Let me see if I'm misunderstanding something about the problem. 1. The items come in a stream, so you have to accept each one in order. 2. You have to output a stream too. 3. You get a fixed amount of storage, much smaller than the stream. 4. The items are arbitrary and unique, so there is no way to compact n items into significantly less then O(n) storage. If the stream is large and sorted, you run out of buffer before the input stream gets past 'A'. You're forced to output thousands/millions of entries in a row that start with A. That doesn't look at all random. It seems impossible if I understand the problem. Is one of my numbered statements wrong? Is there a way to get items out of order? Put items back into the stream? Is there a limited range of items? Getting unique items in order lets me compress the data very slightly, but 25% more storage doesn't fix anything either.
        8y ago

greiskul 8y ago

Never heard of this question, how do you do that? Do you mean getting a random sample from an incoming stream, using only O(1) space?

stcredzero 8y ago
I'm thinking of randomizing the entire stream, and getting something that looks "reasonably random" to casual inspection by human beings, using only O(1) space.
- DuskStar 8y ago
  It's easy if you don't need exact results! For instance if you want 1/2 votes for A, 1/3 for B and 1/6 for C, well you roll a die and vote A for 1-3, B for 4-5 and C for 6 - do this enough times and it'll approximate that distribution! Things only get difficult if you need exact results OR start doing things to make it "look" random - breaking up long runs of one vote, that sort of thing. (which of course makes it look distinctly nonrandom to someone with a stats background)
  - stcredzero 8y ago
    It's easy if you don't need exact results!\ I didn't mean randomizing the votes. Perhaps I should have written "shuffling." I meant randomizing the order of the stream.
    - willbw 8y ago
      hmm you can randomise the time at which you next put something into the stream right? I am thinking you can sleep() until the next time, just by doing rand() * someMultiplier * aSecond
      - stcredzero 8y ago
        How do you do that and wind up with a stochastic O(1) space as opposed to O(n) space? (Remember, O(n/K) is O(n))
    - DuskStar 8y ago
      Randomly choosing the votes sequentially with no memory is arbitrarily close to being the same thing as shuffling for sufficiently high numbers of votes.
      - stcredzero 8y ago
        Except that the votes will come in with names in alphabetical order, which is one of the factors cited in the article which got the students caught.
    - Dylan16807 8y ago
      Let me see if I'm misunderstanding something about the problem. 1. The items come in a stream, so you have to accept each one in order. 2. You have to output a stream too. 3. You get a fixed amount of storage, much smaller than the stream. 4. The items are arbitrary and unique, so there is no way to compact n items into significantly less then O(n) storage. If the stream is large and sorted, you run out of buffer before the input stream gets past 'A'. You're forced to output thousands/millions of entries in a row that start with A. That doesn't look at all random. It seems impossible if I understand the problem. Is one of my numbered statements wrong? Is there a way to get items out of order? Put items back into the stream? Is there a limited range of items? Getting unique items in order lets me compress the data very slightly, but 25% more storage doesn't fix anything either.
      - 8y ago