Give pseudocode over phone and code on a shared screen how to scramble an array of integers in random order. Then optimize it for better performance.

Question

Give pseudocode over phone and code on a shared screen how to scramble an array of integers in random order.  Then optimize it for better performance.

Pavel · Accepted Answer

The above method is the most common solution to this problem, and it is incorrect. There is a huge probability that several cards will remain in the exact same place. What you want to do is take cards out, one by one, out of the unshuffled array and insert them in a random position into a shuffled array.

Rob · Answer

This solution generates a random ordering of the numbers with probabilty 1/n that any value ends up in any specific index:


    public static void swapValues(int[] array, int idx1, int idx2) {
        int temp = array[idx1];
        array[idx1] = array[idx2];
        array[idx2] = temp;
    }
    
    public static void randomizeArray(int[] array) {
        Random random = new Random();

        for (int i = array.length - 1; i >= 0; i--) {
            // get a random index in the array from {0, 1, ..., i }
            int idx = random.nextInt(i + 1);
            
            // move the value at the index to the end of the array
            swapValues(array, idx, i);
        }
    }

Rishi · Answer

int[] arraycard = new int[num];
		i = 0;
		for (i = 0; i < num; i++)
			arraycard[i] = i;
		Random randomInt = new Random();
		int t;
		for (j = 0; j < num; j++) {
			int rand1 = j + randomInt.nextInt(num - j);
			t = arraycard[j];
			arraycard[j] = arraycard[rand1];
			arraycard[rand1] = t;

		}

Amazon

Pergunta de entrevista da empresa Amazon

Respostas da entrevista

Empresas seguidas

Buscas de vagas