Given an integer array shuffle the elements in the array such that no two elements are in same place

Question

Utilisateur anonyme · Accepted Answer

I tried to write a shuffle metho using random generator but it had couple of issues and interviewer helped me but i wasn't able to complete the program . I only had one program and it was more like discussion with interviewer on how to solve not sure if there is any easy way to solve this

Interview Answer in Java · Answer

Here is my answer in Java. The function nextInt(bound) always selects a random integer between 0 (inclusive) and the "bound" (exclusive). Thus, you can use the length of the array as the bound so a randomly selected index will always in bounds. My method steps through the array and for each step, a random number (in bounds) is generated and the current index is swapped with the generated one. Therefore, every number in the array has a chance to be shuffled. It runs in linear time: Overall O(n) given n elements.

public static void shuffle(int[] array) {
		Random rand = new Random();
		int temp, index;
		for(int i = 0; i < array.length; i++) {
			temp = array[i];
			index = rand.nextInt(array.length);
			array[i] = array[index];
			array[index] = temp;
		}
}

Google

Question d’entretien chez Google

Réponses aux questions d'entretien

Entreprises suivies

Recherche d’emplois