Google

www.google.com
Employer Engaged

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<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.