Yahoo Interview Question
Software Engineer / DevelopersI do not think this would be absolutely equal possibility for all numbers :
for the
a = 4*rand_0_or_1() + 2*rand_0_or_1() + rand_0_or_1())==0
ypu have:
num -> possibility
1 -> 1/2
2 -> 1/2
3(1 + 2) -> 1/2 + 1/2 = 1/4
4 -> 1/2
etc...
probably the best way here is to find least common multiple of 5 and 7 = 35 and have s = sum(rand5()) -> 7 times(LCM/5) and return s%7
if we can assume rand5 return integer between 1 and 5, rand7 return integer between 1 and 7
int rand7()
{
int val = 0;
while(val ==0)
val = (rand5() + rand5())%8;
return val;
}
This is not correct. Reason:
The expression rand5() + rand5() will return a value between 0 and 10. Consider two groups on this [0-7] and [8-10].
Now when rand5() + rand5() lies is 2nd group(8-10) , then your method returns a value in [0-2]. Hence the probability of occurrence of of [0-2] is higher than other numbers. Consequently its not random.
The way (rand5() + rand5()) will not work, since the sum to 0 is only (0+0), and sum to 1 is (1+0) and (0+1). The probability of sum to each number is not equal. Correct way is use rand5() to generate two digits (a, b), to form a number a*10 + b. Suppose rand5() is [1, 5], then define 11,12,...,15,21,22 these 7 numbers are valid, and return one of them when we get one. This method can guarantee that the probability of appearance of each these number is equal.
The above solution is incorrect since probability of occurrence of 7 is 0. And also, i am not sure if we can assume the numbers to only be integers, and not fractional. How about this :
a = ( ( rand5() - 1 ) / 4 ) * 3 + 1; //gets a num between 1 and 4
b = ( ( rand5() - 1 ) / 4 ) * 3 + 1 + 3; //gets a num between 4 and 7
c = rand5();
if(c >=1 && a<=3) //0.5 probability of selecting either of a or b
return a;
else
return b;
<pre lang="c" line="1" title="CodeMonkey4069" class="run-this">
// A problem with a lot of the solutions above, is that the resulting distribution won't be uniform.
// This is crude, but should be uniform.
#include <stdlib.h>
#include <stdio.h>
int rand5()
{
return (rand() % 5) + 1;
}
int rand7()
{
// cancel out all the +1s at once
int x = -7;
int i;
for (i = 0; i < 7; ++i) {
x += rand5();
}
// now have a number between 0 and 28.
x %= 7;
x += 1;
return x;
}
int main()
{
int dist[7] = {0};
int i;
for (i = 0; i < 1000; ++i) {
dist[rand7()-1]++;
}
for (i = 0; i < 7; ++i) {
printf("%d ", dist[i]);
}
printf("\n");
return 0;
}
jd@shade:/mnt/raid/projects/interviewQs$ ./rand7
137 156 157 140 132 148 130
-- seems relatively even
</pre>
This solution is not uniform. You may try to modify the number 7 to other numbers (e.g. 5 or 6) in the following line of function rand7(), and still generate a result that seems to be uniform, but not accurately.
for (i = 0; i < 7; ++i) {
Mmmm, yes, I just did that:
# 'bad', '< 5' and 1000 samples
jd@shade:~/projects/interviewQs$ ./rand7
148 156 133 153 135 132 142
and you're right, about the same 'uniformity', by eyeball, as my results above. Neither of them great. But, at 100,000,000 either it's somehow bad luck (but shouldn't be, at 100,000,000) or, I'm right.
# bad; '< 5', 100,000,000
jd@shade:~/projects/interviewQs$ ./rand7
14402060 14431600 14399214 14272500 14112046 14076142 14115245
# good; '< 7' 100,000,000
jd@shade:~/projects/interviewQs$ ./rand7
14306739 14302342 14277656 14270321 14259744 14282261 14300937
# quite a bit more uniform. So, it's a bad test, not a bad algorithm, as far as I can see. Although I'm puzzled, I would have thought the balance would have been much worse.
What I'm going for, is that if you just try to make the number fall between [1..7] that's easy, just add 2 rand5()s together and % 7, + 1. But you'll get the result hitting the lower numbers more often, as the 8,9,10 wraps around to 1,2,3. I'm trying to get rid of the '5-ness' by adding 7 of those random 1..5 numbers together. Perhaps what I was thinking was / 5, not % 7. Though % 7 seems to work ok, perhaps it's equivalent (you'd have to correct what you do with the rand5()s a bit to use / 5. Still, not sure it's right).
int rand7()
{
int i;
do
{
i = 5 * (rand5() - 1) + rand5();
// 5 * (rand5() - 1) could be 0,5,10,15 or 20
// 0 + rand5() => 1 2 3 4 5
// 5 + rand5() => 6 7 8 9 10
// 10 + rand5() => 11 to 15
// ...
// 20 + rand5() => 21 to 25
//
// => i is uniformly random in closed interval [1,25]
} while(i > 21);
return i % 7 + 1;
}
do {
f = rand5();
} while (f==5) //accept only 1-4
do (
s = rand5();
} while (s==5)
do (
t = rand5();
} while (t==5)
return ( (f%2)<<2 + (s%2)<<1 + (t%2) )
fmb's algorithm has a floor of 2 rand5() calls and a 16% change of running 2 additional rand5() calls.
This one is a floor of 3 rand5() calls and a pretty high change of going more, but it still works and is evenly distributed.
The problem with this solution is the probability of getting numbers 1 to 5 is less than the probability of getting 6 and 7
Why not -
rand7() = rand5() + (radn5()%3);
Rand5() has equal probability of 1,2,3,4,5
Rand5()%3 has equal probability of 0,1,2
?
int sum = 0;
int i = 0;
while (i < 7)
sum += rand5();
return (sum % 7) + 1;
IOW, uniform probability for sum to be between 7 and 35.
1. rand5() will give result from 0 to 5.
2. Probablity of getting an even number or an odd number (assuming rand5() is perfect) will be .5 each
3. 7 when converted into binary has 3 set bits.
4. call rand5() 3 times if result is even then set the corresponding bit otherwise make that bit 0.
Basically here I am trying to generate all the bits with equal probablity
psuedo code:
int multiplicationFactor = 1;
int rand7Number = 0;
for(int i = 0 ; i < 3 ; i++)
{
int j = rand5();
rand7Number += (j%2) * multiplicationFactor ;
multiplicationFactor *= 2;
}
return rand7Number ;
two mistakes in the code.
1. rand5() gives a random number in (1, 5) and not (0,5). Probability of getting even number is not equal to p(odd number)
2. your rand7() must give a random number in (1,7). the case of all bits zero must be taken care.
How abt the modification to this solution?
int multiplicationFactor = 1;
int rand7Number = 0;
do{
for(int i = 0 ; i < 3 ; i++)
{
int j = (rand5()%2 + (rand5()+1)%2)%2;;
rand7Number += (j%2) * multiplicationFactor ;
multiplicationFactor *= 2;
}
}while(rand7Number == 0);
return rand7Number ;
Lets say call rand(5) 2 times, so we will get a pair of number by this.
Now if we take any 7 pairs of different numbers (i.e. say (1,2), (1,3), (1,4), (1,5), (2,3), (2,4), and (2,5) call this PairSet) then probability of any pair coming out of calling rand(5) two times is equal and that is 2/25. Map these pairs to number 1 to 7 in any order (for example {[(1,2), 2], [(1,3), 3], [(1,4), 1], [(1,5), 7], [(2,3), 4], [(2,4), 6], [(2,5), 5]} call this PairMap).
So now we can define rand(7) as follows
rand(7){
int num1=0; int num2=0;
while(!(PairMap.contains((num1, num2)) || PairMap.contains((num2, num1)))){
num1 = rand(5);
num2 = rand(5);
}
if(PairMap.contains((num1, num2))
return(PairMap.get((num1, num2)));
else return(PairMap.get((num2, num1)));
}
I think I may have figured out a decent uniform solution. Please let me know if it isn't (or if I'm not the first to suggest this answer...I just skimmed all of the comments so I could have missed one. )
Written in rough pseudo so please let me know if there is anything that doesn't make sense.
{{
num = 0
for 1 ... 7
num += rand5
return num % 7 + 1
}}
To sum it up:
Generate 7 random numbers between 1 and 5 and sum them up
This results in a random number between 5 and 35
Mod this number by 7
This results in a random number between 0 and 6
Add 1
I'd love to see some analysis if somebody is willing to do so but I'm pretty sure this is uniform.
This approach could also be used to generalize this so if you were given a random number generator between 1 and x and you want to generate a number between 1 and y ( where y > x) you generate y random numbers between 1 and x and mod it by y and add 1.
Thought or comments?
I made that first post on my phone and messed up the code format a little so here's a correction for that.
num = 0
for 1 ... 7 {
num += rand5
}
return num % 7 + 1
And now that I'm on a computer, I did a quick analysis on it and it isn't exactly uniform :( ...but it is pretty close.
I'm sure there's an easier way to do this but my stats skillz are really rusty so simply writing a program to brute force this was the quickest way for me. I just counted all of the possible permutations of 7 numbers between 1-5 to see if it was evenly distributed.
For example:
1+1+1+1+1+1+1 % 7 + 1 = 1
1+1+1+1+1+1+2 % 7 + 1 = 2
1+1+1+1+1+1+3 % 7 + 1 = 3
...
5+5+5+5+5+5+4 % 7 + 1 = 7
5+5+5+5+5+5+5 % 7 + 1 = 1
The final result showed that there were more permutations that sum up to 1 than any of the other numbers...but it is really close.
1: 11177
2: 11172
3: 11158
4: 11144
5: 11144
6: 11158
7: 11172
But hey...I make mistakes too so if I'm wrong, please call me out on it :)
If we have rand5(), we can get rand10 by selecting combination of 2 numbers (C5,2). We do rand5 () twice, if the second is the same with the first, regenerate the second. Finally, based on the two number we can switch the return result, each has the possibility of 1/10;
So if the two number is (1,2) return 1, (1,3), return 2....
If we have rand10, we can simply do a rand10 if it is 8,9 or 10, generate again. Then we will have rand7();
The code and testing program is as follows. Testing is to generate 10000 times rand7() and give the frequency of each number, if they are close to 1/7, it would be correct.
import java.util.Hashtable;
public class RAND {
public static int rand5(){
return (int) (Math.random() * 5 + 1);
}
public static int rand10 (){
int p1 = rand5();
int p2 = rand5 ();
while (p1 == p2){
p2 = rand5();
}
int product = p1 * p2;
switch (product){
case 2:
return 1;
case 3:
return 2;
case 4:
return 3;
case 5:
return 4;
case 6:
return 5;
case 8:
return 6;
case 10:
return 7;
case 12:
return 8;
case 15:
return 9;
case 20:
return 10;
}
return -1;
}
public static int rand7 (){
int p = rand10 ();
while (p == 8 || p == 9 || p ==10){
p = rand10 ();
}
return p;
}
public static void main (String args[]){
Hashtable <Integer,Integer> freq = new Hashtable <Integer,Integer> ();
int rounds = 100000;
for (int i = 1 ; i <=7 ; i++ ){
freq.put(i, 0);
}
for (int i = 0 ; i < rounds ; i ++){
int key = rand7();
freq.put(key, freq.get(key) + 1);
}
for (int i = 1 ; i <=7 ; i++ ){
double fre = freq.get(i);
fre /= rounds;
System.out.println(i+"..............."+fre);
}
}
}
- Roshan Mangal May 31, 2012