## Google Interview Question for Web Developers

Team: Solutions Engineering Team
Country: United States
Interview Type: Phone Interview

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

Use shiftxor algorithm to generate a random number:

``````#include "CommonHeader.h"

// Generate RNG numbers.
// The below initialises the seed to pre-determined number
// To get a TRNG (True-Random-Number-Generator) one should initialise the
// seed with a true random number (e.g. capture the mouse current point and use it as the seed)

static size_t s_seed = 940983058;

void setSeed(int seed) { s_seed = seed; }

size_t rng()
{
size_t x = s_seed;
x ^= x << 17;
x ^= x >> 19;
x ^= x << 13;
s_seed = x;
return x;
}

size_t rng(size_t min, size_t max)
{
if(min >= max) return std::string::npos;
if(min == max) return min;

size_t x = s_seed;
x ^= x << 17;
x ^= x >> 19;
x ^= x << 13;
s_seed = x;

// apply the limits
x = (x % (max - min)) + min;
return x;
}``````

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

``````/**
* @brief Generates a random integer
* @return A random positive integer or a zero
*/
int getRandom()
{
/* Three large prime numbers */
/*Refer to compoasso.free.fr/primelistweb/page/prime/liste_online_en.php */
int a = 1000003;
int b = 2000003; // b = 2*a or closest prime number
int c = 3000017; // c = 3*a or closest prime number

static int seed = 5;

int newSeed = ((a * seed) % c + b) % c;
if(newSeed < 0)
{
newSeed += c;
}

if(newSeed == seed)  // IS IT POSSIBLE ?? I DO NOT KNOW HOW TO PROVE/DISPROVE IT.
{
std::cout << "\nREPETITION FOUND !! " << seed << "\n";
seed += a;
/*Explanation for above step
* We are effectively doing the operation y = (ax + b) mod c, where a, b, c are primes
* Suppose we get some bad case when y = x [IS IT POSSIBLE ?? I DO NOT KNOW]
* That implies (ax + b) mod c = x
* Now, what if we replace x with (x + a) ? Will we still get x yet again ? NO
* PROOF : Let (ax + b) mod c = x
* To prove : It is impossible that (a(x + a) + b) mod c = x
* If above is possible, we can equivalently say
* (ax + a*a + b) mod c = x
* or, {(ax + b) mod c + (a*a) mod c} mod c = x
* or, {x  + a*a} mod c = x
* This is possible if and only if (a*a) is a multiple of c, which is IMPOSSIBLE because
* a != c, and both a and c are primes
* So, the logic of adding a to seed will definitely ensure that
* we do not get seed again in very next iteration
* */
}
else
seed = newSeed;

return seed;
}

/**
* @brief Generates a positive random integer in the range min to max
* @param min Lower limit
* @param max Upper limit
* @return A random positive integer
*/
int getRandom(int min, int max)
{
if(min < 0 || max < 0 || min > max)
throw "min must be strictly less than max";
if(min == max)
return min;
else
{
int diff = max - min;
return min + getRandom() % (diff + 1);
}
}``````

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

Check if there is anything statistically wrong with above code.
I tried it and can see approximately 51:49 distribution of 0 and 1 when running it for getRandom(0, 1).

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

Check if there is anything statistically wrong with above code.
I tried it and can see approximately 51:49 distribution of 0 and 1 when running it for getRandom(0, 1).

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.