Google

  www.google.com
Work in HR? Unlock Free Profile

Google Software Engineer Interview Question

I interviewed in Los Angeles, CA and was asked:
"Write a routine that does secret santa in O(N) time."
Add Tags [?]
Answer

Part of a Software Engineer Interview Review - one of 3,029 Google Interview Reviews

Answers & Comments

0
of 1
vote
is it just a random permutation of an array (done in O(n))?
- idispatch on Apr 17, 2013
0
of 1
vote
(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
of 0
votes
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

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

Tags are like keywords that help categorize interview questions that have something in common.