Interview Question

Software Engineer Interview Los Angeles, CA

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

Answer

Interview Answer

3 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

Add Answers or Comments

To comment on this Question, Sign In with Facebook or Sign Up