Yahoo Interview Question for Software Engineer / Developers






Comment hidden because of low score. Click to expand.
2
of 2 vote

rand_0_or_1() {
  while(  (( a=rand5() ) ==5 ) ) {} // if rand5 returns 5 call again

  return a & 0x1 ; // return last bit of number so there is equal chance of getting 0 or 1
}


rand7() {
 
while( (a = 4*rand_0_or_1() + 2*rand_0_or_1() + rand_0_or_1())==0) {} //if it is zero call again

return a;

}

- Roshan Mangal May 31, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I 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

- GKalchev May 31, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

float rand7() {

return ( (rand5()/5)* 7 ) ; 

}

- Please someone verify if following logic is correct : ? September 12, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This is not correct. As your rand7() method will always return a number divisible by (5/7). Consequently the probability of occurrence any number that is not divisible by 5/7 is 0.

- chandransuraj February 11, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;

}

- ganjiayan September 13, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

i guess doing modulo 8 to the expression results in the no from 2 onwards..

- Anonymous September 18, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- chandransuraj February 11, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

int rand7(){
  int a = rand5();
  int b = 0;
  
  do{
    b = rand5();
  }while(a * b > 21);

  return a * b / 3;
}

- BXH September 13, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int rand7(){
  int a = rand5();
  int b = 0;
  
  do{
    b = rand5();
  }while(a * b > 21);

  return a * b / 3;
}

- BXH September 13, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

u dont have to use while loops etc. simply write rand5()+rand5()%3

- Anonymous September 13, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Wrong, because:
1) The number returned is between 0 and 3
2) The number returned will not be random

- chandransuraj February 11, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

modulo 7 of 2*rand(5)

- PrateekCaire September 13, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Sorry..
modulo7 of (rand(5) + rand(5))

- PrateekCaire September 13, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Wrong. See my comments on ganjiayan's answer

- chandransuraj February 11, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- papaya September 13, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

how abt this?

int x = rand5();
int y = rand5() % (7-x);
return x+y;

- Anonymous September 15, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;

- AAD September 15, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- JeffD September 16, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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) {

- jimmyzzxhlh September 19, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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).

- JeffD September 20, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- fmb September 16, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Excellent solution dude :)
But you can just write a simple version of this as:

int rand7()
{
	int i;
	do
	{
		i = 2*rand5() - 1;  //Numbers from 0 to 9 are generated with a probability 
                                             //of 1/9.
	}while(i > 7)

	return i;  //  1 <= i <= 7, where probability of each number = 1/9.
}

- Sanjay Agarwal August 29, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- Anonymous September 17, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

rand7() = rand5()+(rand5()%2)

- Anonymous September 22, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

rand7() = rand5()+((rand5()%2)+1)

- Anonymous September 22, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

The problem with this solution is the probability of getting numbers 1 to 5 is less than the probability of getting 6 and 7

- Anonymous September 22, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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
?

- Anonymous October 05, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

{{rand5()%3 will not choose 0,1,2 with equal probabilty
as rand5() generates number b/w 1 and 5 so
P(0) = 1/5
P(1) = 2/5
P(2) = 2/5

hence
for avoiding this

i think this will work


A = rand5()%3
B = (rand5()+1)%3
C = (rand5()+2)%3

rand7() = rand5()+ (A+B+C)%3

}}

- Aditya October 10, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- Anonymous October 13, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

It is not unifrom probability. Probablity for 7 is (1/5)^7, others are larger than this

- lwz October 25, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

I think the solution should looks like :

int sum = 0;
for(int i = 0; i < 4; i++)
{
sum += sum * 5 + rand5() - 1;
}
return sum % 7 + 1;

the loop produce number [0,4444] (based on 5-coded)
0%7 = 0 4444%7 = 6 this is uniform probablity

- lwz October 25, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

why not rand7()=((rand5-1)/4)*6+1 ??

- Anonymous November 01, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Can anyone comment this post? I think this is the best answer here.

- Anonymous May 31, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

This will never give zero..

- Anon February 29, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

int x;
do{
x = 5*rand5() + rand(5) - 5;
}while(x>21) // i.e. ignore if value of x is greater than 21 and again select new
return x%7

- Anonymous February 16, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

//rand_s() is rand5();
    int s = 5; d = 7;    
    int rand_d()
    {
        static int i = 0;
        int val = rand_s();
        if(val == s)
        {
            val = s + i;
            ++i;
            i = i % (d - s + 1); 
        }
        return val;
    }

- Anonymous March 10, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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 ;

- Paras March 16, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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 ;

- Anonymous March 17, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

As rand5() is giving numbers btw 1 and 5 which is not even 1 and 5....so I think the following code should work

int rand7()
{
int m=rand5();
if(m<=2)
{
m mode 7;
}
else
{
(m+1) mode 7
}
}

please let me if I am wrong...!!

- Yama March 18, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

As rand5() is giving numbers btw 1 and 5 which is not even 1 and 5....so I think the following code should work

int rand7()
{
int m=rand5();
if(m<=2)
{
m mode 7;
}
else
{
(m+1) mode 7
}
}

please let me if I am wrong...!!

- Yama March 18, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

As rand5() is giving numbers btw 1 and 5 which is not even 1 and 5....so I think the following code should work

int rand7()
{
int m=rand5();
if(m<=2)
{
m mode 7;
}
else
{
(m+1) mode 7
}
}

please let me if I am wrong...!!

- Yama March 18, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

As rand5() is giving numbers btw 1 and 5 which is not even 1 and 5....so I think the following code should work

int rand7()
{
int m=rand5();
if(m<=2)
{
m mode 7;
}
else
{
(m+1) mode 7
}
}

please let me if I am wrong...!!

- Yama March 18, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

As rand5() is giving numbers btw 1 and 5 which is not even 1 and 5....so I think the following code should work

int rand7()
{
int m=rand5();
if(m<=2)
{
m mode 7;
}
else
{
(m+1) mode 7
}
}

please let me if I am wrong...!!

- Yama March 18, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- CheckThisOut April 23, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

one correction to above code

while(!(PairSet.contains((num1, num2)) || PairSet.contains((num2, num1))))

- CheckThisOut April 23, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

a= rand(5)
b = (a*3 - 1)/2

I did this in my fifth grade.

- zhiming dai April 26, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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?

- Mike May 15, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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 :)

- MikeC May 15, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

:P

- aman August 09, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int rand7()
{
while(1)
{
int n = 5 * rand5() + rand5();
if(n < 21)
return n % 7; // or else more weighted towards generating 0 to 3
}
}

- Anonymous July 17, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- miaomiao August 06, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int rand7()
{
int vals[5][5] = {
{ 1, 2, 3, 4, 5 },
{ 6, 7, 1, 2, 3 },
{ 4, 5, 6, 7, 1 },
{ 2, 3, 4, 5, 6 },
{ 7, 0, 0, 0, 0 }
};

int result = 0;
while (result == 0)
{
int i = rand5();
int j = rand5();
result = vals[i-1][j-1];
}
return result;
}

- brady May 01, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

rand7() {
    return (2^2 * (rand5%2) + 2^1 * (rand5%2) + 2^0 (rand5%2));
}

- Neutron September 04, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int rand7(){
	while(true){
		int x=5*rand5()+rand5();	
		if(x<=28) 
			return x%7+1;
	}

- Charlie January 08, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int rand(7)
{
	return rand(5) + (rand(5) % 3 < 2 ? rand(5) % 3 : 2 ;
}

- 26788 July 11, 2014 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More