Programming Interview Questions

You have a stream of numbers that you can see one at a time. With uniform probability, select only one of these numbers. That is, each number in the stream has the same probability of being selected. You cannot just store the entire stream to an array or read through the stream twice.

>>15
[/code]
#include <iostream>
#include <cstdlib>
#include <unistd.h>
int main() {
   int reimu, marisa, sanae;
   for (marisa = 0, sanae = 1; ; ++sanae) {
       std::cin >> reimu;
       if ((std::rand() % sanae) == 0) {
           marisa = reimu;
           std::cout << marisa << " was selected with probability 1/" << sanae << std::endl;
       } else {
           std::cout << marisa << " was NOT selected with probability 1/" << sanae << std::endl;
       }
       fork();
   }
   return 0;
}
[/code]

>>19
GOD FUCKING DAMNIT, I HATE IT WHEN I FAIL LIKE THAT

#include <iostream>
#include <cstdlib>
#include <unistd.h>
int main() {
   int reimu, marisa, sanae;
   for (marisa = 0, sanae = 1; ; ++sanae) {
       std::cin >> reimu;
       if ((std::rand() % sanae) == 0) {
           marisa = reimu;
           std::cout << marisa << " was selected with probability 1/" << sanae << std::endl;
       } else {
           std::cout << marisa << " was NOT selected with probability 1/" << sanae << std::endl;
       }
       fork();
   }
   return 0;
}