Return Styles: Pseud0ch, Terminal, Valhalla, NES, Geocities, Blue Moon. Entire thread

Programming Interview Questions

Name: Anonymous 2011-05-22 16:08

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.

Name: Anonymous 2011-05-22 16:15

Impossible without knowing the number of items in the stream.

Name: Anonymous 2011-05-22 16:31

>>2
Think more.

Name: Anonymous 2011-05-22 16:32

>>2
Shut the fuck up, bitch.  You are SO FUCKING WRONG. 

>>1
Ok, nigger, what you FUCKING DO is create an ARRAY of INTEGERS that has ONE ELEMENT for EACH POSSIBLE NUMBER in the STREAM.  You then READ THROUGH the ENTIRE GOD DAMN STREAM.  Increase the ELEMENT WITHIN THE DAMN ARRAY that corresponds with the NUMBER READ FROM THE STREAM.  You'll then have a GOD DAMN FUCKING HISTOGRAM OF ALL READ NUMBERS and can select a RANDOM NUMBER with SHIT PROBABILITES ADJUSTED FOR FREQUENCY OF OCCURRENCE.  FUCK.

Name: Anonymous 2011-05-22 16:40

>>4
What if the numbers can be anything in the range [0,232)?

Name: Anonymous 2011-05-22 16:41

>>4
What if the numbers are floating point?

Name: Anonymous 2011-05-22 16:42

>>4
what if the numbers are 64-bit integers

Name: Anonymous 2011-05-22 16:42

>>5-6
OP needs to specify the rules more clearly.

Name: Anonymous 2011-05-22 16:45

>>1
You could solve it by recursively reading each number in sequence and keeping track of the call depth in another variable, and then random select which value to use when traversing back up the call tree. That's probably what the interviewer is after.

Of course, at this point, I would tell the interviewer to literally go fuck himself, because essentially you're just storing the values in the program stack, and the call overhead of solving the problem in this fashion is more expensive both in terms of time and space complexity than if you were to have just cached the values in a dynamically re-sizable array.

I would then get hired on the spot for my initiative, confidence and bravado.

Name: Anonymous 2011-05-22 16:45

>>4
Seriously bro? That's just a variation on storing the stream in an array. All you're doing is throwing MapReduce at the same unacceptable strategy—you're still finding a way to look at an input element more than once.

Aha! Wait, I think I may have a plan.

Start by selecting the first number. Then, with probability 1/i, overwrite it with the next item in the stream. This works perfectly.

Name: Anonymous 2011-05-22 16:46

You could solve it by recursively reading each number in sequence and keeping track of the call depth in another variable, and then random select which value to use when traversing back up the call tree. That's probably what the interviewer is after.
Yes.

Of course, at this point, I would tell the interviewer to literally go fuck himself, because essentially you're just storing the values in the program stack, and the call overhead of solving the problem in this fashion is more expensive both in terms of time and space complexity than if you were to have just cached the values in a dynamically re-sizable array.
Yes.

I would then get hired on the spot for my initiative, confidence and bravado.
Lol, no.

Name: Anonymous 2011-05-22 16:51

>>10
Learn to probability my friend.

The probability of the value at iteration i being selected is also dependent on the fact that a value at iteration j where j > i, doesn't overwrite. They aren't independent events.

Name: Anonymous 2011-05-22 16:53

>>12
yhbt

Name: Anonymous 2011-05-22 16:58

>>12
I'm probabilitying as fast as I can, home-slice. Only because they overwrite do the values have an equal value of being selected. You don't return until the end of the scan; until then you just hold the variable in memory. I think you understand that.

Consider the straight-forward case: we know we have 3 elements and we want to know what probability each should be considered with in order to produce 1/3 chance of selection:

Item 1: 1/3
Item 2: 1/2
Item 3: 1

The solution I gave in >>10 works by reversing this. ... or maybe it doesn't. I'm not sure.

If it isn't, it's impossible to solve this problem without storing all of the variables in some fashion.

Name: Anonymous 2011-05-22 17:03

>>12
Just tested it quickly:


Private Sub Form_Load()
    Dim k(100) As Integer
    For j = 1 To 10000
    o = 0
    For i = 1 To 100
        If Rnd < 1 / i Then o = i
    Next i
    k(o) = k(o) + 1
    Next j
   
    For j = 1 To 100
        Me.Line (j, 100)-(j, 100 - k(j)), 0
    Next j
End Sub

Yes, VB6 is an embarrassment, but it works and produces an even distribution reliably. So EAT IT.

Name: VIPPER 2011-05-22 17:03

I dont understand this thread, i just thought you should know.

Name: Anonymous 2011-05-22 17:04

>>14
Nope. Doesn't even work in reverse.

Consider the forward example.

p(Item 1) = 1
p(Item 2) = 1/2
p(Item 3) = 1/3

If Item 3 is not selected, then that doesn't affect the fact that we may have selected Item 2 with probability of 1/2.

In other words, in the 3 item case, the probability of selecting Item 2 is in fact p(Item 2) = 2/3 * 1/2 = 2/6.

Name: Anonymous 2011-05-22 17:07

>>17
2/6 = 1/3 = correct. Nice work. My solution stands.

Name: Anonymous 2011-05-22 17:14

>>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]

Name: Anonymous 2011-05-22 17:14

>>18
YHBT

Name: Anonymous 2011-05-22 17:15

>>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;
}

Name: Anonymous 2011-05-22 17:16

>>20
You're cute when you're caught red-handed.

Name: Anonymous 2011-05-22 17:19

>>19,21
I think you may have a halting problem.

Name: Anonymous 2011-05-22 17:25

>>23
What are you talking about? That's what the fork is for. Since there is no such thing as computer with an infinite amount of memory, the program halts when it runs out of its finite memory and swap space and crashes.

That's how I break out of the infinite loop!

Name: Anonymous 2011-05-22 17:33

>>24
You sure are funny guy!!

Name: Anonymous 2011-05-22 20:48

Why do interviewers ask such stupid shit?

Hurr, how do you solve this problem in a way that is impractical in the real world?

Name: Anonymous 2011-05-22 21:19

>>26
To assess your critical reasoning skills and style of thinking. I believe you just fell squarely into the "unimaginative and complains too much to be hired" category.

Name: Anonymous 2011-05-22 21:47

>>27
Hint: You can do that without asking stupid questions with no real world application.

Name: Anonymous 2011-05-22 21:48

while (1) {
if (select()==number)
break;
}
Never said I had to find more than one number.

Name: Anonymous 2011-05-22 22:27

>>28
IN-CORRECT. You must be able to think outside of ANY AND ALL BOXES.
Newer Posts
Don't change these.
Name: Email:
Entire Thread Thread List
All trademarks and copyrights on this site are owned by their respective parties. All comments and posts are the responsibility of their own posters.
- Tinychan + 2ch Mode -