## Google Interview Question for SDE1s

Country: United States

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

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

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

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

``````#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;
++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";
}
}``````

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

Let's call this function rand();

``````int randomNumber = a-1;
for(int i = 0; i < b-a; i++){
if rand() = 0
randomNumber++;
}``````

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

Let's assume the function that randomly returns 1 or 0 is called rand() and is defined in the same class.

``````public int randBetweenAandB(int a, int b){
int r = a-1;
for(int i = 0; i < b-a; i++){
if(rand() == 1)
r++;
}

return r;

}``````

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

random function for every bit
or
rand + 2 * rand + 4*rand + ...
you can see that rand + 2 *rand output 0 1 2 3 uniformly

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.

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