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

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.