Write a routine that does secret santa in O(N) time.

Question

eleane · Accepted Answer

Best Sol: Shuffle the list, and then split the list into two. Do the pairing within the two groups.
Second Best: Shuffle the list, and then form adjacent pairs from the list. (This solution doesn't give all the permutations)

idispatch · Answer

is it just a random permutation of an array (done in O(n))?

Rahul · Answer

(random permutation insufficient; must ensure that permutation is not a derangement)

public static ArrayList secretSanta(int N) {
	ArrayList possibleSolution;
	while (true) {
		possibleSolution = new ArrayList();
		ArrayList remainingRecepients = new ArrayList();
		for (int i = 0; i  0) {
			int chosenIndex = r.nextInt(remainingRecepients.size());
			Integer recepient = remainingRecepients.get(chosenIndex);
			remainingRecepients.remove(recepient);
			possibleSolution.add(recepient);
		}
		boolean valid = true;
		for (int i = 0; i < N; i++) {
			if (possibleSolution.get(i).intValue() == i) {
				valid = false;
				break;
			}
		}
		if (valid) break;
	}
	return possibleSolution;
}

random_consumer · Answer

public ArrayList secretSanta ( int n) {
	
ArrayList  solution = new ArrayList (n);

int remaining = n-1;

Random generator = new Random();

for (int i=0; i

Google

Google Interview Question

Interview Answers

Want the inside scoop on your own company?

Bowls

Followed companies

Job searches