Google

www.google.com
Engaged Employer

## Interview Question

Interview Los Angeles, CA

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

Answer

## Interview Answer

4 Answers

0

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

idispatch on Apr 17, 2013
0

(random permutation insufficient; must ensure that permutation is not a derangement) public static ArrayList<Integer> secretSanta(int N) { ArrayList<Integer> possibleSolution; while (true) { possibleSolution = new ArrayList<Integer>(); ArrayList<Integer> remainingRecepients = new ArrayList<Integer>(); for (int i = 0; i < N; i++) { remainingRecepients.add(i); } while (remainingRecepients.size() > 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; }

Rahul on May 5, 2013
0

public ArrayList<Integer> secretSanta ( int n) { ArrayList <Integer> solution = new ArrayList <Integer>(n); int remaining = n-1; Random generator = new Random(); for (int i=0; i<n; i++) { int r = generator.nextInt( remaining -i -1) + i+1; solution.add ( r ); remaining--; } return solution; }

random_consumer on Sep 14, 2013
0

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)

eleane on Oct 23, 2014

## Add Answers or Comments

To comment on this, Sign In or Sign Up.