CareerCup

int f29() {
       int radix = 2;
       int res;
       do {
       res = f1() * radix^4 + f1() * radix^3 + f1() * radix^2 + f1() * radix^1 + f1();
       } while (res > 29);
       return res;
}

Why not use system time? The seconds go from 0-59
f(1)= get the current time and extract the seconds%2.
f(29)= get the current second, f(29)=(second>=29)?second:(second-30)

From Elements of Programming Interviews;

int UniformRandom(int a, int b)
{
	int t = b - a + 1;
	int res;
	do
	{
		res = 0;
		for (int i = 0; (i << 1) < t; i++)
		{
			res = (res * 2) | f1();
		}
	} while (res >= t);
}

return res + a;

int Gen29()
	{
		while(1){
			
			int Res = 0;

			for(int i = 0; i  < 5; ++i){

				Res = Res << 1 | f1();
			}

			if(Res <= 29)
				return (Res);
		}
	}

Reservoir sampling seems appropriate solution.

how about calling f1() 29 times and adding them as it would generate 0 to 29 with equal probabolity

use bit wise operators

int x = f1();
x = (x << 1 + f1);
x = (x << 1 + f1);
x = (x << 1 + f1);
x = (x << 1 + f1);

/// Javascript
 function f29(){
  return (f1() * (29 - 0)) + 0
 }

int
random (int x)
{

if (x == 2) {
return f1() + f1();
}
return random(x-1) + f1();
}

Solution
Given f1()
Lets build for f2()
f2() is f1() + f1(): which can deliver 0 + 0 or 0+1 or 1+1 or 1+0 (equal probability)

Now build f3()
f3 is f2() + f1() :
the above code works in this fashion

Do it binary search way. Pick any half with equal probability until you finally land at one number. O(log 29)

int left=0
int right = 29


while(left<right){
	
	int mid = (left+right)/2

	if(f1())
		left=mid;
	else
		right=mid;

	if(left==right)
		return left;

		}

Adapting the binomial options pricing model and compound probability we should be able to return the sum of f(1) over 30 trials to give us equal probability in returning [0..29]
The probability is going to be .5^29

public static int f29() {
	int start = 0;
	int randomPick = 0;
	while (start <= 29) {
		randomPick += f1();
	}
	return randomPick;
}