Google Interview Question for Software Engineer / Developers


Country: India




Comment hidden because of low score. Click to expand.
6
of 8 vote

Assumption 1st natural numbers include 0: 0,1,2,3,4,5 would be a valid result if n = 6

1. we need a function to produce a random number between 0..k-1 interval: [0..k)
let's suppose we had this.
2. choose the element for the first position in the array with 1/n probability
3. choose the element for the second position the array with 1/(n-1) probability etc...

// forward declaration: produces random number between 0..k-1
int random(int k);

vector<int> createPermutedArray(int n)
{
	vector<int> a(n);
	for(int i = 0; i < n; i++) a[i] = i;
	for(int i = 0; i < n - 1; i++)
	{
		int j = i + random(n - i); 
		swap(a[i], a[j]);
	}
	return a;
}

now let's think how can we create the random function that returns [0..k) from a random function that returns [0..1), at first glance, just multiply by k, right?

int random(int k)
{
	double r = random(); // [0..1)
	return r * k;
}

the question is, is the distribution 0..k-1 truely uniform if random [0..1) is uniform?
let's see:
everything between [0..1/k) maps to 0
between [1/k .. 2/k)) maps to 1
between [(k-1)/k .. k/k) maps to k-1
k/k = 1, it seems uniform at this point, but double is represented in binary and thus if k is not a power of 2 the number space cannot be seperated in exactly same sized spaces.
Let's for a moment think a double would be 8bit fixed point and k would be 3
[0..85)-> 0, p(0) = 85/255
[85..170) -> 1, p(1) = 85/255
[170..256) -> 2, p(2) = 86/255
this is not uniform. So it turns out above int random(int k) is not truely uniform either. How to get it uniform (if that little non-uniformity would matter)
first of all I would get rid of the double and just use the mantissa which is an integer, I think of about 54 bits on a 64 bit system for simplicity, how ever, let's assume it's 8 bits and scale it up later and let's suppose our k is 7
- floor((2^8) / 7) = 36
- 36 * 7 = 252

int r;
	while((r = randomInt()) >= 252);
	return r / 7;

now create randomInt to extract the mantisa from the double and replace the calculation's constants
appropriately. There is almost certainly a solution while keepting the double as well, maybe somebody could point it out.

- Chris November 15, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

it's a shuffle deck question.
(1) prepare a vector filled with 1-n (the deck) in order
(2) for(int I=0;i<n;i++)
int ind=floor(random()*INT_MAX)%n; //that gives a random index in 0 to (n-1)
swap(deck[i],deck[ind]);
That's it. The code only uses the random API given in the question. There is no need to write a new random function.

- CinamenBun November 16, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

@guangsumengmianxia
be carefull in an interview with these statement it shows some ignorance to important details even if your answer is very practical and fast.

But your shuffle has a problem the way you wrote it (I once thought it would be easier that way you wrote it and got suspicious, so I checked it a while ago and it wasn't good at all). If your variable "ind" was uniform, your swap will not lead to a uniform distribution, because the elements in front are more likely to be swapt multiple times. Essentially, the index 0 has probability 1/n to land at any place in the interval [0..n) at the first iteration (which is good). But, if it is swaped with any of the elements in [1..n) the element which originates from index 0, has another chance to go back to it's original position thus pulling the probability slightly towards staying at it's original position.
You can prove it or you can write a monte carlo to show it. I did both, the shuffle will not produce a random permutation (which is usually understood as every permutation has exactly the same probability to occure, which is 1/(n!)) although it is close to one.

2) doing the modulo will not be truely uniform except when n is a power of 2. While this is minor there are situations where it matters. So it's essential to be aware of and advantageous to know a way out.

yea, you are right, there is no need for a new random number generator, but for a function that uses the existing one and makes one whre you can define the interval. Be it in a function or just a line of code is really not the question here.

- Chris November 16, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

To do Uniform stuff, one needs to do these steps.
1. Get a function -> next_higher_permutation( array ) : available from here :
stackoverflow.com/questions/1622532/algorithm-to-find-next-greater-permutation-of-a-given-string
2. A random no generator to pick large integers from range [0,N)
3. A really large integer container for storing n! ( n factorial ).

Now, the algorithm.
1. Use [2] to generate a number between 0 and n! ( n factorial ) say it is N.
2. Start with the sorted permutation : [ 0,1,2,...n-1 ] as array and then apply
next_higher_permutation on the array N times.

- NoOne November 15, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

that's a shuffle deck question
(1) fill an array deck[n] with numbers 1 to n;
(2) for(int I=0; I<n;i++){
int ind=floor(random()*INT_MAX)%n; //gives a random index from 0 to n-1
swap(deck[i],deck[ind]);
}
that's it. There is no need to rewrite a random function. You only need to use the API random() given in the question.

- guangsumengmianxia November 16, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

namespace RandomPermutation {

float getRandom() {
double randValue = rand();
return randValue / RAND_MAX;
}

int getRandomInt(int max) {
return getRandom() * max;
}

vector<int> getRandomPermutation(int n) {
vector<int> permutation(n,-1);
for (int i=0; i<n; i++) {
permutation[i] = i+1;
}

int temp;
for (int i=0; i<n; i++) {
int shuffleIndex = getRandomInt(n);

temp = permutation[i];
permutation[i] = permutation[shuffleIndex];
permutation[shuffleIndex] = temp;
}
return permutation;
}
}

- EmilFlater November 16, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I assume that we not rotating ' . ' but just a number around so if the input will be something like 0.123456789 ans we want to rotate 3 number the outcome will be. 0.123456789
1.023456789
1.203456789
2.103456789
2.013456789
0.213456789
As you can see we rotating only 3 numbers around ' . ' symbol and to tall permutation is n!.

public class NumPermutation {

    static int chunk = 0;
    static StringBuilder builder;

    public static void main(String[] args) {

        builder = new StringBuilder(getRandNumberAsString());

        chunk = 3;
        permutate(chunk);
    }

    public static String getRandNumberAsString(){
        StringBuilder builder = new StringBuilder(String.valueOf(Math.random()));
        builder.deleteCharAt(1);
        return builder.toString();
    }

    public static void permutate(int size){
        if (size == 1){
            return;
        }

        for (int i = 0; i < size; i++) {
            permutate(size - 1);
            if (size == 2){
                System.out.println(builder.charAt(0) + "." + builder.substring(1));
            }
            leftRotation(size);
        }
    }

    public static void leftRotation(int size){

        char tmp = builder.charAt(0);
        char arr[] = builder.toString().toCharArray();
        for (int i = 0; i < size; i++) {
            arr[i] = arr[i + 1];
        }
        arr[size - 1] = tmp;
        builder = new StringBuilder(String.valueOf(arr));
    }
}

- hasskell November 16, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public int[] getRandomPermutation(int n){
	int[] result = new int[n];


	for(int i = 0; i < n; i++){
		result[i] = i;
} 
	
	for(int i = 0; i < n; i++){
		int index = i + (int)(getRandom() * (n - i));
		int aux = result[i];
		result[i] = result[index];
		result[index] = aux;
	}


	return result;


}

- libertythecoder November 20, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

from random import random

def random_permutation(n):
    numbers = [i for i in xrange(1, n+1)]
    print numbers
    
    for i in xrange(n):
        random_index = int(random()*n)
        temp = numbers[i]
        numbers[i] = numbers[random_index]
        numbers[random_index] = temp
    
    return numbers    
        
print random_permutation(10)

- Nitish Garg December 25, 2016 | 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