Google Interview Question for Software Engineer / Developers


Country: United States
Interview Type: In-Person




Comment hidden because of low score. Click to expand.
0
of 0 vote

should have asked then, that might be the answer :D

- kkr.ashish January 29, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

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.

- lakshaman January 29, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Are all derangements equally likely?

- Anonymous January 29, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

It didnt solve the issue of how to keep generating a random number within a range while excluding the numbers already picked.

- Guy January 30, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Dave January 29, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

It didnt solve the issue of how to keep generating a random number within a range while excluding the numbers already picked.

- Guy January 30, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

It does, if you include the extra bit before the for loop. In python, random.sample(population, k) will sample k items from population without repetition.

- Dave January 30, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Seems like the challenge is how to keep generating a random number within a range while excluding the numbers already picked.

- Guy January 30, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Stephen February 04, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- Alex February 02, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Dave February 14, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- Moe December 17, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Considering googling this problem leads to it being the same as detecting a Hamiltonian cycle, a O(n) solution is impossible

- Westhester February 09, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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;
}

- Anonymous January 29, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

you are missing something what for j==0 and also its not really random as it will be not uniform probablity for secret

- kkr.ashish January 29, 2014 | Flag


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More