Google Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: In-Person
Secret Santa should mean shuffle the contents of an array where if the index of element represent a person the content would represent the person who is assigned [for gifting] to him.
Input would : 0 , 1, 2, 3, 4 ...n
Output should be : shuffled contents such that a[i] != i
Iterate over elements of the array:
copy the content to next cell
copy the content of last cell to first cell.
The approach can be randomized by picking the shift distance randomly instead of 1.
Input: A list of santas, by some unique identifier.
Output: "id1 --> id2" means santa with id1 is assigned to the santa with id2.
If there are no restrictions on "randomness":
santas = [0,1,2,3,4,5,6,7,8,9]
for j in xrange(0, len(santas)):
if j+1 == len(santas):
print "%s -> %s" % (santas[j], santas[0])
else:
print "%s -> %s" % (santas[j], santas[j+1])
If need to be random, just add this before for loop:
import random
santas = random.sample(xrange(0,len(santas)),len(santas))
It didnt solve the issue of how to keep generating a random number within a range while excluding the numbers already picked.
Seems like the challenge is how to keep generating a random number within a range while excluding the numbers already picked.
on input people [] of size n
have a parallel array, secretsantas[]
and a Random number generator r
sequentially fill in secretsantas[] by picking a random person of the range [0,n) from people[].
upon picking a person, swap the selected person with the last person. decrement your range each time.
this solves the aforementioned problem of picking a random person when the number keeps changing.
also, don't pick yourself.
I think the solution could be found in terms of permutations.
First, let's define the state as some permutation that could be divided on cycles, like:
1 3 2 -> 2 cycles 1 -> 1, and 3 -> 2 -> 3.
Then in one iteration we can merge 2 cycles. Just find random 2 components and random vertices in each.
Using pointers we can do everything in linear time.
sounds like graph visitation problem, each person is a vertex, the direct edge is the direction of the gift giving, keep picking random vertices from a list of unvisited vertices
or put it another way, make the graph completely connected and do a DFS, skipping vertices that have already been visited
1) Duplicate the list of people to a second list
2) For every person in first list, select random(size of list) from the second list and remove that person.
Note: make sure not to select identical person. can be done in O(1).
If identical person is selected then add it to the first of the list and then select(random+1)
This will insure that we wont reselect it another time ..
The above solution will take O(n) if find and remove from list is O(1).
This is not the case in linkedlist: find is O(k) itself.
If an array was used as the list then removal is O(n) time (shifting elements after removing)
Keep in mind that we sacrificed space and extra time to build the list in the first place.
vector< pair<string, string> > santa(vector<string>& names)
{
vector<string> tmp = names;
vector< pair<string, string> > ans;
int n = names.size();
for (int j = n-1; j>=1; j++) {
int k = rand(0, j-1);
swap(tmp[k], tmp[j]);
}
for (int i= 0 ; i < n; i++)
ans.push_back( make_pair(tmp[i], names[i]) );
return ans;
}
should have asked then, that might be the answer :D
- kkr.ashish January 29, 2014