## Google Interview Question

SDE1s**Country:**United States

```
#include <iostream>
#include <unordered_map>
using namespace std;
bool Rand2()
{
return rand() % 2;
}
uint32_t RandAB(uint32_t a, uint32_t b)
{
uint32_t max_val = b - a;
int bits = 0;
for (uint32_t mask = 1; mask <= max_val && mask != 0; mask <<= 1) {
++bits;
}
uint32_t rnd = 0;
do {
rnd = 0;
for (int i = 0; i < bits; ++i) {
rnd <<= 1;
rnd |= Rand2();
}
} while (rnd > max_val);
return a + rnd;
}
int main()
{
srand(time(NULL));
unordered_map<uint32_t, int> stats;
for (int i = 0; i < 100000000; ++i) {
++stats[RandAB(3, 14)];
}
for (auto &el : stats) {
cout << el.second << "=>" << el.first << "\n";
}
}
```

Here is my Solution:

```

public void random(int a, int b) {

int num = 1<<31;

int min=num|a;

int max=num|b;

StringBuilder sb=new StringBuilder("");

String minStr=Integer.toBinaryString(min);

String maxStr=Integer.toBinaryString(max);

int idx=1;

while (idx< maxStr.length()){

if(minStr.charAt(idx)!=maxStr.charAt(idx)) break;

sb.append(minStr.charAt(idx));

idx++;

}

int temp=idx;

while (true){

while (idx<maxStr.length()){

String r=rand();

sb.append(r);

idx++;

}

if((Integer.parseInt(sb.toString(),2) >=a &&

Integer.parseInt(sb.toString(),2)<=b)){

System.out.println(Integer.parseInt(sb.toString(),2));

break;

}

sb.delete(temp-1,sb.length());

idx=temp;

}

}

private String rand() {

Random rd = new Random(); // creating Random object

return !rd.nextBoolean() ? "0" : "1";

}

```

between a and b, I assume a half open interval [a, b)

- Chris December 03, 2017question is the distribution, if it should be normal, the previous posts are probably right (needs a prove though). If we want uniform distribution things are different.

I could create a random function that creates a uniform random number in the range [0 and 2^n) by applying the given function to each bit. Then I could use this new function to create a random number in the range [0, 2^n) where n would be lg2(b-a) + 1. If the random number exceeds b-a, I try again, if not, I add it to a and return the result.