Google Interview Question: Write a routine that does sec... | Glassdoor

Google

## Interview Question

Software Engineer 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 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;
}

Rahul on May 5, 2013
0

public ArrayList secretSanta ( int n) {

ArrayList solution = new ArrayList (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.